Vector of lists?

[Amit Bhatia]

Hi,
I have the following question:

I make a list whose elements are instances of class B;
list<class B>;

Now I wish to make a vector of such lists:

vector<list<class B> > v;

Is this operation valid?

thanks,
--a.


--

 

[Thomas Tutone]

I make a list whose elements are instances of class B;
list<class B>;

Now I wish to make a vector of such lists:

vector<list<class B> > v;

Is this operation valid?

Yes, but your syntax is slightly off.

If you have a class B:

class B {};

then a list of that class would be:

std::list<B> theList;

and a vector of such lists would be:

std::vector<std::list<B> > v;

Best regards,

Tom

 

[Eric Pruneau]

Hi,
I have the following question:

I make a list whose elements are instances of class B;
list<class B>;

Now I wish to make a vector of such lists:

vector<list<class B> > v;

Is this operation valid?

thanks,
--a.

 

[Eric Pruneau]

Hi,
I have the following question:

I make a list whose elements are instances of class B;
list<class B>;

Now I wish to make a vector of such lists:

vector<list<class B> > v;

Is this operation valid?

yes

as long as you dont type
vector<list<class B>> v; // should be > > not >>

moreover, elements in a vector must be default constructible
and list has a default constructor.

So you cannot have a vector of Widget if Widget is like :

class Widget
{
Widget() {} // default ctor is private
};

so
vector<Widget> vec(100);
will not compile

Eric

 

[Jerry Coffin]

[ ... ]

So you cannot have a vector of Widget if Widget is like :

class Widget
{
Widget() {} // default ctor is private
};

so
vector<Widget> vec(100);
will not compile

That won't compile, but you CAN still create a vector of items that
aren't default constructible. In this case, you have to supply an object
of the correct type that's used to initialize the objects in the vector.
Since the initializing object isn't the first parameter, you also have
to supply an initial size for the vector:

class Widget {
int x_;
Widget() {} // default ctor is still private
public:
Widget(int x) x_(x) {} // requires a parameter
};

// A vector of 100 Widgets, each initialized to 200:
std::vector<Widget> vw(100, Widget(200));

 

[Amit Bhatia]

Thanks.
but this brings me to one more question: I guess the elements of a list
"should" also be default constructible? I want to make a tree of nodes as follows, but am not sure now if it
will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible. vector< Node & > child_nodes; //Could use pointer here but want to
avoid it if possible.};

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;
};


I don't want to create duplicate copies of nodes, and want everything to
point correctly to elements in the global list treeofnodes.
any suggestions?

thanks,
--a.

yes

as long as you dont type
vector<list<class B>> v; // should be > > not >>

moreover, elements in a vector must be default constructible
and list has a default constructor.

So you cannot have a vector of Widget if Widget is like :

class Widget
{
Widget() {} // default ctor is private
};

so
vector<Widget> vec(100);
will not compile

Eric

--

 

[Eric Pruneau]

Thanks.
but this brings me to one more question: I guess the elements of a list
"should" also be default constructible?

yes, or you have to allocate with initialization

I want to make a tree of nodes as follows, but am not sure now if it

will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible.
vector< Node & > child_nodes; //Could use pointer here but want to
avoid it if possible.};

No no no... cannot do a vector of references. This is illegal
you must use pointers here.

Are you sure you want to use vector here...
If you have to do a lot of insertion/removal list is probably the
structure you want.

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;

Samething here with list.. must use pointers.
I dont see why you are using a list here and a vector in
your node class

};


I don't want to create duplicate copies of nodes, and want everything to
point correctly to elements in the global list treeofnodes.
any suggestions?

Well if you want a basic implementation of a tree, you seems to be on the
right track. just have a tree class with a list of Node. And Node having
also
a list of Node. Now do you needs your Nodes to be dynamically allocated?

something like

class Tree
{
public:
[...] ctor dtor
[...] // probably want to give access to some functions to search or sort
your tree
private:
Node m_Root;
list<Node> m_Childs;
};

class Node
{
public:
[...] ctor dtor
private:
[...] info about the node
list<Node> m_Childs;
// Do you really need a reference to the parent??? maybe not...
};

 

[Amit Bhatia]

Thanks.
but this brings me to one more question: I guess the elements of a list
"should" also be default constructible?

yes, or you have to allocate with initialization

I want to make a tree of nodes as follows, but am not sure now if it

will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible.
vector< Node & > child_nodes; //Could use pointer here but want to
avoid it if possible.};

No no no... cannot do a vector of references. This is illegal
you must use pointers here.

Are you sure you want to use vector here...
If you have to do a lot of insertion/removal list is probably the
structure you want.

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;

Samething here with list.. must use pointers.
I dont see why you are using a list here and a vector in
your node class

};


I don't want to create duplicate copies of nodes, and want everything to
point correctly to elements in the global list treeofnodes.
any suggestions?

Well if you want a basic implementation of a tree, you seems to be on the
right track. just have a tree class with a list of Node. And Node having
also
a list of Node. Now do you needs your Nodes to be dynamically allocated?

something like

class Tree
{
public:
[...] ctor dtor
[...] // probably want to give access to some functions to search or sort
your tree
private:
Node m_Root;
list<Node> m_Childs;
};

class Node
{
public:
[...] ctor dtor
private:
[...] info about the node
list<Node> m_Childs;
// Do you really need a reference to the parent??? maybe not...
};

Thanks. Yes I do need quick access to the parent. In your suggestion,
there is something like

list<Node> m_childs;

But won't this result in duplicate copies: one in node and one in tree?
I want to avoid that. The feature that I wish to have is to be able to remove a particular
child node whenever I want, and also free up that space from the tree. If
I use pointers, and I have a list of pointer
class Tree{
//; ;
list<Node * > m_Childs;
};

but when I free memory from a particular pointer, can I ensure somehow
that that pointer entry is also removed from the list? I guess I could do
it if I could use iterators as
class Node{

//; ;
vector<list<Node>::iterator > m_Childs;
};

and then
class Tree{
//; ;
list<Node> tree;
};

but just using pointers ? btw, I wanted to use vector in nodes as I will
be needing random access, and when I do have to delete the children, I
will probably be requiring to delete all of them in one go.
thanks,
--a.

 

[Eric Pruneau]

Thanks. Yes I do need quick access to the parent. In your suggestion,
there is something like

list<Node> m_childs;

But won't this result in duplicate copies: one in node and one in tree?

humm no.
the tree is just like a node (except it doesnt have a parent).
The tree contain a list of his (immediate) children, not the list of all
node in the tree.
Each of tree's child ( a node) contain a list of his children ( a list of
nodes) and so on.

So there is only one node created for each elements of your tree.

Also, you can use either reference or pointer for keeping track of
the parent of a node.

Eric