«

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

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

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

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

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.

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

Matthias Käppler wrote in news:contnc$j97$04$ 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/

Matthias Käppler <> wrote in message news:<conbic$5qf$02$>...
> 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