title: How to sort only subset in std::vector?
body: <p>I have a <code>vector</code> of <code>pair</code>s:</p>
  
  <pre><code>std::vector&lt;std::pair&lt;std::string, Cell::Ptr&gt;&gt; mCells;
  </code></pre>
  
  <p>I want to sort only a subset of elements (on the <code>first</code>'s <code>string</code>).  The <code>Cell</code> has method <code>GetSorted()</code> which indicates if it's part of this subset or not.</p>
  
  <p>This is what I had initially:</p>
  
  <pre><code>std::sort(mCells.begin(), mCells.end(),
            [](std::pair&lt;std::string, Cell::Ptr&gt; const &amp;a,
               std::pair&lt;std::string, Cell::Ptr&gt; const &amp;b)
  {
      // Only compare when both cells need to be sorted; otherwise return false
      // to indicate that they are already in correct order.  This keeps the
      // non-marked cells at their original positions.
      if (a.second-&gt;GetSorted() &amp;&amp; b.second-&gt;GetSorted())
      {
          return a.first &lt; b.first;
      }
      else
      {
          return false;
      }
  });
  </code></pre>
  
  <p>But it does not work, because <code>sort</code>, of course, does not compare all combinations.  Sometimes the <code>return a.first &lt; b.first</code> line is not even executed once.</p>
  
  <p>To define the required sort function, here's an example.  Suppose the elements are:</p>
  
  <pre><code>G* F  C* A* D  B  E*
  </code></pre>
  
  <p>Only the *-ones need to be sorted.  But, the sort should only be applied to adjacent to-be-sorted elements.  (That's why I had <code>a.second-&gt;GetSorted() &amp;&amp; b.second-&gt;GetSorted()</code>.)  The result should then be:</p>
  
  <pre><code>G* F  A* C* D  B  E*
  </code></pre>
  
  <p>So, only <strong>A</strong> and <strong>C</strong> are adjacent, and are sorted.  Is there an easy solution to this problem?</p>
  
  <p>Alternatively a solution that results in:</p>
  
  <pre><code>A* F  C* E* D  B  G*
  </code></pre>
  
  <p>would also be usable for me at the moment.  So, sorting all * elements, while leaving the others where they are.  This appears to be easier to do.</p>