Reduction function (for many sets) in C ++

Question

What I'm trying to do: I have a simple function for combining sets in C ++ using STL, and I'm trying to wrap it in a function that will allow me to combine arbitrarily many sets contained in STL data structures (for example, std::list , std::vector , std::forward_list , ...).

How I tried to do this: First, my simple union set:

 #include <algorithm> template <typename set_type> set_type sunion(const set_type & lhs, const set_type & rhs) { set_type result; std::set_union( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.end()) ); return result; } 

where set_type defines some STL std::set<T> , for example. std::set<int> .

After noticing several times that I need to perform several unions on set iterators (in Python this will reduce my sunion function over some set_type s object). For example, I could

 std::vector<std::set<int> > all_sets; 

or

 std::list<std::set<int> > all_sets; 

etc., and I want to get the union of all sets in all_sets . I am trying to implement a simple snapshot for this, which essentially makes the (faster, more elegant, non-copying) version:

 sunion(... sunion( sunion( all_sets.begin(), all_sets.begin()+1 ), all_sets.begin()+2 ) , ... ) 

Essentially, to do this quickly, I just want to declare a set_type result , and then iterate through all_sets and paste the value into each set of all_sets into the result object:

 template <typename set_type> set_type sunion_over_iterator_range(const std::iterator<std::forward_iterator_tag, set_type> & begin, const std::iterator<std::forward_iterator_tag, set_type> & end) { set_type result; for (std::iterator<std::forward_iterator_tag, set_type> iter = begin; iter != end; iter++) { insert_all(result, *iter); } return result; } 

where insert_all is defined:

 // |= operator; faster than making a copy and performing union template <typename set_type> void insert_all(set_type & lhs, const set_type & rhs) { for (typename set_type::iterator iter = rhs.begin(); iter != rhs.end(); iter++) { lhs.insert(*iter); } } 

How it does not work: Unfortunately, my sunion_over_iterator_range(...) does not work with the arguments std::vector<set_type>::begin(), std::vector<set_type>::end() , which are of type std::vector<set_type>::iterator . I thought std::vector<T>::iterator returns iterator<random_access_iterator_tag, T> . A

After compilation failed due to incompatibility of iterator types, I looked at the source of the stl vector (located in /usr/include/++/4.6/bits/stl_vector.h for g ++ 4.6 and Ubuntu 11.10), and was surprised to see that the typedef for vector<T>::iterator will be typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; . I thought ForwardIterator was a subtype of RandomAccessIterator, and that should be fine , but obviously I was wrong or I wouldn’t be here.

I am so grateful and ashamed of inciting your disappointment due to my inexperience: I apologize if I show my ignorance - I try to learn how to be the best object-oriented programmer (in the past I just hacked everything in style C code).

I'm doing my best, coach! Please help me and save the world from the bad code that I will produce without your understanding of the ninja code ...

Answer 1

Usually when using iterators we do not care about the real category. Just let the implementation figure it out. This means that just change the function to accept any type:

 template <typename T> typename std::iterator_traits<T>::value_type sunion_over_iterator_range(T begin, T end) { typename std::iterator_traits<T>::value_type result; for (T iter = begin; iter != end; ++ iter) { insert_all(result, *iter); } return result; } 

Note that I used typename std::iterator_traits<T>::value_type , which is a type of *iter .

By the way, the iterator pattern is not associated with OOP. (This does not mean that it is bad).

Answer 2

Here's a very naive approach:

 std::set<T> result; std::vector<std::set<T>> all_sets; for (std::set<T> & s : all_sets) { result.insert(std::make_move_iterator(s.begin()), std::make_move_iterator(s.end())); } 

This invalidates the elements in the source sets, although it does not actually move the element nodes. If you want to leave the source sets intact, just remove make_move_iterator .

Unfortunately, there is no interface for std::set , which allows you to "splic" two sets in such a way as not to redistribute the internal nodes of the tree, so this is more or less good than you can get.

The variational pattern is applied here:

 template <typename RSet> void union(RSet &) { } template <typename RSet, typename ASet, typename ...Rest> void union(RSet & result, ASet const & a, Rest const &... r) { a.insert(a.begin(), a.end()); union(result, r...); } 

Using:

 std::set<T> result union(result, s1, s2, s3, s4); 

(Similar relocation optimizations are possible here, you can even add a branch that will be copied from immutable, but switched from mutable or only from rvalues ​​if you want.)

Here is the version using std::accumulate :

 std::set<T> result = std::accumulate(all_sets.begin(), all_sets.end(), std::set<T>(), [](std::set<T> & s, std::set<T> const & t) { s.insert(t.begin(), t.end()); return s; } ); 

This version seems to rely a lot on optimizing the return value, so you might like to compare it with this hacked and rather ugly version:

 std::set<T> result; std::accumulate(all_sets.begin(), all_sets.end(), 0, [&result](int, std::set<T> const & t) { result.insert(t.begin(), t.end()); return 0; } );