Geek Answers Handbook

Does STL or BOOST provide any clean way to get the sort order without reordering the original sequence?

I would like to find the sort order of the vector, for example, without reordering the vector.

I can come up with several ways to do this, I'm wondering if I lack some of the built-in STL or BOOST ways to do this.

I assume that if the functionality was available, the code would end up looking something like this:

std::vector<float> unsortedSeq; unsortedSeq.push_back( 1.1 ); unsortedSeq.push_back( 1.0 ); unsortedSeq.push_back( 0.5 ); unsortedSeq.push_back( 1.2 ); unsortedSeq.push_back( 1.15 ); std::list<std::size_t> sortOrder; std::sort_indices( unsortedSeq.begin(), unsortedSeq.end(), sortOrder.begin() ); BOOST_FOREACH( std::size_t index, sortOrder ) { std::cout << index << "\n" } 2 1 0 4 3

Does anyone know of any STL or BOOST sims that will do what I ask for, as simple as shown?

+4
source share
5 answers

You would do something like this:

 template<typename T> class SortOrder { public: SortOrder(const std::vector<T> *_sortArray) : sortArray(_sortArray) {;} bool operator()(int lhs, int rhs) const { return sortArray[lhs] < sortArray[rhs]; } private: const std::vector<T> *sortArray; }; //To do the sorting: #include <boost/range/counting_range.hpp> auto countRange = boost::range::counting_range(0, myListOfStuff.size()); //Build a vector<int> that has one index for every value in your actual vector. vector<int> indexList(countRange.begin(), countRange.end()); std::sort(indexList.begin(), indexList.end(), SortOrder(&myListOfStuff));

This generates an index vector and then sorts them based on the actual material vector.

+4
source 
 std::vector<float> v; // filled somewhere else std::vector<std::size_t> indices(v.size()); // iota is from <numeric>, C++0x std::iota(indices.begin(), indices.end(), 0); std::sort(indices.begin(), indices.end(), [&v](std::size_t left, std::size_t right) { return v[left] < v[right]; });
+4
source

No; you have to do it yourself.

Fortunately, it's pretty simple! (which may therefore not be provided for)

  • Consider the input vector v
  • Create an index vector 0..n, where n is the size of your input v
  • std::sort an index vector containing a reference to input v and a custom comparator that returns v[left] < v[right] .
+2
source

Another example: boost::ref ...

 #include <algorithm> #include <iostream> #include <vector> #include <iterator> #include <boost/ref.hpp> int main() { int n[] = { 3, 4, 1, 7, 10 }; std::vector<int> v(n, n + 5); // print the original sequence std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // fill another vector with references to the data in the original std::vector<boost::reference_wrapper<int> > vp; std::transform(v.begin(), v.end(), std::back_inserter(vp), &boost::ref<int>); // sort the references std::sort(vp.begin(), vp.end()); // print the filtered version. std::copy(vp.begin(), vp.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // print the original sequence again to show it hasnt changed std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; }
+1
source

With just a few changes to Nicol Bolas's answer , this allows you to use any random access iterator as input (if it is a random iterator and has a reference ). A comparison function can also be provided (as in std::sort , by default it will be std :: less).

 template<typename const_iterator> class SortOrder { public: using Compare = std::function<bool(typename const_iterator::reference, typename const_iterator::reference)>; SortOrder(const_iterator to_sort, Compare comp = std::less<typename const_iterator::reference>()) : to_sort_(to_sort), comp_(comp) {} bool operator()(int lhs, int rhs) const { return comp_(*(to_sort_ + lhs), *(to_sort_ + rhs)); } private: const_iterator to_sort_; Compare comp_; }; vector<double> to_sort{1, 5, 9, 2, 6, 17, 2, 8.5}; // Create integers, one value for each to_sort element auto count_range = boost::counting_range(size_t(0), to_sort.size()); vector<int> indices(count_range.begin(), count_range.end()); // indices = 0 1 2 3 4 5 6 7 auto it = to_sort.begin(); sort(indices.begin(), indices.end(), SortOrder<decltype(it)>(it)); // indices = 0 3 6 1 4 7 2 5

A working example can be found here .

0
source

More articles:


All Articles