Sets and level order iteration.

[Amit]

Greetings All.

One of the usages that I need is accessing the contents of the container
that I am using in level order( which would mean breadth- first search
approach for a binary tree) as compared to the default depth-first search
approach that happens when we traverse using the default iterator for a set
or a map, when using either the less/greater comparator function object.

Would anyone know, how I can access the elements of a set or a map in a
level order? I tried specifying the comparator object that I want, but
having it sorted as well as getting what I want (level order access) is not
working out.
Further more, if I want all level order elements of that container(either
set or map) maintained via a linked list for traversing, is there an easy
way to get it done ? This would of course mean deriving a custom container
from a Set and adding another pointer that points to a peer Node. I know
there is a _Tree template class(which is a red black tree), the class
template which is used for deriving Map and Set . Maybe I can use that
directly, but I am still not sure how I can still get level order access
using that.

Thanks.

 

[Kai-Uwe Bux]

Greetings All.

One of the usages that I need is accessing the contents of the container
that I am using in level order( which would mean breadth- first search
approach for a binary tree) as compared to the default depth-first search
approach that happens when we traverse using the default iterator for a
set or a map, when using either the less/greater comparator function
object.

The standard containers are abstractions. They are designed so that
implementation details (like whether there is an underlying binary tree) do
not leak. As far as std::set is concerned, there is no depth-first or
breadth-first ordering of the element.

Would anyone know, how I can access the elements of a set or a map in a
level order? I tried specifying the comparator object that I want, but
having it sorted as well as getting what I want (level order access) is
not working out.

Even if the implementation happens to use a tree, it will be hidden from
you, private, and inaccessible.

Further more, if I want all level order elements of that container(either
set or map) maintained via a linked list for traversing, is there an easy
way to get it done ? This would of course mean deriving a custom container
from a Set and adding another pointer that points to a peer Node. I know
there is a _Tree template class(which is a red black tree), the class
template which is used for deriving Map and Set . Maybe I can use that
directly, but I am still not sure how I can still get level order access
using that.

There might be a _Tree class provided by the vendor of the standard library
that you happen to use. Using that class would, however, be highly
non-portable. You are better off running your own tree.

On a related note: if you consider using the _Tree class from your STL
implementation, keep in mind that you have no controll over the insertion
and balancing algorithm that is used. Very likely the level-order of the
elements is completely unrelated to your problem. For that reason, I
actually doubt that you really need to access the particular level-order
that just happens to be generated by that mysterious _Tree class.


Best

Kai-Uwe Bux

 

[Stephen Howe]

One of the usages that I need is accessing the contents of the container

that I am using in level order( which would mean breadth- first search
approach for a binary tree) as compared to the default depth-first search
approach that happens when we traverse using the default iterator for a
set
or a map, when using either the less/greater comparator function object.

Would anyone know, how I can access the elements of a set or a map in a
level order?

You can't. There is absolutely no guarantee that a binary tree is used, a
different data structure might be used by set/map.

I tried specifying the comparator object that I want, but
having it sorted as well as getting what I want (level order access) is
not
working out.
Further more, if I want all level order elements of that container(either
set or map) maintained via a linked list for traversing, is there an easy
way to get it done?
No.

This would of course mean deriving a custom container
from a Set and adding another pointer that points to a peer Node. I know
there is a _Tree template class(which is a red black tree), the class
template which is used for deriving Map and Set.

That is just implementation detail.
As said there is no guarantee that map/set is implemented as you say.
All that matter fro mthe point of view of standard C++ is that the container
fulfills its pre/post conditions for each operation and complexity
guarantees. You are assuiming too much in what goes on under the hood.

Stephen Howe

 

[Jeff Flinn]

Greetings All.

One of the usages that I need is accessing the contents of the container
that I am using in level order( which would mean breadth- first search
approach for a binary tree) as compared to the default depth-first search
approach that happens when we traverse using the default iterator for a
set
or a map, when using either the less/greater comparator function object.

....

What is it that your really trying to accomplish in the end. Your describing
a particular (non)solution, rather than the eventual goal. That said, as
others have responded, use a tree container. There was some recent activity
concerning tree's on the boost development mailing list. See www.boost.org.
In the short term, a tree is-a graph. So look at
http://www.boost.org/libs/graph/doc/table_of_contents.html.

Jeff Flinn