Sign in to follow this  
Tybon

Problem with deque

Recommended Posts

Tybon    194
Hi, I am having a problem with declaring a deque member variable of the same type as the class containing the member variable. If I use a different type then there is no problem. I also don't have this problem with vectors, so there must be something different about the way queue/deque are constructed. If you know what going on then please help! Thanks.
class X {};

class Q
{
	std::deque<Q> Q_dq;	// compile error
	std::deque<X> X_dq;	// no problem
	std::vector<Q> Q_v;	// no problem
};

These are the errors from the compiler: c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\deque(59) : error C2027: use of undefined type 'Q' c:\Dev\Queue\Queue.cpp(12) : see declaration of 'Q' c:\Dev\Queue\Queue.cpp(13) : see reference to class template instantiation 'std::deque<_Ty>' being compiled with [ _Ty=Q ] c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\deque(60) : error C2027: use of undefined type 'Q' c:\Dev\Queue\Queue.cpp(12) : see declaration of 'Q' c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\deque(61) : error C2027: use of undefined type 'Q' c:\Dev\Queue\Queue.cpp(12) : see declaration of 'Q' c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\deque(62) : error C2027: use of undefined type 'Q' c:\Dev\Queue\Queue.cpp(12) : see declaration of 'Q'

Share this post


Link to post
Share on other sites
Oluseyi    2103
A type can not contain instances of itself. It leads to an exploded definition. Q includes a Q, which includes a Q, which includes a Q, which includes a Q, which includes...

You can store a pointer to the type, so you can also use a deque of pointers to Q. This has nothing to do with deque.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Tybon
I am having a problem with declaring a deque member variable of the same type as the class containing the member variable. If I use a different type then there is no problem. I also don't have this problem with vectors, so there must be something different about the way queue/deque are constructed. If you know what going on then please help! Thanks.


Well if you think about it for a second you have a self reference relationship, in general you cannot store instance by value until the class is fully defined so if you try to store instances of self you get into chicken & egg problem what comes first? e.g:


struct foo {

foo f;
//...
};


is impossible because foo hasn't been fully defined yet, the solution to the problem is to store a reference/pointer to foo's.

Back to your problem, its the same thing, now how STL containers work internally is implementation dependant its not going to be exactly the same for all compilers, so with your compiler the reason why it works for vector is its using pointers to Q which is correct way to handle self reference, with your compiler's deque it needs the full definition of Q.

Anyways you shouldn't relie on this it might not be the case on another implementation of STL, the correct method of handling self reference is to store pointer/reference to the type in question, note you can't store bare naked references in STL containers so you need to use (smart) pointers.

You need to change the above to :


class Q {
std::deque<Q*> Q_dq;
};

Share this post


Link to post
Share on other sites
Tybon    194
Hmm... I actually need to use a priority_queue for my data. If I have to hold pointers in my priority_queue, how are the comparisons done? Does it compare the pointers (which is not what I want) or the objects themselves?

Also, on the subject of recursive definitions, shouldn't it be okay if I declare it as a static member? It works for normal classes but not for STL containers. In the following code, containerA is an array of Q and produces compile errors because of recursive definition, containerB is a static array of Q and compiles okay, but why does containerC, which is a static deque of Q, produces compile error?



class Q
{
Q containerA[100]; // compile error
static Q containerB[100]; // no problem
static std::deque<Q> containerC; // compile error
};


Share this post


Link to post
Share on other sites
chollida1    532
I think snk_kid and Oluseyi have done a good job of explaining it but if your still a little confused think of it this way.

To create a class of type Q the compiler needs to know the size of class Q.

But if class Q has a member of type class Q it can't know its size until it knows the size of its member variable of type class Q, which can't know its size until it knows the size of class Q, and so on as Oluseyi pointed out.

Hope that helps you.

Cheers
Chris

Share this post


Link to post
Share on other sites
Fruny    1658
Oluseyi - True, but Q contains a deque<Q> which will dynamically allocate some Qs, it doesn't directly contain any Q. So he's fine.


#include <deque>

class Q;

class Q
{
std::deque<Q> q;
};

int main()
{
Q q;
}



Compiles just fine on g++ 3.4.3 at its most anal setting (-Wall -W -ansi -pedantic). In fact, it works even without the forward declaration.

Share this post


Link to post
Share on other sites
Tybon    194
Fruny -
Oh my god that exact same code will not compile on Visual Studio .NET 2003 so it must be a compiler specific problem. But the question is what does the standard specification say?


chollida1 -
I know that the compiler needs to know the size of Q, but the size is calculated from the non-static members of Q. For the following class declaration, the size of class Q is 4 bytes, assuming an int is 4 bytes.

class Q
{
int i;
static Q q;
};

My problem was with a "static" member deque of type class Q, which does not compile, while a "static" member array of type class Q compiles just fine.

<head explodes>

Share this post


Link to post
Share on other sites
MaulingMonkey    1728
Quote:
Original post by Oluseyi
A type can not contain instances of itself. It leads to an exploded definition. Q includes a Q, which includes a Q, which includes a Q, which includes a Q, which includes...

You can store a pointer to the type, so you can also use a deque of pointers to Q. This has nothing to do with deque.


However, the size() of a deque or vector dosn't have to be non-zero - this compiles and links and runs on my computer:

#include <vector>

using namespace std;

struct Q
{
vector< Q > v;
};

int main ( int argc , char ** argv )
{
Q q;
q.v.resize( 1 );
q.v[0].v.resize( 1 );
q.v[0].v[0].v.resize( 1 );
return 0;
}


It also compiles with std::deque< Q >!

Then again this is on my linux box (g++ 3.3.5)

Share this post


Link to post
Share on other sites
x_gamer_x    136
Tybon - Fruny's code does not compile for me on VS.NET 03 either.

c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\deque(62): error C2027: use of undefined type 'Q'
c:\Documents and Settings\SpicyMC\My Documents\test2\main.cpp(6) : see declaration of 'Q'

Share this post


Link to post
Share on other sites
Tybon    194
Okay then it must be Micro$oft's fault. Some how Visual Studio .Net 2003's C++ compiler has problem with the queue family of class templates. Very gay...

This compiles fine:


class V
{
static std::vector<V> v;
};



Yet, this does not compile:


class Q
{
static std::deque<Q> q;
};

Share this post


Link to post
Share on other sites
Zipster    2359
It could simply be that MSVC 2003 implements deque (and other queue classes) in such a way were you can't use a partially defined types without generating a compile error, by whatever internal rule it uses.

Oh, and Micro$oft. I've never heard that one before. The cleverness has stupefied me to the point where it isn't funny, just tired and cliché. Weird.

Share this post


Link to post
Share on other sites
daerid    354
IIRC, the standard only mentions this behavior in reference to std::vector, allowing class T to contain a std::vector of class T. The other container types are not defined, I think (which would leave them implementation dependent).

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Tybon
If I have to hold pointers in my priority_queue, how are the comparisons done? Does it compare the pointers (which is not what I want) or the objects themselves?


if you checked documentation you would see that priority_queue is also parameterized by comparator type which defaults to std::less<T> allowing you to provide a custom comparator type be it free/member function or a functor you do something like this:


struct Q_Less {
bool operator()(const Q* const a, const Q* const b) const {
return /* some comparisons */
}
};

typedef std::priority_queue< Q*, std::vector<Q*>, Q_Less > pq_of_Qs;


Quote:
Original post by Tybon
Some how Visual Studio .Net 2003's C++ compiler has problem with the queue family of class templates.


if you actually checked vc++ 2k3's deque you would see what line is giving you problems:


template< class _Ty,
class _Ax >
class deque : public _Deque_val<_Ty, _Ax> {
public:

enum { _DEQUESIZ = _DEQUESIZ_VALUE };
//..


where _DEQUESIZ_VALUE is defined to be:


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


There for the type parameter _Ty needs to be fully defined at compile-time regardless of making it class/static member or not.

Either you change what the value of _DEQUESIZ is, or you store (smart) pointers to Q, or you do template specialization for Q, or you download a different implementation of STL (something like STLport), or you try a different container.

If i was you i would go for just storing smart pointers to Q this will give you expected behaviour on all different compiler implementations of STL not just vc++ 2k3.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this