Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > order in map

Reply
Thread Tools

order in map

 
 
John
Guest
Posts: n/a
 
      01-03-2007

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

 
Reply With Quote
 
 
 
 
=?ISO-8859-1?Q?Erik_Wikstr=F6m?=
Guest
Posts: n/a
 
      01-03-2007
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! ]

 
Reply With Quote
 
 
 
 
Salt_Peter
Guest
Posts: n/a
 
      01-03-2007

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

 
Reply With Quote
 
Stephen Howe
Guest
Posts: n/a
 
      01-04-2007
> 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! ]

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
If you get an order # does it mean the order is accepted? =?Utf-8?B?U3RldmUxMDc3?= Windows 64bit 3 05-12-2005 11:46 PM
map<wstring, set<wstring> > preserving insertion order? He Shiming C++ 8 01-03-2005 06:42 AM
Traversion order cf. output order in XSL Soren Kuula XML 2 02-01-2004 09:10 AM
In which order are files looked for when loaded/requierd - and what'sthe order of suffixes? Stephan Kämper Ruby 2 01-18-2004 02:07 PM
How to Display DropDownList with preserved order (custom order) cspoh ASP .Net Web Controls 0 07-31-2003 09:19 AM



Advertisments