std::set<T>::insert, duplicate elements

2
votes

What would be an efficient implementation for a std::set insert member function? Because the data structure sorts elements based on std::less (operator < needs to be defined for the element type), it is conceptually easy to detect a duplicate.

How does it actually work internally? Does it make use of the red-back tree data structure (a mentioned implementation detail in the book of Josuttis)?

Implementations of the standard data structures may vary...

I have a problem where I am forced to have a (generally speaking) sets of integers which should be unique. The length of the sets varies so I am in need of dynamical data structure (based on my narrow knowledge, this narrows things down to list, set). The elements do not necessarily need to be sorted, but there may be no duplicates. Since the candidate sets always have a lot of duplicates (sets are small, up to 64 elements), will trying to insert duplicates into std::set with the insert member function cause a lot of overhead compared to std::list and another algorithm that may not resort to having the elements sorted?

Additional: the output set has a fixed size of 27 elements. Sorry, I forgot this... this works for a special case of the problem. For other cases, the length is arbitrary (lower than the input set).

3
c++data-structuresstlset
It's not clear what your question is. Is it "How does std::set work?", or is it "what's the complexity of std::set::insert?" or is it "what data structure should I use?" or something else? - Oliver Charlesworth
Basically the answer to all three would be great, because I am not sure if I chose the right data structure for the problem at hand. The complexity of the insert is logarithmic, but it can be decreased if I can guesstimate the iterator position of the insert operation. I can also speed it up if I assemble all the elements and then I use a single call instead of a per-element call. I've read all that, but still I'm not sure if I'm doing the right thing. - tmaric
Guesstimating the iterator position is not good enough, you have to get it exactly right or it won't help. - Mark Ransom
Out of curiosity, what do you think std::list offers here that would make it more suited to the task where std::vector would not? In fact, since std::vector has random access, it would be a far better choice than std::list, since if you kept it sorted, you could use a binary search on it. In fact, in some cases, this is even better than std::set. - Benjamin Lindley
@Itjax: But first you need to find the position where the element goes. - Benjamin Lindley

3 Answers

1
votes

When you only have 64 possible values known ahead of time, just take a bit field and flip on the bits for the elements actually seen. That works in n+O(1) steps, and you can't get less than that.

Inserting into a std::set of size m takes O(log(m)) time and comparisons, meaning that using an std::set for this purpose will cost O(n*log(n)) and I wouldn't be surprised if the constant were larger than for simply sorting the input (which requires additional space) and then discarding duplicates.

Doing the same thing with an std::list would take O(n^2) average time, because finding the insertion place in a list needs O(n).

Inserting one element at a time into an std::vector would also take O(n^2) average time – finding the insertion place is doable in O(log(m)), but elements need to me moved to make room. If the number of elements in the final result is much smaller than the input, that drops down to O(n*log(n)), with close to no space overhead.

If you have a C++11 compiler or use boost, you could also use a hash table. I'm not sure about the insertion characteristics, but if the number of elements in the result is small compared to the input size, you'd only need O(n) time – and unlike the bit field, you don't need to know the potential elements or the size of the result a priori (although knowing the size helps, since you can avoid rehashing).

3
votes

If you're creating the entire set all at once, you could try using std::vector to hold the elements, std::sort to sort them, and std::unique to prune out the duplicates.

2
votes

The complexity of std::set::insert is O(log n), or amortized O(1) if you use the "positional" insert and get the position correct (see e.g. http://cplusplus.com/reference/stl/set/insert/).

The underlying mechanism is implementation-dependent. It's often a red-black tree, but this is not mandated. You should look at the source code for your favourite implementation to find out what it's doing.

For small sets, it's possible that e.g. a simple linear search on a vector will be cheaper, due to spatial locality. But the insert itself will require all the following elements to be copied. The only way to know for sure is to profile each option.