deque and vector

Daniel

unread,

Dec 4, 2016, 11:46:04 PM12/4/16

to

In vs 2015, the following compiles:

#include <vector>

template <class T>
struct A
{
std::vector<T> d_;
};

struct B
{
A<B> x_;
};

int main()
{
B b;
}

However, replacing vector with deque,

#include <deque>

template <class T>
struct A
{
std::deque<T> d_;
};

struct B
{
A<B> x_;
};

int main()
{
B b;
}

fails with error message "use of undefined type 'B'"

Is that expected?

Thanks,
Daniel

Ian Collins

unread,

Dec 5, 2016, 12:05:42 AM12/5/16

to

Where?

> Is that expected?

No, are you sure you posted what you compiled?

--
Ian

Alf P. Steinbach

unread,

Dec 5, 2016, 7:07:02 AM12/5/16

to

In the C++03 days it would be expected, also for the vector.

A standard library container item type could not be of incomplete type,
so you'd get the same problem with

struct S { vector<S> v; };

But I have a vague recollection that this was changed in C++11 or C++14.
Not sure though. Technically it can be supported because the various
/operations/ of that vector are not instantiated until they're used, at
which point S is complete, e.g. its size is known.

Cheers & hth.,

- Alf

Mr Flibble

unread,

Dec 5, 2016, 12:31:05 PM12/5/16

to

value_type requirements have indeed been decomposed into the functions
that use them rather than for the container as a whole.

/Flibble

Daniel

unread,

Dec 5, 2016, 10:13:11 PM12/5/16

to

On Monday, December 5, 2016 at 12:05:42 AM UTC-5, Ian Collins wrote:
> On 12/ 5/16 05:45 PM, Daniel wrote:
> > In vs 2015, the following compiles:
> >
> > #include <vector>
> >
> > template <class T>
> > struct A
> > {
> > std::vector<T> d_;
> > };
> >
> > struct B
> > {
> > A<B> x_;
> > };
> >
> > int main()
> > {
> > B b;
> > }
> >
> > However, replacing vector with deque,
> >
> > #include <deque>
> >
> > template <class T>
> > struct A
> > {
> > std::deque<T> d_;
> > };
> >
> > struct B
> > {
> > A<B> x_;
> > };
> >
> > int main()
> > {
> > B b;
> > }
> >
> > fails with error message "use of undefined type 'B'"
>
> Where?

It can't compile

enum {_EEN_DS = _DEQUESIZ}; // helper for expression evaluator

#define _DEQUESIZ (sizeof (value_type) <= 1 ? 16 \
: sizeof (value_type) <= 2 ? 8 \
: sizeof (value_type) <= 4 ? 4 \
: sizeof (value_type) <= 8 ? 2 \
: 1) /* elements per block (a power of 2) */

Daniel

unread,

Dec 5, 2016, 10:25:21 PM12/5/16

to

On Monday, December 5, 2016 at 10:13:11 PM UTC-5, Daniel wrote:
>
> #define _DEQUESIZ (sizeof (value_type) <= 1 ? 16 \
> : sizeof (value_type) <= 2 ? 8 \
> : sizeof (value_type) <= 4 ? 4 \
> : sizeof (value_type) <= 8 ? 2 \
> : 1) /* elements per block (a power of 2) */
>
> >

Although if I understand this correctly, it seems to be allocating in chunks of
16 bytes, which would be unhelpful for my purposes.

Daniel

Öö Tiib

unread,

Dec 6, 2016, 1:02:54 AM12/6/16

to

Yes, 'std::deque' of Microsoft standard library is odd. Smaller chunks
than one L1 cache line (so 64 bytes modern times) do not make sense.

Scott Lurndal

unread,

Dec 6, 2016, 8:33:23 AM12/6/16

to

Most allocators will return space aligned to the largest native
type requirement (e.g. 16-bytes for 128-bit SIMD data). Particularly
important on architectures that don't support unaligned accesses.

Scott Lurndal

unread,

Dec 6, 2016, 8:35:33 AM12/6/16

to

Don't be silly. Some processors have 128-byte cache lines. If
one is allocating 32-bytes, there is very seldom reason to waste the
other 32 (or 96) bytes.

The standard allocators will always return memory aligned to the
largest native type supported by the architecture (typically 128-bits
on x86 and arm64) as per the various psABI's.

Gerald Breuer

unread,

Dec 6, 2016, 9:26:52 AM12/6/16

to

Am 05.12.2016 um 05:45 schrieb Daniel:
> In vs 2015, the following compiles:

> ...

That might depend on that the following does compile:

template<typename T>
struct S
{
T *pt;
};

struct C
{
S<C> sc;
};

But this doesn't compile:

template<typename T>
struct S
{
T t;
};

struct C
{
S<C> sc;
};

Don't know when this changed.

Öö Tiib

unread,

Dec 6, 2016, 6:31:18 PM12/6/16

to

On Tuesday, 6 December 2016 15:35:33 UTC+2, Scott Lurndal wrote:
> =?UTF-8?B?w5bDtiBUaWli?= <oot...@hot.ee> writes:
> >On Tuesday, 6 December 2016 05:25:21 UTC+2, Daniel wrote:
> >> On Monday, December 5, 2016 at 10:13:11 PM UTC-5, Daniel wrote:
> >> >
> >> > #define _DEQUESIZ (sizeof (value_type) <= 1 ? 16 \
> >> > : sizeof (value_type) <= 2 ? 8 \
> >> > : sizeof (value_type) <= 4 ? 4 \
> >> > : sizeof (value_type) <= 8 ? 2 \
> >> > : 1) /* elements per block (a power of 2) */
> >> >
> >> > >
> >> Although if I understand this correctly, it seems to be allocating in
> >> chunks of 16 bytes, which would be unhelpful for my purposes.
> >
> >Yes, 'std::deque' of Microsoft standard library is odd. Smaller chunks
> >than one L1 cache line (so 64 bytes modern times) do not make sense.
> >
>
> Don't be silly. Some processors have 128-byte cache lines. If
> one is allocating 32-bytes, there is very seldom reason to waste the
> other 32 (or 96) bytes.

I was saying it not about allocators but about the small arrays that
Microsoft's 'std::deque' internally allocates.
If the chunks that deque internally allocates are very small then
that hurts its performance and usage cases where it is better than
vector are rare.