Do you have some efficient routine for returning array with indices for sorted elements in a array? I think that some convenient way exists using stl vector
. Do you have already implemented an efficient algo without stl, or do you have a reference to pseudo code or C++ code?
26
votes
So you are returning an array containing indices to another array? And those indices will be ordered in your new array in a way it represents the older array sorted but without actually sorting it?
– Artie
4 Answers
40
votes
Using C++11, the following should work just fine:
template <typename T>
std::vector<size_t> ordered(std::vector<T> const& values) {
std::vector<size_t> indices(values.size());
std::iota(begin(indices), end(indices), static_cast<size_t>(0));
std::sort(
begin(indices), end(indices),
[&](size_t a, size_t b) { return values[a] < values[b]; }
);
return indices;
}
7
votes
You could try something like this:
template<typename C>
class index_sorter {
public:
compare(C const& c) : c(c) {}
bool operator()(std::size_t const& lhs, std::size_t const& rhs) const {
return c[lhs] < c[rhs];
}
private:
C const& c;
};
std::sort(index_vector.begin(), index_vector.end(), index_sorter(vector));
4
votes
Adding to @Konrad answer:
If for some reason you are not able to use C++11, then you can use boost::phoenix
to simulate it like
#include <vector>
#include <algorithm>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
template <typename T>
std::vector<size_t> ordered(std::vector<T> const& values)
{
using namespace boost::phoenix;
using namespace boost::phoenix::arg_names;
std::vector<size_t> indices(values.size());
int i = 0;
std::transform(values.begin(), values.end(), indices.begin(), ref(i)++);
std::sort(indices.begin(), indices.end(), ref(values)[arg1] < ref(values)[arg2]);
return indices;
}
2
votes
For C++03, I think this guru of the week can help you :
namespace Solution3
{
template<class T>
struct CompareDeref
{
bool operator()( const T& a, const T& b ) const
{ return *a < *b; }
};
template<class T, class U>
struct Pair2nd
{
const U& operator()( const std::pair<T,U>& a ) const
{ return a.second; }
};
template<class IterIn, class IterOut>
void sort_idxtbl( IterIn first, IterIn last, IterOut out )
{
std::multimap<IterIn, int, CompareDeref<IterIn> > v;
for( int i=0; first != last; ++i, ++first )
v.insert( std::make_pair( first, i ) );
std::transform( v.begin(), v.end(), out,
Pair2nd<IterIn const,int>() );
}
}
#include <iostream>
int main()
{
int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };
std::cout << "#################" << std::endl;
std::vector<int> aidxtbl( 10 );
// use another namespace name to test a different solution
Solution3::sort_idxtbl( ai, ai+10, aidxtbl.begin() );
for( int i=0; i<10; ++i )
std::cout << "i=" << i
<< ", aidxtbl[i]=" << aidxtbl[i]
<< ", ai[aidxtbl[i]]=" << ai[aidxtbl[i]]
<< std::endl;
std::cout << "#################" << std::endl;
}
The original article is here.