STL Data Structures, Sorted Insertion?

K

Kushal

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
 
R

Rob Williscroft

Kushal wrote in
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.
 
T

tom_usenet

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top