The right way to check if the container .at () implements the access / std :: sort compatible member

Question

I am looking for the best / right way to determine if a container implements access to random elements via .at() . In a scenario where different (stl) containers should be sorted relative to each other (say, sorting a container std::vector<int> , relative to std::vector<double> ), I do something like 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 in a template function, but I don’t know how to best restrict or check containers that have random access iterators /.at () (when they do not, something expensive has to be done).

I have it

 #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'm interested in any type of container, not just STL. My example used STL containers for convenience and reproducibility.

Answer 1

In principle, this is not the right approach in which general algorithms should be implemented . iterator s and std::iterator_traits usually used to determine the base type and allowed operations. If you want to execute a different algorithm (with a different complexity) based on which interface the container provides (random access, non-random access), you should do what follows.

First of all, your general algorithm should work on ranges, not containers. That is, it should look like any of the <algorithm> functions:

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

Secondly, you must write helper functions that use a different sorting method to make the most of the container interface in order 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 actually redirect the iterators only to the corresponding helper function, based on the type of 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 the 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 types of type C ++ 11, then in C ++ 03 you can define the following:

 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 decisions based on compilation based on this, you can use the SFINAE expression 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, to verify the existence of a member function of a given signature, a handwritten attribute is required:

 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); }; 

which can be used in 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

Answer 2

You can do something like the following

 namespace detail { template<typename T> decltype(std::declval<T>().at(0), std::true_type{}) has_at(int); template<typename T> std::false_type has_at(...); } // traits to detect if T::at(int) is valid template<typename T> struct has_at : public decltype(detail::has_at<T>(0)) {}; template<typename T, typename U> typename std::enable_if<has_at<U>::value>::type 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);}); } 

And then you can implement an alternative function if !has_at<U>::value :

 template<typename T, typename U> typename std::enable_if<!has_at<U>::value>::type sorty(T& a, U const x) { // Alternative implementation }