CODEWITHSUNDEEP
c++stlset
Simon
Simon

Reputation: 3450

Alternative to std::set (with ability to move elements from one set to another)

I'm looking for an alternative to std::set. I need it to support more operations then std::set:

  1. Move elements from one set to another without 'create new->copy->remove old'.

  2. Split set at some position to get two sets (similar behaviour can be obtained using std::list splice)

  3. Set operations (like union) without unnecessary copying. std::set_union will copy elements from sets A and B to set C which is inefficient if I only need set C and don't need A and B anymore.

Are there any implementations which support these operations or I need to write one myself?

Upvotes: 3

Views: 3967

Answers (3)

Botond Dénes
Botond Dénes

Reputation: 620

I have the same problem as you with std::set and there doesn't seem to be any sane way around with C++11, C++14. However in C++17 there are two new members added to std::set which look very promising. std::set::extract allows extracting an entire node from the set. The removed node allows for obtaining a non-const reference to the underlying value effectively allowing for moving elements out of the set. It can be also inserted into another set without copying or moving the underlying value. std::set::merge allows for merging two sets without copying or moving any elements, only updating internal pointers.

Upvotes: 6

Haocheng
Haocheng

Reputation: 1343

For point 1 & 3, you can use set<shared_ptr> or some other smart pointer instead of store object directly in the set. In this case, you should implement

bool operator<(shared_ptr<T> const & a, shared_ptr<T> const & b)

For point 2, there won't be such a method determined just by index because there's no index in set. However, you can use something like filter in ruby. Here predicator can be function, function object or closure.

remove_copy_if(foo.begin(), foo.end(), back_inserter(bar), some_predicator);

Upvotes: 2

Peter Ogden
Peter Ogden

Reputation: 720

The problem with trying to do what you suggest with a std::set is that I do not believe you can move a value out of one. This is due to set iterators only returning const references to stop you changing the value and breaking the internal structure. You could probably const_cast your way around this but I wouldn't recommend it. Even if you adopt this approach then you still have nodes in the tree being allocated and there is nothing you can do to avoid this overhead.

If you decide to implement your own set which supports moving values around, you should be able to get the Boost::Intrusive library (http://www.boost.org/doc/libs/1_52_0/doc/html/intrusive.html) to do the heavy lifting of keeping a set of sorted values. You would need to implement the code for managing the object lifetimes but that is easier than building a RB-tree implementation.

I implemented something similar for maps which stored the nodes in a std::list. This allowed for moving elements between maps without copying either the node structure or the values being stored. If I get time I will try and tidy it up and post it here.

Upvotes: 2

Related Questions