title: A reduce function (for many set unions) in C++
body: <p><strong>What I am trying to do:</strong>
  I have a simple set union function in C++ using STL, and I'm trying to wrap it in a function that will let me perform the union of arbitrarily many sets contained in STL data structures (e.g. <code>std::list</code>, <code>std::vector</code>, <code>std::forward_list</code>, ...).</p>
  
  <p><strong>How I tried to do it:</strong>
  To start, my simple set union:</p>
  
  <pre><code>#include &lt;algorithm&gt;
  template &lt;typename set_type&gt;
  set_type sunion(const set_type &amp; lhs, const set_type &amp; rhs)
  {
    set_type result;
    std::set_union( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.end()) );
    return result;
  }
  </code></pre>
  
  <p>where <code>set_type</code> defines some STL <code>std::set&lt;T&gt;</code>, e.g. <code>std::set&lt;int&gt;</code>.</p>
  
  <p>After noticing several times that I end up needing to perform several unions on iterators of sets (in <code>Python</code> this would be a <code>reduce</code> of my <code>sunion</code> function over some iterable object of <code>set_type</code>s). For instance, I might have </p>
  
  <pre><code>std::vector&lt;std::set&lt;int&gt; &gt; all_sets;
  </code></pre>
  
  <p>or </p>
  
  <pre><code>std::list&lt;std::set&lt;int&gt; &gt; all_sets;
  </code></pre>
  
  <p>etc., and I want to get the union of all sets in <code>all_sets</code>. I am trying to implement a simple reduce for this, which essentially does a (faster, more elegant, non-copying) version of:</p>
  
  <pre><code>sunion(... sunion( sunion( all_sets.begin(), all_sets.begin()+1 ), all_sets.begin()+2 ) , ... )
  </code></pre>
  
  <p>Essentially, to do this quickly, I just want to declare a <code>set_type result</code> and then iterate through <code>all_sets</code> and insert value in every set in <code>all_sets</code> into the result object:</p>
  
  <pre><code>template &lt;typename set_type&gt;
  set_type sunion_over_iterator_range(const std::iterator&lt;std::forward_iterator_tag, set_type&gt; &amp; begin, const std::iterator&lt;std::forward_iterator_tag, set_type&gt; &amp; end)
  {
    set_type result;
    for (std::iterator&lt;std::forward_iterator_tag, set_type&gt; iter = begin; iter != end; iter++)
      {
        insert_all(result, *iter);
      }
    return result;
  }
  </code></pre>
  
  <p>where <code>insert_all</code> is defined:</p>
  
  <pre><code>// |= operator; faster than making a copy and performing union
  template &lt;typename set_type&gt;
  void insert_all(set_type &amp; lhs, const set_type &amp; rhs)
  {
    for (typename set_type::iterator iter = rhs.begin(); iter != rhs.end(); iter++)
      {
        lhs.insert(*iter);
      }
  }
  </code></pre>
  
  <p><strong>How it didn't work:</strong>
  Unfortunately, my <code>sunion_over_iterator_range(...)</code> doesn't work with arguments <code>std::vector&lt;set_type&gt;::begin(), std::vector&lt;set_type&gt;::end()</code>, which are of type <code>std::vector&lt;set_type&gt;::iterator</code>. I thought <code>std::vector&lt;T&gt;::iterator</code> returns an <code>iterator&lt;random_access_iterator_tag, T&gt;</code>. A</p>
  
  <p>After compilation failed because of type incompatibility of the iterators, I looked at the stl vector source (located in <strong>/usr/include/c++/4.6/bits/stl_vector.h</strong> for g++ 4.6 &amp; Ubuntu 11.10), and was surprised to see the typedef for <code>vector&lt;T&gt;::iterator</code> to be <code>typedef __gnu_cxx::__normal_iterator&lt;pointer, vector&gt; iterator;</code>. I had thought that a <a href="http://www.cplusplus.com/reference/std/iterator/ForwardIterator/">ForwardIterator was a subtype of RandomAccessIterator, and so should be fine</a>, but clearly I was incorrect, or I would not be here.</p>
  
  <p><strong>How I am grateful and ashamed of inciting your frustration due to my inexperience:</strong>
  Apologies if I'm showing my ignorance-- I am trying to learn to be a better object oriented programmer (in the past I have simply hacked everything out in C-style code). </p>
  
  <p>I'm doing my best, coach! Please help me out and spare the world from bad code that I would produce without your code ninja insight... </p>