Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL Data Structures, Sorted Insertion?

Reply
Thread Tools

STL Data Structures, Sorted Insertion?

 
 
Kushal
Guest
Posts: n/a
 
      01-30-2004
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
 
Reply With Quote
 
 
 
 
Rob Williscroft
Guest
Posts: n/a
 
      01-30-2004
Kushal wrote in news:(E-Mail Removed) om:

> 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/
 
Reply With Quote
 
 
 
 
tom_usenet
Guest
Posts: n/a
 
      01-30-2004
On 30 Jan 2004 07:45:01 -0800, http://www.velocityreviews.com/forums/(E-Mail Removed) (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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
STL container for sorted items Hunk C++ 18 03-29-2007 04:01 AM
STL set members sorted? chenboston@gmail.com C++ 1 03-17-2006 05:22 PM
STL :: Set operations on sorted structures Generic Usenet Account C++ 8 12-07-2005 03:26 AM
Data/File Structure and Algorithm for Retrieving Sorted Data Chunk Efficiently Jane Austine Python 14 10-09-2004 05:54 PM
STL and sorted list Der Andere C++ 10 06-03-2004 06:35 AM



Advertisments