how to return index of sorted vector

[boheman]

Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.
I can use

sort(x.begin(), x.end(), less<int>());

to sort the vector x. Then the sorted x becomes {0, 2, 2, 3, 5}. But
how can I obtain the indices of sorted x, which is {3, 1, 4, 2, 0}.

I know that I can insert each element of x paired with the index into a
multimap and read out the reordered indices. But that is not what I am
looking for since I do not want to spend memory to keep another copy of
my vector x in multimap.

Surapong L.

[Clem.Dickey]

bo*****@gmail.com wrote:

Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.

....

to sort the vector x. Then the sorted x becomes {0, 2, 2, 3, 5}. But
how can I obtain the indices of sorted x, which is {3, 1, 4, 2, 0}.

Create a vector i = {0,1,2,3,4,5} of sort indexes (std::generate should
com in handy). Use the three argument sort, where the third argument
references your vector x, to compare the elements of i based not on
their own values but on the values they index in x:

class lt {
vector<int&_x;
public:
lt( vector<int& x ) : _x(x) {}
bool comp( int j, int k ) const { return _x[j] < _x[k]; }
};
....
sort( i.begin(), i.end(), lt(x) );

Incidentally, APL has a "grade" primitive which does exactly this.

[Daniel T.]

bo*****@gmail.com wrote:

>
Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.
I can use

sort(x.begin(), x.end(), less<int>());

to sort the vector x. Then the sorted x becomes {0, 2, 2, 3, 5}. But
how can I obtain the indices of sorted x, which is {3, 1, 4, 2, 0}.

I know that I can insert each element of x paired with the index into a
multimap and read out the reordered indices. But that is not what I am
looking for since I do not want to spend memory to keep another copy of
my vector x in multimap.

Another solution. Create a vector< pair< int, int . The first int in
the pair is the index. Use a compare function that only deals with the
second element for your sort. That way the index will follow the value.

Like the last solution, generate can be used to initialize the indexes.

[rossum]

On 13 Dec 2006 22:12:44 -0800, bo*****@gmail.com wrote:

>Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.
I can use

sort(x.begin(), x.end(), less<int>());

to sort the vector x. Then the sorted x becomes {0, 2, 2, 3, 5}. But
how can I obtain the indices of sorted x, which is {3, 1, 4, 2, 0}.

Using std::sort() the indices could also be {3, 4, 1, 2, 0} as
std::sort() is not guaranteed to be stable. If this is important to
you then you need to use std::stable_sort() which will produce {3, 1,
4, 2, 0} only.

rossum

>
I know that I can insert each element of x paired with the index into a
multimap and read out the reordered indices. But that is not what I am
looking for since I do not want to spend memory to keep another copy of
my vector x in multimap.

Surapong L.

[surapong]

Thanks so much for all of your replys !!!

Surapong L.