473,231 Members | 1,790 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,231 software developers and data experts.

std::set and insert speed

I have a program that reads sorted data from a database and inserts it
element by element into a set.

If the data is sorted is there a faster way to insert ? Meaning is
there a way to tell the std::set to check the end of the tree before
doing the insert as a fast check on where the key is going to end up ?

Thanks.

Jul 7 '06 #1
5 5772
asdf wrote:
I have a program that reads sorted data from a database and inserts it
element by element into a set.

If the data is sorted is there a faster way to insert ? Meaning is
there a way to tell the std::set to check the end of the tree before
doing the insert as a fast check on where the key is going to end up ?
RTFM. There is more than one 'insert' function. Also see the return
values of those 'insert' members.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jul 7 '06 #2
In article <11**********************@s13g2000cwa.googlegroups .com>,
qj*********@yahoo.com says...
I have a program that reads sorted data from a database and inserts it
element by element into a set.

If the data is sorted is there a faster way to insert ? Meaning is
there a way to tell the std::set to check the end of the tree before
doing the insert as a fast check on where the key is going to end up ?
Yes, you can use the version of insert that allows you to pass a
"hint" about where the insertion is likely to take place.

Given that you're starting with sorted data, you might consider
putting it into a vector, and using a binary search. You can then
supplement that (if necessary) with a set to hold newly-inserted
data. Since it uses contiguous memory, searching a vector is nearly
always substantially faster than searching a set. The shortcoming, of
course, is insertions (and deletions, if you insist on really
deleting data instead of just marking a location as empty).

Combining the two makes it fairly easy to get most of the good points
of each: you get faster searching because most data is in the vector,
but also fast inserts because you insert new data into the set.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 7 '06 #3
Victor Bazarov wrote:
asdf wrote:
>I have a program that reads sorted data from a database and inserts it
element by element into a set.

If the data is sorted is there a faster way to insert ? Meaning is
there a way to tell the std::set to check the end of the tree before
doing the insert as a fast check on where the key is going to end up ?

RTFM. There is more than one 'insert' function. Also see the return
values of those 'insert' members.
For building a set from sorted data you would not need the insert return
value just use end() (or begin() resp.) as hint.

Jul 7 '06 #4

Jerry Coffin wrote:
In article <11**********************@s13g2000cwa.googlegroups .com>,
qj*********@yahoo.com says...
I have a program that reads sorted data from a database and inserts it
element by element into a set.

If the data is sorted is there a faster way to insert ? Meaning is
there a way to tell the std::set to check the end of the tree before
doing the insert as a fast check on where the key is going to end up ?

Yes, you can use the version of insert that allows you to pass a
"hint" about where the insertion is likely to take place.
Thanks ! Just wondering - if the data happens not to be sorted and the
hint is pretty much useless what is the performance hit going to be
like ? I think it should still be comparable to without using the hint
- likely just a little slower. Eg what does the algorithm do when it
sees the hint ?
Given that you're starting with sorted data, you might consider
putting it into a vector, and using a binary search. You can then
supplement that (if necessary) with a set to hold newly-inserted
data. Since it uses contiguous memory, searching a vector is nearly
always substantially faster than searching a set. The shortcoming, of
course, is insertions (and deletions, if you insist on really
deleting data instead of just marking a location as empty).

Combining the two makes it fairly easy to get most of the good points
of each: you get faster searching because most data is in the vector,
but also fast inserts because you insert new data into the set.
Sounds good ! I will keep this in mind.

Jul 7 '06 #5
In article <11**********************@h48g2000cwc.googlegroups .com>,
qj*********@yahoo.com says...

[ ... ]
Thanks ! Just wondering - if the data happens not to be sorted and the
hint is pretty much useless what is the performance hit going to be
like ? I think it should still be comparable to without using the hint
- likely just a little slower. Eg what does the algorithm do when it
sees the hint ?
Right -- basically it normally just checks whether the hint is
correct. If it is, it can insert there in roughly constant time. If
not, you've lost that time to do the check, and then it does the
insert as if there was no hint. IOW, a fairly substantial gain when
it's right, but a pretty minimal penalty when it's wrong.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 8 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

26
by: Michael Klatt | last post by:
I am trying to write an iterator for a std::set that allows the iterator target to be modified. Here is some relvant code: template <class Set> // Set is an instance of std::set<> class...
7
by: ma740988 | last post by:
The position returned via the STL std::set container never made much sense to me. When you insert elements within the container, the position returned - via find - does not reflect the actual...
5
by: Peter Jansson | last post by:
Hello, I have the following code: std::map<int,std::set<std::string> > k; k="1234567890"; k="2345678901"; //... std::set<std::string> myMethod(std::map<int,std::set<std::string> > k)...
1
by: jimmy | last post by:
Hi, I am getting a Fatal signal with std::set::insert(). I'm really not sure what to try next: Here is my code: std::cout << "max size: " << _indices.max_size() << std::endl; std::cout <<...
10
by: danibe | last post by:
I never had any problems storing pointers in STL containers such std::vector and std::map. The benefit of storing pointers instead of the objects themselves is mainly saving memory resources and...
4
by: Gernot Frisch | last post by:
Hi, is the sorting order of std::set / std::map defined? i.e. is the *begin() of std::set<int> always smaller than *(--end()) ? -- -Gernot int main(int argc, char** argv) {printf...
2
by: shuisheng | last post by:
Dear All, std::set is sorted. So I am wondering is there any fast way to access (sucn as random access) to its elements just like std::vector. Assume I have a set std::set<inta; So I can...
7
by: Renzr | last post by:
I have a problem about the std::set<>iterator. After finding a term in the std::set<>, i want to know the distance from the current term to the begin(). But i have got a error. Please offer me...
2
by: mathieu | last post by:
hi there, I would like to know if the following piece of code is garantee to work. I am afraid that the cstring address I am using in the std::map found from a request in std::set is not...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...

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.