Sortable associative container?

Discussion in 'C++' started by Matthias =?ISO-8859-1?Q?K=E4ppler?=, Dec 1, 2004.

  1. 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 =?ISO-8859-1?Q?K=E4ppler?=, Dec 1, 2004
    #1
    1. Advertising

  2. Matthias =?ISO-8859-1?Q?K=E4ppler?=

    Rolf Magnus Guest

    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++.
     
    Rolf Magnus, Dec 1, 2004
    #2
    1. Advertising

  3. 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
     
    Andrey Tarasevich, Dec 2, 2004
    #3
  4. 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, Dec 2, 2004
    #4
  5. 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 =?ISO-8859-1?Q?K=E4ppler?=, Dec 2, 2004
    #5
  6. > 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 =?ISO-8859-1?Q?K=E4ppler?=, Dec 2, 2004
    #6
  7. Matthias Käppler wrote in news:contnc$j97$04$-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/
     
    Rob Williscroft, Dec 2, 2004
    #7
  8. Matthias Käppler <> wrote in message news:<conbic$5qf$02$-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
     
    20thCenturyBoy, Dec 3, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?RGlmZmlkZW50?=

    Setting CSSClass for Datagrid header's for sortable fields

    =?Utf-8?B?RGlmZmlkZW50?=, Dec 22, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    1,630
    =?Utf-8?B?QmlsbCBCb3Jn?=
    Dec 23, 2004
  2. T.Meitz

    associative container

    T.Meitz, Feb 16, 2004, in forum: C++
    Replies:
    2
    Views:
    385
    T.Meitz
    Feb 17, 2004
  3. aaragon
    Replies:
    21
    Views:
    699
    Diego Martins
    Oct 17, 2006
  4. desktop
    Replies:
    5
    Views:
    404
    James Kanze
    Jun 26, 2007
  5. jacob navia

    An associative container

    jacob navia, Nov 17, 2009, in forum: C Programming
    Replies:
    21
    Views:
    682
    Phil Carmody
    Nov 21, 2009
Loading...

Share This Page