Containers of iterators vs. containers of references

[clark.coleman]

Relatively new to STL use. I coded up a bunch of container code with
lots of iterators. Now I question whether I want to have so much
nested iterator syntax.

For example, if you are coding a compiler and you have classes such as
BasicBlock. Each basic block has predecessors and successors in the
control flow graph. Right now, I am storing these as iterators:

list<list<BasicBlock>::iterator> Predecessors;
list<list<BasicBlock>::iterator> Successors;

This leads to messy looking code. I have a GetFirstPred() method that
now returns something of type:

list<list<BasicBlock>::iterator>::iterator

and likewise a GetLastPred() method that does the same. Now, when I
want to iterate through all predecessors of a block, I have a loop
with all kinds of dereferencing of iterators:

list<list<BasicBlock>::iterator>::iterator CurrPred;
for (CurrPred = this->GetFirstPred(); CurrPred != this->GetLastPred();
++CurrPred) {

if ((*CurrPred)->IsJoinPoint()) .... etc.
}

Should this all be list of references instead of list of iterators for
simplicity?

list<BasicBlock &> Predecessors;

Thanks for any recommendations.

 

[Ian Collins]

Relatively new to STL use. I coded up a bunch of container code with
lots of iterators. Now I question whether I want to have so much
nested iterator syntax.

For example, if you are coding a compiler and you have classes such as
BasicBlock. Each basic block has predecessors and successors in the
control flow graph. Right now, I am storing these as iterators:

list<list<BasicBlock>::iterator> Predecessors;
list<list<BasicBlock>::iterator> Successors;

This leads to messy looking code. I have a GetFirstPred() method that
now returns something of type:

list<list<BasicBlock>::iterator>::iterator

Hide the complexity behind typedefs.

Should this all be list of references instead of list of iterators for
simplicity?

list<BasicBlock &> Predecessors;

You can't have containers of references.

 

[James Kanze]

Relatively new to STL use. I coded up a bunch of container code with
lots of iterators. Now I question whether I want to have so much
nested iterator syntax.

For example, if you are coding a compiler and you have classes such as
BasicBlock. Each basic block has predecessors and successors in the
control flow graph. Right now, I am storing these as iterators:

list<list<BasicBlock>::iterator> Predecessors;
list<list<BasicBlock>::iterator> Successors;

Why? I'd just use pointers. (Although list is somewhat of an
exception, in general, iterators are just too fragile to be of
much use except for immediately looping.)

This leads to messy looking code. I have a GetFirstPred()
method that now returns something of type:

list<list<BasicBlock>::iterator>::iterator

Typedef's would help, don't you think? Something like:

typedef std::list< BasicBlock* >::iterator
PredecessorIter ;

(FWIW: I'd probably use an std::vector here, rather than
std::list.)

[...]

Should this all be list of references instead of list of iterators for
simplicity?

list<BasicBlock &> Predecessors;

You can't have a container of references; references aren't
objects. I would use a container of pointers, however.

 

[clark.coleman]

You can't have a container of references; references aren't
objects. I would use a container of pointers, however.

Any recommendations for type of pointer? I started playing with
shared_ptr but then I discovered that Visual Studio does not yet
support C++ TR1. I need the code to run on both x86/Linux under g++
and Visual Studio.

 

[Jeff F]

Any recommendations for type of pointer? I started playing with
shared_ptr but then I discovered that Visual Studio does not yet
support C++ TR1. I need the code to run on both x86/Linux under g++
and Visual Studio.

Use the shared_ptr from www.boost.org, which is the basis for TR1, and
supports both of those compilers along with many others.

Better yet see the boost graph library which more directly supports your
application.

Jeff Flinn

 

[James Kanze]

Any recommendations for type of pointer?

A pointer to whatever type you wanted the reference to.

I started playing with shared_ptr but then I discovered that
Visual Studio does not yet support C++ TR1. I need the code to
run on both x86/Linux under g++ and Visual Studio.

I wouldn't bother with shared_ptr except in some special cases.
I find it fairly rare that a container should control the
lifetime of an object that isn't copiable (and if the object is
copiable, of course, the vector will contain objects, and not
pointers or references)---most of the time, objects which aren't
copiable are entity objects which control their own lifetime.
(One exception might be a container of polymorphic agents. In
such cases, I'll usually use an invasive reference counter in
the base class.)

If you do want shared_ptr, of course, you can get it from boost.
I'm pretty sure that recent versions of both g++ and VC++ can
handle Boost.

 

[James Kanze]

Use the shared_ptr fromwww.boost.org, which is the basis for
TR1, and supports both of those compilers along with many
others.

Better yet see the boost graph library which more directly
supports your application.

Looking at his application: he certainly doesn't want
shared_ptr, since there will be cycles---and in this case, using
weak_ptr to break them will be fairly complicated. I'm not
familiar with the Boost graph library, to know whether it's
appropriate, but if not, raw pointers would seem to be the way
to go.

 

[Pete Becker]

Any recommendations for type of pointer? I started playing with
shared_ptr but then I discovered that Visual Studio does not yet
support C++ TR1. I need the code to run on both x86/Linux under g++
and Visual Studio.

VC++ 2008 has support for TR1 (excluding C99 and special math
functions) in their "Feature Pack".