Function sortByComputedValue

source/core/StarAlgorithm.hpp:231–258

// must be constructable with Container(size_t).
template <typename Container, typename Getter>
void sortByComputedValue(Container& container, Getter&& valueGetter, bool stable = false) {
  typedef typename Container::value_type ContainerValue;
  typedef decltype(valueGetter(ContainerValue())) ComputedValue;
  typedef std::pair<ComputedValue, size_t> ComputedPair;

  size_t containerSize = container.size();

  if (containerSize <= 1)
    return;

  std::vector<ComputedPair> work(containerSize);
  for (size_t i = 0; i < containerSize; ++i)
    work[i] = {valueGetter(container[i]), i};

  auto compare = [](ComputedPair const& a, ComputedPair const& b) { return a.first < b.first; };

  // Sort the comptued values and the associated indexes
  if (stable)
    stableSort(work, compare);
  else
    sort(work, compare);

  Container result(containerSize);
  for (size_t i = 0; i < containerSize; ++i)
    swap(result[i], container[work[i].second]);

  swap(container, result);
}

template <typename Container, typename Getter>
void stableSortByComputedValue(Container& container, Getter&& valueGetter) {