Jump to content

View more

Image of the Day

Full Syncs #screenshotsaturday favourites https://t.co/i1Flnwcg3l #xbox #ps4 https://t.co/m0v2F1SxGs
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

2: Adsense

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.


  • You cannot reply to this topic
15 replies to this topic

#1 Tybon   Members   

194
Like
0Likes
Like

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'

#2 Oluseyi   Members   

2076
Like
0Likes
Like

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.

#3 snk_kid   Members   

1312
Like
0Likes
Like

Posted 21 January 2005 - 01:58 AM

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;
};


#4 aloknarula   Members   

122
Like
0Likes
Like

Posted 21 January 2005 - 02:01 AM

Try,
///////////////////////
class Q;

class Q
{
std::deque<*Q> Q_dq;
};
/////////////////////
it should work


#5 Tybon   Members   

194
Like
0Likes
Like

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
};




#6 chollida1   Members   

532
Like
0Likes
Like

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

#7 Fruny   Moderators   

1654
Like
0Likes
Like

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.

#8 Tybon   Members   

194
Like
0Likes
Like

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>


#9 MaulingMonkey   Members   

1684
Like
0Likes
Like

Posted 21 January 2005 - 08:35 AM

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)

#10 Tybon   Members   

194
Like
0Likes
Like

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...

#11 x_gamer_x   Members   

136
Like
0Likes
Like

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'



#12 Tybon   Members   

194
Like
0Likes
Like

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;
};



#13 Zipster   Members   

2207
Like
0Likes
Like

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.

#14 daerid   Members   

354
Like
0Likes
Like

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

#15 snk_kid   Members   

1312
Like
0Likes
Like

Posted 21 January 2005 - 11:03 PM

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.

#16 Tybon   Members   

194
Like
0Likes
Like

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.