| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Matthias =?ISO-8859-1?Q?K=E4ppler?=" |
| Date: |
01 Dec 2004 02:41:13 PM |
| Object: |
Sortable associative container? |
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
.
|
|
| User: "Martin Rennix" |
|
| Title: Re: Sortable associative container? |
01 Dec 2004 11:42:14 PM |
|
|
Matthias K=E4ppler 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.
--=20
Martin Rennix
.
|
|
|
| User: "Matthias =?ISO-8859-1?Q?K=E4ppler?=" |
|
| Title: Re: Sortable associative container? |
02 Dec 2004 02:26:18 PM |
|
|
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).
.
|
|
|
| User: "Rob Williscroft" |
|
| Title: Re: Sortable associative container? |
02 Dec 2004 02:48:33 PM |
|
|
Matthias Käppler wrote in news:contnc$j97$04$1@news.t-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/
.
|
|
|
|
|
| User: "Matthias =?ISO-8859-1?Q?K=E4ppler?=" |
|
| Title: Re: Sortable associative container? |
02 Dec 2004 09:16:25 AM |
|
|
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.
.
|
|
|
| User: "20thCenturyBoy" |
|
| Title: Re: Sortable associative container? |
02 Dec 2004 07:12:47 PM |
|
|
Matthias Käppler <nospam@digitalraid.com> wrote in message news:<conbic$5qf$02$1@news.t-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
.
|
|
|
|
|
|
| User: "Rolf Magnus" |
|
| Title: Re: Sortable associative container? |
01 Dec 2004 02:59:55 PM |
|
|
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++.
.
|
|
|
|
| User: "Andrey Tarasevich" |
|
| Title: Re: Sortable associative container? |
01 Dec 2004 06:43:02 PM |
|
|
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
.
|
|
|
|
|
Related Articles |
|
|
