File indexing completed on 2024-04-06 12:31:46
0001 #ifndef precomputed_value_sort_H
0002 #define precomputed_value_sort_H
0003
0004
0005
0006
0007
0008
0009
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
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
0034
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