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