C ++ Elegant solution to partition problem

Question

I would like to see the most elegant STL extension, similar to the STL partitioning algorithm extension:

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 see no way to do this without actually redefining the section and building a map along the way.

Answer 1

Copy your vector ints into a vector of something like:

struct ValIdx
{
    int val;
    size_t idx;
};

Separate with the corresponding functor, then move the result by copying the ints back and plotting the map.