C++ Elegant solution to partition problem

Question

I would like to see the most elegant STL like extension to the partition algorithm in the STL:

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<int, int> where map[i]=j means that integer at index i is now at j.

Obviously the first part (without the second requirement) is something like

partititon(vec.begin(), vec.end(), IsEven)

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

Answer 1

Copy your vector of ints into a vector of something like:

struct ValIdx
{
    int val;
    size_t idx;
};

Partition with an appropriate functor, then iterate over the result copying the ints back out and building your map.