Correct way to test if a container implements .at() member access / std::sort compatible

Question

I am looking for the best/correct way to determine if a container implements random element access via .at(). In the scenario where different (stl) containers are to be sorted relative to each other (say sorting a container std::vector<int>, relative to std::vector<double>), I do something this:

std::sort(toOrder.begin(), toOrder.end(), [&orderBy](int i, int j) -> bool {
    return orderBy.at(i) > orderBy.at(j);
});

where

std::vector<int> toOrder;
std::vector<double> orderBy

I can wrap this up in a template function, but am unsure of the best way to restrict, or test for, containers having random access iterators/.at() (when they do not, something expensive will need to be done).

I have this

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

template <typename T, typename U>
void sorty(T& a, U const x) {
    std::sort(a.begin(), a.end(),
              [&x](int i, int j) -> bool { return x.at(i) > x.at(j); });
}

int main() {

    std::vector<int> toOrder(10);
    std::iota(toOrder.begin(), toOrder.end(), 0);
    std::vector<double> orderBy{0.2, 9.8,  4.0,  0.01,  15.1,
                                3.3, 9.01, 9.11, 100.1, 2.03};

    std::unordered_set<double> orderBy_s(orderBy.begin(),
                                         orderBy.end()); // no .at()

    sorty(toOrder, orderBy);

    for (auto i : toOrder) {
        std::cout << i << "\t";
    }

    return 0;
}

demo code here

UPDATE: I hastily posted without editing the title. I am concerned with any container type, not just STL. My example used STL containers for convenience and reproducibility.

Answer 1

Basically, this is not the proper approach in which generic algorithms should be implemented. Usually, one would use iterators and std::iterator_traits to determine the underlying type and allowed operations. If you want to execute a different algorithm (with a different complexity) based on what interface the container provides (random access, non-random access), you should do what follows.

First of all, your generic algorithm should operate on ranges rather than containers. That is, this should look like any of <algorithm>'s functions:

template <typename Iterator>
void sorty(Iterator first, Iterator last);

Secondly, you should write helper functions that apply a different sorting method to utilize the interface of a container as much as possible, so as to work in the most efficient way:

// O(N*lgN) complexity sorting
template <typename Iterator>
void sorty_helper(Iterator first, Iterator last,
                  std::random_access_iterator_tag);

// O(N*N) complexity sorting
template <typename Iterator>
void sorty_helper(Iterator first, Iterator last,
                  std::forward_iterator_tag);

Now, your original sorty function should in fact only forward iterators to an appropriate helper function, based on the type of the iterator obtained through std::iterator_traits:

template <typename Iterator>
void sorty(Iterator first, Iterator last)
{
    sorty_helper(first, last,
                 typename std::iterator_traits<Iterator>::iterator_category());
}

DEMO 1

An alternative approach would be to enable/disable function templates using a SFINAE technique:

#include <iterator>
#include <type_traits>    

template <typename Iterator>
typename std::enable_if<
    std::is_same<typename std::iterator_traits<Iterator>::iterator_category, std::random_access_iterator_tag>::value
    >::type
    sorty(Iterator first, Iterator last)
{
    // O(N*lgN) complexity sorting
}

template <typename T> struct AlwaysFalse : std::false_type {};

template <typename Iterator>
typename std::enable_if<
    !std::is_same<typename std::iterator_traits<Iterator>::iterator_category, std::random_access_iterator_tag>::value
    >::type
    sorty(Iterator first, Iterator last)
{
    // other sorting algorithm or print out a user-friendly error
    static_assert(AlwaysFalse<Iterator>{}, "Iterator must be a random-access iterator!");
}

DEMO 2

Where enable_if and is_same are C++11's type traits, that in C++03 can be defined as follows:

template <bool b, typename T = void>
struct enable_if {};
template <typename T>
struct enable_if<true, T> { typedef T type; };
template <typename T, typename U>
struct is_same { static const bool value = false; };
template <typename T, typename U>
const bool is_same<T, U>::value;
template <typename T>
struct is_same<T, T> { static const bool value = true; };
template <typename T>
const bool is_same<T, T>::value;

If, on the other hand, you want to check only the existence of the at member function, and make compile-time decisions based on that, you might want to use an expression SFINAE technique:

template <typename Container>
auto sorty_helper(Container&& container, int)
    -> decltype(void(std::forward<Container>(container).at(0)))
{
    // O(N*lgN) complexity sorting
}

template <typename Container>
void sorty_helper(Container&& container, void*)
{
    // O(N*N) complexity sorting
}

template <typename Container>
void sorty(Container&& container)
{
    sorty_helper(std::forward<Container>(container), 0);
}

DEMO 3

In C++03, verifying the existence of a member function of a given signature requires a hand-written trait:

template <typename T>
struct has_at
{
    typedef char (&yes)[1];
    typedef char (&no)[2];

    template <typename U, U u>
    struct SFINAE {};

    template <typename U>
    static yes test(SFINAE<typename U::reference(U::*)(std::size_t), &U::at>*);

    template <typename U>
    static no test(...);

    static const bool value = sizeof(test<T>(0)) == sizeof(yes);
};

that can be used in a combination with enable_if:

template <bool b, typename T = void>
struct enable_if {};

template <typename T>
struct enable_if<true, T> { typedef T type; };

template <typename Container>
typename enable_if<has_at<Container>::value>::type
    sorty(Container& container)
{
    // O(N*lgN) complexity sorting
}

template <typename Container>
typename enable_if<!has_at<Container>::value>::type
    sorty(Container& container)
{
    // O(N*N) complexity sorting
}

DEMO 4