order in map

Discussion in 'C++' started by John, Jan 3, 2007.

  1. John

    John Guest

    Is there a way to implement order in map. What I mean is a function
    called
    Order(i) which outputs the i-th iterator in the sorted order. In
    theory, such
    a computation can be done in O(log n) time. In practice, I dont see how
    to
    implement it easily on a std::map.

    Thanks,
    --j


    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    John, Jan 3, 2007
    #1
    1. Advertising

  2. On 2007-01-03 15:01, John wrote:
    > Is there a way to implement order in map. What I mean is a function
    > called Order(i) which outputs the i-th iterator in the sorted order.
    > In theory, such a computation can be done in O(log n) time. In
    > practice, I dont see how to implement it easily on a std::map.


    It can be done in O(i)-time:

    template<class T>
    typename T::const_iterator Order(const T& m, size_t i)
    {
    T::const_iterator it = m.begin();
    for (size_t j = 0; j < i; ++j)
    ++it;
    return it;
    }

    I don't think that you can get better than that without getting
    platform-specific, see my other reply for more information about why.

    --
    Erik Wikström

    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Jan 3, 2007
    #2
    1. Advertising

  3. John

    Salt_Peter Guest

    John wrote:
    > Is there a way to implement order in map.


    Clarify your question, there is no such thing as an unordered std::map.
    You can supply whatever predicate you choose if std::less<> doesn't
    order the keys as required.
    Typically, these are implemented using a red-black tree.

    > What I mean is a function
    > called
    > Order(i) which outputs the i-th iterator in the sorted order. In
    > theory, such
    > a computation can be done in O(log n) time. In practice, I dont see how
    > to
    > implement it easily on a std::map.
    >
    > Thanks,
    > --j
    >
    >



    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Salt_Peter, Jan 3, 2007
    #3
  4. John

    Stephen Howe Guest

    > Is there a way to implement order in map. What I mean is a function
    > called
    > Order(i) which outputs the i-th iterator in the sorted order. In
    > theory, such
    > a computation can be done in O(log n) time.


    Can it? If map's were implemented as binary trees, and each node carried
    information as to how many left and right nodes were attached, then yes it
    could. But that is immense overhead to carry, _just_ to do this. It would
    mean that every insert, every erase would have to updated the counters.

    The other alternative is to 'walk' the map which gives a O(n) time to find
    Order node.

    Another possibility is to use a a sorted vector or deque instead of a map
    and in that case it is trivial to convert the ith-entry back to an iterator.

    Stephen Howe



    --
    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Stephen Howe, Jan 4, 2007
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Soren Kuula
    Replies:
    2
    Views:
    498
    Soren Kuula
    Feb 1, 2004
  2. He Shiming
    Replies:
    8
    Views:
    4,824
    Stephen Howe
    Jan 3, 2005
  3. Mosfet
    Replies:
    6
    Views:
    4,897
  4. cspoh
    Replies:
    0
    Views:
    245
    cspoh
    Jul 31, 2003
  5. Stephan Kämper
    Replies:
    2
    Views:
    232
    Stephan Kämper
    Jan 18, 2004
Loading...

Share This Page