Jump to content
  • Advertisement
Sign in to follow this  
Tybon

Problem with deque

This topic is 5079 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
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
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
Can someone else please try with Visual Studio and see if it compiles?

I need to go to bed...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!