General/interface/precomputed_value_sort.h

0001 #ifndef precomputed_value_sort_H
0002 #define precomputed_value_sort_H
0003
0004 /** \file precomputed_value_sort.h
0005  *  Sort using precomputed values.
0006  *
0007  *  precomputed_value_sort behaves like std::sort, but pre-computes the
0008  *  values used in the sorting using an Extractor, so that the computation
0009  *  is performed only once per element.
0010  */
0011
0012 #include <vector>
0013 #include <algorithm>
0014 #include <functional>
0015
0016 template <class RandomAccessIterator, class Extractor, class Compare>
0017 void precomputed_value_sort(RandomAccessIterator begin,
0018                             RandomAccessIterator end,
0019                             const Extractor& extr,
0020                             const Compare& comp) {
0021   using Value = typename std::iterator_traits<RandomAccessIterator>::value_type;
0022   using Scalar = decltype(extr(*begin));
0023
0024   std::vector<std::pair<RandomAccessIterator, Scalar>> tmpvec;
0025   tmpvec.reserve(end - begin);
0026
0027   // tmpvec holds iterators - does not copy the real objects
0028   for (RandomAccessIterator i = begin; i != end; i++)
0029     tmpvec.emplace_back(i, extr(*i));
0030
0031   std::sort(tmpvec.begin(), tmpvec.end(), [&comp](auto const& a, auto const& b) { return comp(a.second, b.second); });
0032
0033   // overwrite the input range with the sorted values
0034   // copy of input container not necessary, but tricky to avoid
0035   std::vector<Value> tmpcopy(begin, end);
0036   for (unsigned int i = 0; i < tmpvec.size(); i++) {
0037     *(begin + i) = std::move(tmpcopy[tmpvec[i].first - begin]);
0038   }
0039 }
0040
0041 template <class RandomAccessIterator, class Extractor>
0042 void precomputed_value_sort(RandomAccessIterator begin, RandomAccessIterator end, const Extractor& extr) {
0043   using Scalar = decltype(extr(*begin));
0044   precomputed_value_sort(begin, end, extr, std::less<Scalar>());
0045 }
0046
0047 #endif