By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,148 Members | 1,339 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,148 IT Pros & Developers. It's quick & easy.

sort and get index?

P: n/a
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
Jul 22 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
"b83503104" <b8*******@yahoo.com> 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
Jul 22 '05 #2

P: n/a
Me
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[b]; }
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.
Jul 22 '05 #3

P: n/a
b8*******@yahoo.com (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[i];
cout << "(" << *p << "," << p-start << " ";
}
Jul 22 '05 #4

P: n/a
b8*******@yahoo.com (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[i];
cout << "(" << *p << "," << p-start << " ";
}
Jul 22 '05 #5

P: n/a
an*****************@yahoo.com (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[b]; }
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.
Jul 22 '05 #6

P: n/a

"b83503104" <b8*******@yahoo.com> wrote in message
news:73**************************@posting.google.c om...
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
Jul 22 '05 #7

P: n/a
Me
> 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).
Jul 22 '05 #8

P: n/a
an*****************@yahoo.com (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.
Jul 22 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.