Sets and level order iteration.

Discussion in 'C++' started by Amit, May 19, 2005.

  1. Amit

    Amit Guest

    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.

    Amit, May 19, 2005
    1. Advertisements

  2. Amit

    Kai-Uwe Bux Guest

    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.
    Even if the implementation happens to use a tree, it will be hidden from
    you, private, and inaccessible.
    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.


    Kai-Uwe Bux
    Kai-Uwe Bux, May 19, 2005
    1. Advertisements

  3. Amit

    Stephen Howe Guest

    One of the usages that I need is accessing the contents of the container
    You can't. There is absolutely no guarantee that a binary tree is used, a
    different data structure might be used by set/map.
    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
    Stephen Howe, May 19, 2005
  4. Amit

    Jeff Flinn Guest


    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
    In the short term, a tree is-a graph. So look at

    Jeff Flinn
    Jeff Flinn, May 19, 2005
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.