# sort and get index?

Discussion in 'C++' started by b83503104, May 21, 2004.

1. ### b83503104Guest

In matlab, the sort function returns two things:

[a,b]=sort([5, 8, 7])

a = 5 7 8
b = 1 3 2

where a is the sorted result, and b is the corresponding index.
Is there C++ code available to achieve this?
Better compatible with STL vector.
Thanks

b83503104, May 21, 2004

2. ### Victor BazarovGuest

"b83503104" <> wrote...
> In matlab, the sort function returns two things:
>
> [a,b]=sort([5, 8, 7])
>
> a = 5 7 8
> b = 1 3 2
>
> where a is the sorted result, and b is the corresponding index.
> Is there C++ code available to achieve this?

Probably. You could simply sort pairs based on their 'first'
members, then get the 'second' members (which you should set
to ordinal numbers before sorting).

V

Victor Bazarov, May 21, 2004

3. ### MeGuest

template<class T> struct index_cmp {
index_cmp(const T arr) : arr(arr) {}
bool operator()(const size_t a, const size_t b) const
{ return arr[a] < arr; }
const T arr;
};

vector<int> a;
a.push_back(5); a.push_back(8); a.push_back(7);

vector<size_t> b;
for (unsigned i = 0; i < a.size(); ++i)
b.push_back(i);
// b = [0, 1, 2]
sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));
// b = [0, 2, 1]

then just offset into the a vector with the indices in b. I recomend
just sorting the indices this way and not touching the a vector.

Me, May 21, 2004
4. ### Siemel NaranGuest

(b83503104) wrote in message

> In matlab, the sort function returns two things:
>
> [a,b]=sort([5, 8, 7])
>
> a = 5 7 8
> b = 1 3 2
>
> where a is the sorted result, and b is the corresponding index.
> Is there C++ code available to achieve this?
> Better compatible with STL vector.
> Thanks

There is no such way in C++. But you can build it yourself.

Here is one suggestion: make your original vector { 5, 8, 7 }, make a
vector of pointers { &orig[0], &orig[1], &orig[2] }, sort the vector
of pointers using std::sort of 3 arguments which should yield {
&orig[0], &orig[2], &orig[1] }.

A second suggestion is: make your original vector a vector of
pair<int, index> as { {5,0}, {8,1}, {7,2} }, sort the vector using
std::sort of 3 arguments which should yield { {5,0}, {7,2}, {8,1} }.

The first way would look something like this:

std::vector<int> orig;
orig.push_back(5);
orig.push_back(7);
orig.push_back(8);
std::vector<const int *> pointer;
pointer.reserve(orig.size());
const int *const start = &orig[0];
const int *const end = start + orig.size();
for (int * iter = start; iter != end; ++iter) pointer.push_back(iter);
std::sort(pointer.begin(), pointer.end(), LessDereference());

where

struct LessDereference {
template <class T>
bool operator()(const T * lhs, const T * rhs) const {
return *lhs < *rhs;
}
};

To print the results, choose whatever option you want. There are many
ways, and here is one:

for (int i=0; i<pointer.size(); i++) {
const int * p = pointer;
cout << "(" << *p << "," << p-start << " ";
}

Siemel Naran, May 21, 2004
5. ### Siemel NaranGuest

(b83503104) wrote in message

> In matlab, the sort function returns two things:
>
> [a,b]=sort([5, 8, 7])
>
> a = 5 7 8
> b = 1 3 2
>
> where a is the sorted result, and b is the corresponding index.
> Is there C++ code available to achieve this?
> Better compatible with STL vector.
> Thanks

There is no such way in C++. But you can build it yourself.

Here is one suggestion: make your original vector { 5, 8, 7 }, make a
vector of pointers { &orig[0], &orig[1], &orig[2] }, sort the vector
of pointers using std::sort of 3 arguments which should yield {
&orig[0], &orig[2], &orig[1] }.

A second suggestion is: make your original vector a vector of
pair<int, index> as { {5,0}, {8,1}, {7,2} }, sort the vector using
std::sort of 3 arguments which should yield { {5,0}, {7,2}, {8,1} }.

The first way would look something like this:

std::vector<int> orig;
orig.push_back(5);
orig.push_back(7);
orig.push_back(8);
std::vector<const int *> pointer;
pointer.reserve(orig.size());
const int *const start = &orig[0];
const int *const end = start + orig.size();
for (int * iter = start; iter != end; ++iter) pointer.push_back(iter);
std::sort(pointer.begin(), pointer.end(), LessDereference());

where

struct LessDereference {
template <class T>
bool operator()(const T * lhs, const T * rhs) const {
return *lhs < *rhs;
}
};

To print the results, choose whatever option you want. There are many
ways, and here is one:

for (int i=0; i<pointer.size(); i++) {
const int * p = pointer;
cout << "(" << *p << "," << p-start << " ";
}

Siemel Naran, May 21, 2004
6. ### Siemel NaranGuest

(Me) wrote in message

> template<class T> struct index_cmp {
> index_cmp(const T arr) : arr(arr) {}
> bool operator()(const size_t a, const size_t b) const
> { return arr[a] < arr; }
> const T arr;
> };

Maybe class index_cmp could hold a const reference rather than an
object (ie. change const T arr to const T& arr). Saves unnecessary
copying.

> sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));

You can provide rename index_cmp to index_cmp_t and provide an inline
function

template <class Container>
inline
index_cmp_t<Container>
index_cmp(const Container& c)
{
return index_cmp_t<Container>(c);
}

This prevents the need to explicitly qualify template parameters in
the code.

Siemel Naran, May 21, 2004
7. ### Jeff FlinnGuest

"b83503104" <> wrote in message
news:...
> In matlab, the sort function returns two things:
>
> [a,b]=sort([5, 8, 7])
>
> a = 5 7 8
> b = 1 3 2
>
> where a is the sorted result, and b is the corresponding index.
> Is there C++ code available to achieve this?
> Better compatible with STL vector.
> Thanks

Try the following untested code after installing boost from www.boost.org.

#include <map>
#include <boost/bind.hpp>
#include <boost/iterator/counting_iterator.hpp>

typedef std::map<int,int> tMap; // <data,index>

tMap Map;

int Data[] = { 5, 8, 7 };

std::transform( &data[0], &data[3]
, boost::counting_iterator<int>(1)
, std::inserter<tMap>(Map)
, boost::bind( std::make_pair<int,int>, _1, _2 )
);

for( tMap::const_iterator lItr = Map.begin() ; lItr != Map.end() ; ++lItr )
{
std::cout << "Data Value: " << lItr->first
<< " At Index: " << lItr->second;
}

Jeff F

Jeff Flinn, May 21, 2004
8. ### MeGuest

> Maybe class index_cmp could hold a const reference rather than an
> object (ie. change const T arr to const T& arr). Saves unnecessary
> copying.
>
> > sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));

It does hold a const reference (notice the '&' at the call to sort). I
did it this way because doing it the way I would do in real life (add
a reference only if T isn't a pointer or a reference) requires a lot
more code or a dependency on boost's type_traits (which will hopefully
be added to the next standard).

Me, May 22, 2004
9. ### Siemel NaranGuest

(Me) wrote in message

> > Maybe class index_cmp could hold a const reference rather than an
> > object (ie. change const T arr to const T& arr). Saves unnecessary
> > copying.
> >
> > > sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));

>
> It does hold a const reference (notice the '&' at the call to sort). I
> did it this way because doing it the way I would do in real life (add
> a reference only if T isn't a pointer or a reference) requires a lot
> more code or a dependency on boost's type_traits (which will hopefully
> be added to the next standard).

Good point, sorry missed it.

Siemel Naran, May 22, 2004