O(1) append to set

[Phil Endecott]

Dear All,

I have some code that first populates a std::set, and subsequently does
a mixture of tests-for-presence and deletions. As I understand it,
populating the set will be O(N log N), since each of the N inserts will
be O(log N), and the test and deletes will each be O(log N).

In this case, however, I am populating it with values in ascending order
- it's actually a for loop. I feel that because of this it should be
possible to populate the set in O(N) time. This would be possible if
std::set had an O(1) 'append'-like operation.

Can anyone suggest how I could go about getting this reduced complexity,
if indeed it is possible? I could use a sorted std::vector, which has
O(1) append and could have an O(log N) find using a binary chop (is
there a std::algorithm that will do that for me?), but it doesn't have
an O(log N) delete operation; a sorted std::list does have good delete
performance but lacks O(log N) find. Any ideas?

Cheers,

--Phil.

 

[Mark P]

Dear All,

I have some code that first populates a std::set, and subsequently does
a mixture of tests-for-presence and deletions. As I understand it,
populating the set will be O(N log N), since each of the N inserts will
be O(log N), and the test and deletes will each be O(log N).

In this case, however, I am populating it with values in ascending order
- it's actually a for loop. I feel that because of this it should be
possible to populate the set in O(N) time. This would be possible if
std::set had an O(1) 'append'-like operation.

Can anyone suggest how I could go about getting this reduced complexity,
if indeed it is possible? I could use a sorted std::vector, which has
O(1) append and could have an O(log N) find using a binary chop (is
there a std::algorithm that will do that for me?), but it doesn't have
an O(log N) delete operation; a sorted std::list does have good delete
performance but lacks O(log N) find. Any ideas?

Cheers,

--Phil.

Not sure if this is standard, but the SGI STL implementation guarantees
linear time for ranged insertions if the range is already sorted. (I
actually find this a bit suspicious since it's stated so generally. I
suspect they mean this for the case where the set is initially empty.)

Another option is to use insert with hint and use end() as the hint for
each sequential insertion.

 

[John Harrison]

Dear All,

I have some code that first populates a std::set, and subsequently does
a mixture of tests-for-presence and deletions. As I understand it,
populating the set will be O(N log N), since each of the N inserts will
be O(log N), and the test and deletes will each be O(log N).

In this case, however, I am populating it with values in ascending order
- it's actually a for loop. I feel that because of this it should be
possible to populate the set in O(N) time. This would be possible if
std::set had an O(1) 'append'-like operation.

Can anyone suggest how I could go about getting this reduced complexity,
if indeed it is possible? I could use a sorted std::vector, which has
O(1) append and could have an O(log N) find using a binary chop (is
there a std::algorithm that will do that for me?), but it doesn't have
an O(log N) delete operation; a sorted std::list does have good delete
performance but lacks O(log N) find. Any ideas?

Cheers,

--Phil.

Set does have an O(1) append operation, but only if you use the two
iterator version of the constructor and the values are in order.

So build the values you want to populate with into a vector then
construct the set

std::vector<int> sorted_values;
for (...)
{
...
sorted_values.push_back(...);
}
std:set<int> s(sorted_values.begin(), sorted_values.end());

john

 

[John Harrison]

So build the values you want to populate with into a vector then
construct the set

std::vector<int> sorted_values;
for (...)
{
...
sorted_values.push_back(...);
}
std:set<int> s(sorted_values.begin(), sorted_values.end());

john

Or use the hint option that Mark P talks about, I forgot about that.

john

 

[Phil Endecott]

Set does have an O(1) append operation, but only if you use the two
iterator version of the constructor and the values are in order.

Thanks Mark & John for the very quick replies - this is exactly what I
needed.

--Phil.

 

[=?iso-8859-1?Q?Ali_=C7ehreli?=]

I could use a sorted std::vector, which has O(1) append and could have an
O(log N) find using a binary chop (is there a std::algorithm that will do
that for me?),

Yes, there is a binary search algorithm but it is called lower_bound. Note
that it is log N only for random access iterators, which vector provides.

The algorithm that one would assume to be doing binary search is called
binary_search, but it returns merely whether the object exists or not

Ali