Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Sortable associative container?

Reply
Thread Tools

Sortable associative container?

 
 
Matthias =?ISO-8859-1?Q?K=E4ppler?=
Guest
Posts: n/a
 
      12-01-2004
Hi,

I have the following problem:
I want to store file objects in a container 8for now, it's not important how
they look like).
Now, on the one hand I need to be able to randomly pick files from the
container as fast as possible. So far I have been using std::map to store
the files, whereas the key was a unique file ID. That given, I could pick
random files from the container in O(logn).
On the other hand, I need functionality to sort the files, e.g. by date or
size. However, std::sort and std::stable_sort only seem to work on
non-associative containers. On top of that, std::map doesn't define an own
sorting operation, like std::list does.

My questions:

1) How come there's no sorting operation for std::map?

2) Which solutions are at hand? Is there such a thing as a sortable map at
all?

Thanks,
Matthias
 
Reply With Quote
 
 
 
 
Rolf Magnus
Guest
Posts: n/a
 
      12-01-2004
Matthias Käppler wrote:

> Hi,
>
> I have the following problem:
> I want to store file objects in a container 8for now, it's not important
> how they look like).
> Now, on the one hand I need to be able to randomly pick files from the
> container as fast as possible. So far I have been using std::map to store
> the files, whereas the key was a unique file ID. That given, I could pick
> random files from the container in O(logn).
> On the other hand, I need functionality to sort the files, e.g. by date or
> size. However, std::sort and std::stable_sort only seem to work on
> non-associative containers. On top of that, std::map doesn't define an own
> sorting operation, like std::list does.
>
> My questions:
>
> 1) How come there's no sorting operation for std::map?


That's because the main reason why maps are so quick at looking for a
specific key because they store the elements ordered. If you could sort a
map, the lookup wouldn't work anymore.

> 2) Which solutions are at hand? Is there such a thing as a sortable map at
> all?


No. At least not in standard C++.

 
Reply With Quote
 
 
 
 
Andrey Tarasevich
Guest
Posts: n/a
 
      12-02-2004
Matthias Kšppler wrote:
> ...
> My questions:
>
> 1) How come there's no sorting operation for std::map?


Because associative containers are kept sorted at all times. Sorting is
performed in accordance with comparator supplied at construction time.
You cannot re-sort the container in accordance with any other
comparator. This is essential to proper operation of such containers.

> 2) Which solutions are at hand? Is there such a thing as a sortable map at
> all?


You can take a "sortable" container (say, 'std::vector') and fill it
with, say, pointers to elements of your 'std::map'. Then sort it any way
you want. That would be an off-line solution.

A possible on-line solution would involve keeping the elements in
several associative containers at once, each sorted with its own
specific comparator.

Each solution has its pros and cons.

--
Best regards,
Andrey Tarasevich
 
Reply With Quote
 
Martin Rennix
Guest
Posts: n/a
 
      12-02-2004
Matthias Kšppler wrote:
> Hi,
>
> I have the following problem:
> I want to store file objects in a container 8for now, it's not

important how
> they look like).
> Now, on the one hand I need to be able to randomly pick files from

the
> container as fast as possible. So far I have been using std::map to

store
> the files, whereas the key was a unique file ID. That given, I could

pick
> random files from the container in O(logn).
> On the other hand, I need functionality to sort the files, e.g. by

date or
> size. However, std::sort and std::stable_sort only seem to work on
> non-associative containers. On top of that, std::map doesn't define

an own
> sorting operation, like std::list does.
>
> My questions:
>
> 1) How come there's no sorting operation for std::map?
>
> 2) Which solutions are at hand? Is there such a thing as a sortable

map at
> all?
>
> Thanks,
> Matthias



Check out the Boost Multi-Index Library at
http://www.boost.org/libs/multi_index/doc/index.html

It lets you define multiple "views" of data. So one view could be
sorted by filename, another sorted by date, and another by size.
--
Martin Rennix

 
Reply With Quote
 
Matthias =?ISO-8859-1?Q?K=E4ppler?=
Guest
Posts: n/a
 
      12-02-2004
Martin Rennix wrote:

> Check out the Boost Multi-Index Library at
> http://www.boost.org/libs/multi_index/doc/index.html
>
> It lets you define multiple "views" of data. So one view could be
> sorted by filename, another sorted by date, and another by size.


Haven't read through the whole tutorial yet, but it looks like this is
*exactly* what I need. Thanks Martin.
 
Reply With Quote
 
Matthias =?ISO-8859-1?Q?K=E4ppler?=
Guest
Posts: n/a
 
      12-02-2004
> http://www.boost.org/libs/multi_index/doc/index.html

Hmm, is this a very recent addition to boost? Because after reading the docs
I wanted to give it a try and when he couldn't find the header I searched
for it by hand in /usr/include and it's not there. I'm running boost 1.31.0
(Debian Sarge).
 
Reply With Quote
 
Rob Williscroft
Guest
Posts: n/a
 
      12-02-2004
Matthias Kšppler wrote in news:contnc$j97$04$(E-Mail Removed)-online.com in
comp.lang.c++:

>> http://www.boost.org/libs/multi_index/doc/index.html

>
> Hmm, is this a very recent addition to boost? Because after reading
> the docs I wanted to give it a try and when he couldn't find the
> header I searched for it by hand in /usr/include and it's not there.
> I'm running boost 1.31.0 (Debian Sarge).
>


Its in the latest release 1.32.

FYI: Boost have usenet access to there user support mailing list:

news:gmane.comp.lib.boost.user

Rob.
--
http://www.victim-prime.dsl.pipex.com/
 
Reply With Quote
 
20thCenturyBoy
Guest
Posts: n/a
 
      12-03-2004
Matthias Kšppler <(E-Mail Removed)> wrote in message news:<conbic$5qf$02$(E-Mail Removed)-online.com>...
> Martin Rennix wrote:
>
> > Check out the Boost Multi-Index Library at
> > http://www.boost.org/libs/multi_index/doc/index.html
> >
> > It lets you define multiple "views" of data. So one view could be
> > sorted by filename, another sorted by date, and another by size.

>
> Haven't read through the whole tutorial yet, but it looks like this is
> *exactly* what I need. Thanks Martin.


No worries. Check out the rest of Boost while you're there, it's a
veritable treasure chest of goodies.

--
Martin Rennix
 
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
Why "associative" in associative container? desktop C++ 5 06-26-2007 07:49 AM
Multiple sortable headers(linkbuttons) per column? tonicvodka ASP .Net 0 01-18-2006 12:07 PM
Sortable/pagable datagrid with hyperlink column =?Utf-8?B?VFBoZWxwcw==?= ASP .Net 3 01-03-2006 09:21 AM
DataGrid header style inconsistent with sortable column style cedoucette@alum.rpi.edu ASP .Net 0 10-14-2005 12:13 AM
Setting CSSClass for Datagrid header's for sortable fields =?Utf-8?B?RGlmZmlkZW50?= ASP .Net 2 12-23-2004 07:25 AM



Advertisments