# stl algorithm get - C++ sorting and keeping track of indexes

You could sort std::pair instead of just ints - first int is original data, second int is original index. Then supply a comparator that only sorts on the first int. Example:

``````Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]
``````

Sort the new problem instance using a comparator like:

``````typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
{ return l.first < r.first; }
// forgetting the syntax here but intent is clear enough
``````

The result of std::sort on v_prime, using that comparator, should be:

``````v_prime = [<5,0>, <7,2>, <8,1>]
``````

You can peel out the indices by walking the vector, grabbing .second from each std::pair.

the indices array

Using C++, and hopefully the standard library, I want to sort a sequence of samples in ascending order, but I also want to remember the original indexes of the newly samples.

For example, I have a set, or vector, or matrix of samples `A : [5, 2, 1, 4, 3]`. I want to sort these to be `B : [1,2,3,4,5]`, but I also want to remember the original indexes of the values, so I can get another set which would be: `C : [2, 1, 4, 3, 0 ]` - which corresponds to the index of the each element in 'B', in the original 'A'.

For example, in Matlab you can do:

`````` [a,b]=sort([5, 8, 7])
a = 5 7 8
b = 1 3 2
``````

Can anyone see a good way to do this?

``````vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
// filling the original array
cin >> k;
a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
cout << a[i].first << " " << a[i].second << "\n";
}
``````

Now `a` contains both both our values and their respective indices in the sorted.

`a[i].first = value` at `i`'th.

`a[i].second = idx` in initial array.

Its easier than it seems to be.

Suppose Given vector is

``````A=[2,4,3]
``````

Create A new vector

``````V=[0,1,2] // indicating positions
``````

Sort V and while sorting instead of comparing elements of V , compare corresponding elements of A

`````` //Assume A is a given vector with N elements
vector<int> V(N);
int x=0;
std::iota(V.begin(),V.end(),x++); //Initializing
sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
``````

Beautiful solution by @Lukasz Wiklendt! Although in my case I needed something more generic so I modified it a bit:

``````template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

vector<size_t> idx(last-first);
iota(idx.begin(), idx.end(), 0);

auto idxComp = [&first,comp](size_t i1, size_t i2) {
return comp(first[i1], first[i2]);
};

sort(idx.begin(), idx.end(), idxComp);

return idx;
}
``````

Example: Find indices sorting a vector of strings by length, except for the first element which is a dummy.

``````vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
cout << beginIt[i] << endl;
``````

prints:

``````abc
ab
a
``````

There is another way to solve this, using a map:

``````vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
m[*it] = it - v.begin();
``````

This will eradicate non-unique elements though. If that's not acceptable, use a multimap:

``````vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
m.insert(make_pair(*it, it - v.begin()));
``````

In order to output the indices, iterate over the map or multimap:

``````for (auto it = m.begin(); it != m.end(); ++it)
cout << it->second << endl;
``````

For this type of question Store the orignal array data into a new data and then binary search the first element of the sorted array into the duplicated array and that indice should be stored into a vector or array.

``````input array=>a
duplicate array=>b
vector=>c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i<n;i++)
c.push_back(binarysearch(b,n,a[i]));`
``````

Here binarysearch is a function which takes the array,size of array,searching item and would return the position of the searched item

There are many ways. A rather simple solution is to use a 2D vector.

``````#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<vector<double>> val_and_id;
val_and_id.resize(5);
for (int i = 0; i < 5; i++) {
val_and_id[i].resize(2); // one to store value, the other for index.
}
// Store value in dimension 1, and index in the other:
// say values are 5,4,7,1,3.
val_and_id[0][0] = 5.0;
val_and_id[1][0] = 4.0;
val_and_id[2][0] = 7.0;
val_and_id[3][0] = 1.0;
val_and_id[4][0] = 3.0;

val_and_id[0][1] = 0.0;
val_and_id[1][1] = 1.0;
val_and_id[2][1] = 2.0;
val_and_id[3][1] = 3.0;
val_and_id[4][1] = 4.0;

sort(val_and_id.begin(), val_and_id.end());
// display them:
cout << "Index \t" << "Value \n";
for (int i = 0; i < 5; i++) {
cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
}
return 0;
}
``````

Here is the output:

``````   Index   Value
3       1
4       3
1       4
0       5
2       7
``````

### Tags

c++   sorting   stl   indexing