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
2  4961 
Kushal wrote in news:4b******** *************** ***@posting.goo gle.com: 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/
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_boun d (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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
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 data structure (array->hash->array). This
isn't the actual code, but should demonstrate the general idea:
foreach $bar_count(@bars) {
foreach $el_count(@els) {
$var = somefunc($bar_count,$el_count);
|
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 or 6 neighbor
points. Could anyone suggest me a data structure for it.
Thanks in advance.
John
|
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 no. of elements can change at runtime and hence it should be dynamic.
Right now i am using SortedVector , but it is very slow.
So, can u pls suggest a suitable Datastructure.
|
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 deletion.
Does anybody know of ready data structures that can be freely used
under the .Net framwork.
Thanks in Advance
|
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:
SortedList();
SortedList(const SortedList& aSortedList);
~SortedList();
| | |
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, ArrayList, or hash maps for most
of day to day work.
If there is a perticular algorithm needs to be implemented then I try
to think of trees or linked list.
|
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 time? Should the
time not be nlgn where n is the number of elements?
|
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 methods or syntax to a less experienced perl coder. I will post links to online resources you can read if necessary. Experienced perl coders might find nothing new or useful contained in this article.
Short Review
In part one I showed you some...
|
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 initialize a SortedList all at once from
sorted data?
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
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 Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| | |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
