By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,669 Members | 1,654 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,669 IT Pros & Developers. It's quick & easy.

Sets and level order iteration.

P: n/a
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.
Jul 23 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Amit wrote:
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
Jul 23 '05 #2

P: n/a
> 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
Jul 23 '05 #3

P: n/a

"Amit" <am***********@intel.com> wrote in message
news:d6**********@news01.intel.com...
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/..._contents.html.

Jeff Flinn
Jul 23 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.