• FEATURED

View more

View more

View more

$2 ### Image of the Day Submit IOTD | Top Screenshots ### The latest, straight to your Inbox. Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content. Sign up now ## Problem with deque Old topic! Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic. 15 replies to this topic ### #1Tybon Members Posted 21 January 2005 - 01:44 AM 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' ### #2Oluseyi Members Posted 21 January 2005 - 01:52 AM 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. ### #3snk_kid Members Posted 21 January 2005 - 01:58 AM Quote:  Original post by TybonI 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;}; ### #4aloknarula Members Posted 21 January 2005 - 02:01 AM Try, /////////////////////// class Q; class Q { std::deque<*Q> Q_dq; }; ///////////////////// it should work ### #5Tybon Members Posted 21 January 2005 - 06:09 AM 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}; ### #6chollida1 Members Posted 21 January 2005 - 06:42 AM 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 ### #7Fruny Moderators Posted 21 January 2005 - 07:07 AM 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. ### #8Tybon Members Posted 21 January 2005 - 07:32 AM 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> ### #9MaulingMonkey Members Posted 21 January 2005 - 08:35 AM Quote:  Original post by OluseyiA 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) ### #10Tybon Members Posted 21 January 2005 - 08:43 AM Can someone else please try with Visual Studio and see if it compiles? I need to go to bed... ### #11x_gamer_x Members Posted 21 January 2005 - 04:29 PM 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' ### #12Tybon Members Posted 21 January 2005 - 04:59 PM 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;};

### #13Zipster  Members

Posted 21 January 2005 - 05:40 PM

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.

### #14daerid  Members

Posted 21 January 2005 - 08:00 PM

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).
daerid@gmail.com

### #15snk_kid  Members

Posted 21 January 2005 - 11:03 PM

Quote:
 Original post by TybonIf 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 TybonSome 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.

### #16Tybon  Members

Posted 22 January 2005 - 12:32 AM

Thanks for the suggestions snk_kid. At least I now know why the problem is happening and have some options.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.