473,394 Members | 1,478 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,394 software developers and data experts.

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 4940
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: spar | last post by:
I'm converting a Perl script to Python and have run into something I'm not sure how to do in Python. In Perl, I am running through a couple loops and inserting values directly into a complex...
5
by: John | last post by:
Hi: I'd like to implement a simple map, which is a 2-D plane with many points, e.g., 100. The points are not evenly distributed, i.e., some points may have two neighbor points; some may have 5...
10
by: Raghavendra Mahuli | last post by:
i need to store a lot of integers(say 10,000) in a datastructure. The constraints are: 1. It should be fast. 2. It should be orderded or sorted. 3.Insterting and deleting should be fast. 4. The...
22
by: Curious | last post by:
Hi, I am searching for a data structure that stores key-value pairs in it. This data structure is to hold large amounts of key-value pairs, and so needs to be efficient both in insertion and...
1
by: dtefran3 | last post by:
The problem Implement a SortedList class which stores a list of int data in ascending order. Program requirements The public interface of your class is as follows: class SortedList{ public:...
4
by: sakcee | last post by:
Hi I hope that I can learn from your experience . I want to know if you have seen a perticular problem and used a perticular data structure , and why? I usually end up using just arrays,...
7
by: desktop | last post by:
In the C++ standard page 472 it says that you can construct a std::set in linear time if the constructor gets a sorted sequence of elements. But how is this possible when insert takes logarithmic...
1
KevinADC
by: KevinADC | last post by:
Introduction In part one we discussed the default sort function. In part two we will discuss more advanced techniques you can use to sort data. Some of the techniques might introduce unfamiliar...
1
by: Harold Howe | last post by:
Howdy all, The msdn help says this about SorteList<k,v>: "If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary." My question is this: how do I...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.