By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,132 Members | 1,265 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,132 IT Pros & Developers. It's quick & easy.

order in map

P: n/a

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

Jan 3 '07 #1
Share this Question
Share on Google+
3 Replies


P: n/a
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! ]

Jan 3 '07 #2

P: n/a

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

Jan 3 '07 #3

P: n/a
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! ]

Jan 4 '07 #4

This discussion thread is closed

Replies have been disabled for this discussion.