title: Standard library partition algorithm
body: <p>I wrote this partition function:</p>
  
  <pre><code>template &lt;class I, class P&gt; I partition(I beg, I end, P p)
  {
      I first = beg;
      while(beg != end) {
          if(!p(*beg))
              beg++;
          else {
              // if(beg != first) - EDIT: add conditional to prevent swapping identical elements
              std::swap(*beg, *first);
              first++;
              beg++;
          }
      }
      return first;
  }
  </code></pre>
  
  <p>I've tested it with a few outputs and I haven't found anything wrong with it.</p>
  
  <p>The standard library partition function is equivalent to:</p>
  
  <pre><code>template &lt;class BidirectionalIterator, class UnaryPredicate&gt;
    BidirectionalIterator partition (BidirectionalIterator first,
                                     BidirectionalIterator last, UnaryPredicate pred)
  {
    while (first!=last) {
      while (pred(*first)) {
        ++first;
        if (first==last) return first;
      }
      do {
        --last;
        if (first==last) return first;
      } while (!pred(*last));
      swap (*first,*last);
      ++first;
    }
    return first;
  }
  </code></pre>
  
  <p>The latter seems much more complicated and has nested loops. Is there something wrong with my version? If not why the more complicated version?</p>
  
  <p>Here is some output using the following predicate:</p>
  
  <pre><code>bool greaterthantwo(double val)
  {
      return val &gt; 2;
  }
  </code></pre>
  
  <p><code>MAIN</code></p>
  
  <pre><code>std::vector&lt;double&gt; test{1,2,3,4,2,5,6,7,4,8,2,4,10};
  std::vector&lt;double&gt;::iterator part = ::partition(test.begin(), test.end(), greaterthantwo);
  for(const auto &amp;ref:test)
      std::cout &lt;&lt; ref &lt;&lt; " ";
  std::cout &lt;&lt; std::endl;
  for(auto it = part; it != test.end(); it++)
      std::cout &lt;&lt; *it &lt;&lt; " ";
  std::cout &lt;&lt; std::endl;
  </code></pre>
  
  <p><code>OUTPUT</code></p>
  
  <pre><code>3 4 5 6 7 4 8 4 10 2 2 2 1 
  2 2 2 1 
  </code></pre>