3
\$\begingroup\$

I've just asked

What's the idiomatic way to get the sort order of data, without actually applying it?

(or see the original it was found to be a dupe on). So, I want to implement properly what seems to be the only suggested option - generating an array of indices and sorting it by the original data's relative order. Here's my code (ignoring includes):

template<typename RAIterator, typename Comparator, typename Size = size_t>
inline std::vector<Size>
sorted_indices(RAIterator first, RAIterator last, Comparator comparator)
{
    std::vector<Size> result(last - first);
    std::iota(result.begin(), result.end(), 0);
    auto adapted_comparator = [&first, comparator](Size lhs, Size rhs) {
        return comparator(first[lhs], first[rhs]);
    };
    std::sort(result.begin(), result.end(), adapted_comparator);
    return result;
}

template<typename RAIterator, typename Size = size_t>
inline std::vector<Size>
sorted_indices(RAIterator first, RAIterator last)
{
    using value_type = typename std::iterator_traits<RAIterator>::value_type;
    auto comparator = [](const value_type& lhs, const value_type& rhs) { return lhs < rhs; };
    return sorted_indices<RAIterator, decltype(comparator), Size>(first, last, comparator);
}

template<typename Container, typename Comparator, typename Size = typename Container::size_type>
inline std::vector<Size> sorted_indices(Container& container, Comparator comparator)
{
    return sorted_indices<typename Container::const_iterator, Size>(
        std::begin(container), std::end(container), comparator);
}

template<typename Container, typename Size = typename Container::size_type>
inline std::vector<Size> sorted_indices(Container& container)
{
    return sorted_indices<typename Container::const_iterator, Size>(
        std::begin(container), std::end(container));
}

Have I covered all my bases or is there something I might be missing? Also, how legitimate is it to return the vector of indices?

\$\endgroup\$
1
\$\begingroup\$

Two thing I noticed I can do are:

  • use std::less<T> as a default comparator class
  • set a default value for the comparator parameter, using the default initializer of the comparator class

The combination of these two cuts code length by half without reducing legibility (!):

template<
    typename RAIterator, 
    typename Size = size_t, 
    typename Compare = std::less<typename std::iterator_traits<RAIterator>::value_type>
>
inline std::vector<Size>
sorted_indices(RAIterator first, RAIterator last, Compare compare = Compare())
{
    std::vector<Size> result(last - first);
    std::iota(result.begin(), result.end(), (Size) 0);
    auto lookup_and_compare = [&first, compare](Size lhs, Size rhs) {
        return compare(first[lhs], first[rhs]);
    };
    std::sort(result.begin(), result.end(), lookup_and_compare);
    return result;
}

template<
    typename Container,
    typename Size = typename Container::size_type,
    typename Compare = std::less<typename Container::value_type>
>
inline std::vector<Size> sorted_indices(Container& container, Compare compare = Compare())
{
    return sorted_indices<typename Container::const_iterator, Size>(
        std::begin(container), std::end(container), compare);
}

The downside is that you must then depend on <iterator> and <functional>; since I use them already for other things, I don't really mind.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.