Sortable associative container?

[Matthias Käppler]

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

[Rolf Magnus]

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++.

[Andrey Tarasevich]

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

[Martin Rennix]

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

[Matthias Käppler]

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.

[Matthias Käppler]

> 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).

[Rob Williscroft]

Matthias Käppler wrote in news:co*************@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/

[20thCenturyBoy]

Matthias Käppler <no****@digitalraid.com> wrote in message news:<co*************@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