C++ Elegant solution to partition problem
<p>I would like to see the most elegant STL like extension to the partition algorithm in the
STL:</p>

<pre><code>given a vector of ints, partition the vector so that the positive integers appear
to the front of the negative integers
AND
return a map&lt;int, int&gt; where map[i]=j means that integer at index i is now at j.
</code></pre>

<p>Obviously the first part (without the second requirement) is something like</p>

<pre><code>partititon(vec.begin(), vec.end(), IsEven)
</code></pre>

<p>I can't see a way to do this without actually reimplementing partition and building the
map along the way. </p>
