469,356 Members | 2,656 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,356 developers. It's quick & easy.

STL Data Structures, Sorted Insertion?

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
Jul 22 '05 #1
2 4763
Kushal wrote in news:4b**************************@posting.google.c 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/
Jul 22 '05 #2
On 30 Jan 2004 07:45:01 -0800, ku************@hotmail.com (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
Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by spar | last post: by
5 posts views Thread by John | last post: by
10 posts views Thread by Raghavendra Mahuli | last post: by
22 posts views Thread by Curious | last post: by
4 posts views Thread by sakcee | last post: by
7 posts views Thread by desktop | last post: by
1 post views Thread by Marylou17 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.