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.

    Thanks.
     
    Amit, May 19, 2005
    #1
    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.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, May 19, 2005
    #2
    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
    #3
  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 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
     
    Jeff Flinn, May 19, 2005
    #4
    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.