Re: indirect / index sorting with the STL

I was challenged to come up with a way to use existing STL algorithms
to sort one vector but given sorting precedence in a separate vector.
An additional constraint is that only O(1) constant external storage
may be used.

In other words, a vector<string> containing "A","B","C" sorted
indirectly given the precedence vector<int> of 22,11,33 would yield a
vector<string> of "B","A","C".

I tried to write my own container class that simulated a real
container but contained references to the two vectors, the target
vector and the index vector. I ran into trouble when I had to
implement operator* on my pointer class because I had no real object
to return a reference to.

Obviously the puzzle is easy if I copy the elements into a vector<
pair<k,v> > and supply my own comparison functor which compares the
pair::second. But this adds too much overhead in the copy/copy back
and violates my constraint of O(1) external storage.

I've come to the conclusion that this can't be done with std::sort,
but is there another algorithm that can help? Aside from rewriting
sort on my own, does anyone have another suggestion?

Thanks,

J