According to this page, I can achieve constant time insertion if I use
iterator std::set::insert ( iterator position, const value_type& x );
and the position
iterator I provide directly "precedes" the proper (in-order) insertion point.
Now the case I'm concerned with is if I know that the value I'm inserting goes at the end (since it's the largest), e.g.:
set<int> foo = {1, 2, 3};
foo.insert(4); // this is an inefficient insert
According to the above criterion I should pass the last element foo.end()-1
to insert
not foo.end()
. Is my understanding correct? What happens if I pass foo.end()
? Will it be a O(log n)
insertion or a O(1)
one. So, the options are:
// Option A
foo.insert(foo.end()-1, 4);
// Option B
foo.insert(foo.end(), 4);
// Safer version of Option A
if(foo.empty())
foo.insert(4);
else
foo.insert(foo.end()-1, 4);
I ask because I'm writing a function that's templated on the container. I want to insert an element (that I know is the largest) to the end of whatever container is passed in. Using "Option A" above has a different behavior for a container like vector
:
foo.insert(foo.end()-1, 4);
// result is {1, 2, 3, 4} if foo is an std::set
// result is {1, 2, 4, 3} if foo is an std::vector
As @Bo_Persson suggests, the problem here is that C++03 says "logarithmic in general, but amortized constant if t is inserted right after p." while C++0x says "logarithmic in general, but amortized constant if t is inserted right before p."
PS: I'm using GCC 4.5 on Ubuntu 11.04 with C++0x support enabled.
Edit: I ran empirical tests with C++0x support enabled and disabled and posted the results in an answer. Basically, the conclusion is that it's just as good (and is obviously safer) to provide end()
as the insertion hint. However, that's obviously just an empirical observation. The standard, as stated, is still confusing on this aspect.
Its time complexity is O(logN) where N is the size of the set. insert(): insert a new element. Its time complexity is O(logN) where N is the size of the set. size(): Returns the size of the set or the number of elements in the set.
A set is the wrong container for keeping insertion order, it will sort its element according to the sorting criterion and forget the insertion order.
The time complexity of Insertion Sort in the best case is O(n). In the worst case, the time complexity is O(n^2).
set find() function in C++ STL The set::find is a built-in function in C++ STL which returns an iterator to the element which is searched in the set container. If the element is not found, then the iterator points to the position just after the last element in the set.
Is it cheating to run a test instead of reading through library specifications?
For g++-4.4 -O2
for the integers 0 <= i < 5000000
my running times for
standard insertion are
real 0m14.952s
user 0m14.665s
sys 0m0.268s
and my running times for insertion using end()
as hint are
real 0m4.373s
user 0m4.148s
sys 0m0.224s
Insertion at end() - 1
is just as fast as far as I can tell, but it is more cumbersome to use because end() - 1
is an illegal operation (you have to use operator--()
) and it crashes if the set happens to be empty.
#include <set>
typedef std::set<int> Set;
void insert_standard(Set& xs, int x)
{
xs.insert(x);
}
void insert_hint_end(Set& xs, int x)
{
xs.insert(xs.end(), x);
}
int main()
{
const int cnt = 5000000;
Set xs;
for (int i = 0; i < cnt; i++) {
// insert_hint_end(xs, i);
insert_standard(xs, i);
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With