STL Data Structures, Sorted Insertion?

Discussion in 'C++' started by Kushal, Jan 30, 2004.

  1. Kushal

    Kushal Guest

    Hello,

    I am trying to build a dynamic set/list of data which should be sorted
    as each element is inserted. The main criteria in this list is the
    speed, the time it takes to insert a element, and the time it takes to
    retrive it. Therefore I was wondering between STL Vectors, Maps, and
    Set, what would be the most efficient way to do this, and how can it
    be done easily.

    Also, if I were to use STL Vectors, is there anyway that I can get the
    desired functionality of sorting on insertion, with efficiency.

    Thanks,

    Kushal
     
    Kushal, Jan 30, 2004
    #1
    1. Advertising

  2. Kushal wrote in news::

    > Hello,
    >
    > I am trying to build a dynamic set/list of data which should be sorted
    > as each element is inserted. The main criteria in this list is the
    > speed, the time it takes to insert a element, and the time it takes to
    > retrive it.


    Unfortunatly you "main criteria" it 2 criteria you should realy decide
    which is most important.

    > Therefore I was wondering between STL Vectors, Maps, and
    > Set, what would be the most efficient way to do this, and how can it
    > be done easily.


    The only real difference between a map and a set is wether you
    want to store a single object/key (std::set) ar a key an a value
    (std::map) otherwise they have identical insert and search capabilities.

    >
    > Also, if I were to use STL Vectors, is there anyway that I can get the
    > desired functionality of sorting on insertion, with efficiency.
    >


    Yup, but you have to do a binary search on the vector which has
    the same complexity as set/map's insert, so you gain nothing,
    additionally you have to copy elements that have already been
    inserted "out of the way", so you end up with something worse
    than using set/map.

    HTH.

    Rob.
    --
    http://www.victim-prime.dsl.pipex.com/
     
    Rob Williscroft, Jan 30, 2004
    #2
    1. Advertising

  3. Kushal

    tom_usenet Guest

    On 30 Jan 2004 07:45:01 -0800, (Kushal)
    wrote:

    >Hello,
    >
    >I am trying to build a dynamic set/list of data which should be sorted
    >as each element is inserted. The main criteria in this list is the
    >speed, the time it takes to insert a element, and the time it takes to
    >retrive it. Therefore I was wondering between STL Vectors, Maps, and
    >Set, what would be the most efficient way to do this, and how can it
    >be done easily.


    std::set is tailor made for this. It is likely to be the most
    efficient container when insertions are common, although lookup speed
    is slower than for vector.

    >
    >Also, if I were to use STL Vectors, is there anyway that I can get the
    >desired functionality of sorting on insertion, with efficiency.


    Not with much efficiency, no. You can find the place to insert using
    std::lower_bound (O(log n)), but then inserting the element is (O(n))
    in assignments or similar.

    You could have a vector to store the elements in in insertion order,
    and then a vector of indices into that vector that you keep in the
    sort order. That's a possibility if your elements are expensive to
    copy.

    Tom

    C++ FAQ: http://www.parashift.com/c -faq-lite/
    C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
     
    tom_usenet, Jan 30, 2004
    #3
    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. Alfonso Morra
    Replies:
    11
    Views:
    755
    Emmanuel Delahaye
    Sep 24, 2005
  2. chai

    Insertion to a sorted list

    chai, Oct 7, 2005, in forum: C Programming
    Replies:
    3
    Views:
    558
  3. Franco Perilli

    Big problem doing sorted insertion in a list

    Franco Perilli, Jul 14, 2006, in forum: C Programming
    Replies:
    3
    Views:
    331
    Franco Perilli
    Jul 15, 2006
  4. Generic Usenet Account

    STL :: Set operations on sorted structures

    Generic Usenet Account, Nov 23, 2005, in forum: C++
    Replies:
    8
    Views:
    349
    Generic Usenet Account
    Dec 7, 2005
  5. Replies:
    1
    Views:
    736
    Harold Aptroot
    Jul 16, 2008
Loading...

Share This Page