order in map

[John]

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! ]

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

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! ]

[Salt_Peter]

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! ]

[Stephen Howe]

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! ]