Inserting into std::set

[Marcus Kwok]

I am not sure if this is something that is covered by the Standard, or
if it's an implementation detail of my Standard Library.

I am reading in a large amount of data into a std::set. There is an
overload for std::set::inser t() that takes in an iterator as a hint as
to where the new value should be inserted, and my implementation
(Dinkumware) says that if the hint is good (meaning the iterator points
immediately before or after where the inserted value should go) then the
insertion can happen in amortized constant time rather than logarithmic
time.

I would like to take advantage of this fact. My input data should
already be in sorted order, therefore I think I can use my_set.end() as
the hint to insert(). Is this a valid assumption, or does this depend
on how std::set is actually implemented?

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Marcus Kwok]

Pete Becker <pe********@acm .orgwrote:

Marcus Kwok wrote:

>Mark P <us****@fall200 5remove.fastmai lcaps.fmwrote:

>>Keep in mind that inserting elements into a set in sorted order may be
far from optimal and that the run time may be dominated by the
rebalancing required to maintain the red-black tree.

Hmm, OK, in that case let me add something to my situation. I have a
large list of data that I am adding to my container in sorted order.
There is a possibility of duplicates, but we do not want to add
duplicates. Initially, I was pushing the data to the back of a vector,
but checking if the element was already in the vector before pushing it
back. This repeated searching was very inefficient and was what caused
me to redesign it using a set, since I can just insert without needing
to check before. Using a set instead of the previous method with vector
caused a 4-5x speed increase.

Do you have another suggestion for something I can try?

std::unique or std::unique_cop y.

Thanks, I'll look into them.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Marcus Kwok]

David Harmon <so****@netcom. comwrote:

If your data is sorted, then you only need to check if each item is
the same as the previous, right? And at the same time, a check if
the item is "less than" the previous will verify that it really is
sorted.

That's a good idea. Unfortunately, I should have said that our data
"should be" sorted before reading in, but there is the possibility that
something might come in out of order... though this possibility is
rather low, I still need to handle it properly in case it isn't.

Thanks for your input.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Mark P]

Marcus Kwok wrote:

David Harmon <so****@netcom. comwrote:

>If your data is sorted, then you only need to check if each item is
the same as the previous, right? And at the same time, a check if
the item is "less than" the previous will verify that it really is
sorted.

That's a good idea. Unfortunately, I should have said that our data
"should be" sorted before reading in, but there is the possibility that
something might come in out of order... though this possibility is
rather low, I still need to handle it properly in case it isn't.

Thanks for your input.

So apply std::sort to the initial data, then apply std::unique or
std::unique_cop y as Pete Becker suggested.

As a rule of thumb, if the data only needs to be sorted once, then a
dynamically sorted container such as std::set is probably overkill
(read: inefficient). std::set is nice if you need to sort "online", but
red-black tree algorithms are much more complex than simple sorting.