Sign in to follow this  

STL list question

This topic is 4842 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

Just out of curiosity, why is this valid with vectors but not lists?
//No compile errors
class node {
  int value;
  vector<node> children;
};

//error C2079: '_Value' uses undefined class 'node'
class node {
  int value;
  list<node> children;
};

Share this post


Link to post
Share on other sites
It looks as though in that implementation the list contains an actual object of the templated type rather than a pointer to an object of that type. This means it needs to know the size of the type and not just the name of the type. So it needs the full implentation. This is quite normal (but not necessary).

vectors are pretty much going to be wrappers around a c-style array. So the vector only needs to know the name of the type rather than having the full definition available at the time of being declared.

If you want to store a list in the way you have it you could do

class node {
int value;
list<node*> children;
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Fourty_Two
Just out of curiosity, why is this valid with vectors but not lists?


Out of luck (i'm being serious!) you have a circular def dependence (meaning you have an chicken & egg story going on). This depends on the implementation but vector is normally implementated in terms of pointers to nodes in your case which is the correct method of handling circular dependencies so essentially you can imagine it generating:


class vector {
/* ... omitted stuff .. */
node* _v;
/* ... omitted stuff ... */
};


where as list is implementated with a doublely-linked list which is different from a dynamically array, list nodes are conceptually implementated like so:


template < typename T >
list_node {

list_node<T>* pred, succ;
T _elem;
};


so when you use list like you have there your having chicken & egg syndrome, if you have self-reference dependency you have to use a pointer to the type in question.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fourty_Two
That makes sense. I take it the list object wouldn't call delete on its elements when it is deleted though. Am I correct?


negative list elements are list nodes which are dynamically allocated & deleted for you it just doesn't delete the typed contained directly it does it indirectly when it explicitly deletes a list node.

If you have any self references in a type you have to either use reference or pointer to the type in question to avoid chicken & egg problem (which came first the chicken or the egg? the compiler doesn't know thats for sure lol).

EDIT: if you store pointers any dynamically allocated memory there refer to its your responsibility to delete them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fourty_Two
That makes sense. I take it the list object wouldn't call delete on its elements when it is deleted though. Am I correct?


right, you'd have to put something in the destructor to run through the list calling delete on them all. Using the STL you could do:


//utility.h
namespace utility {
template<typename T>
void destroy(T*& obj) {
delete obj;
obj = 0;
}
}




//node.h
#include <algorithm>
#include "utility.h"

node::~node() {
std::for_each(list.begin(), list.end(), utility::destroy);
}


Share this post


Link to post
Share on other sites

This topic is 4842 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.

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