Sort any container

Question

I have a function, that takes a std container and operates on it. Somewhere in the process, the container items need to be sorted. Now, the sorting of std::vector and std::list cause me headache. How would I unify the process?
Here's an example that yields both errors:

#include <vector>
#include <list>
#include <algorithm>

template <class C> void foo(C& container){
    // this one works for std::vector
    std::sort(container.begin(), container.end(), [](auto&a, auto&b){return a<b;});
    
    // this one works for the list
    container.sort();
}

int main()
{
    std::list<int> a{0,3,1,2};
    std::vector<int> b{0,3,1,2};
    foo(a);
    foo(b);
    return 0;
}

Errors are:

• std::vector has no sort function:

main.cpp: In instantiation of ‘void foo(C&) [with C = std::vector<int>]’:
main.cpp:18:8:   required from here
   18 |     foo(b);
      |     ~~~^~~
main.cpp:10:15: error: ‘class std::vector’ has no member named ‘sort’
   10 |     container.sort();
      |     ~~~~~~~~~~^~~~

• list::iterator has no - operator to calculate a distance.

In file included from /usr/include/c++/14/algorithm:61,
                 from main.cpp:3:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of ‘constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = _List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<foo<std::__cxx11::list<int> >(std::__cxx11::list<int>&)::<lambda(auto:9&, auto:10&)> >]’:
/usr/include/c++/14/bits/stl_algo.h:4804:18:   required from ‘constexpr void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = _List_iterator<int>; _Compare = foo<std::__cxx11::list<int> >(std::__cxx11::list<int>&)::<lambda(auto:9&, auto:10&)>]’
 4804 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:7:14:   required from ‘void foo(C&) [with C = std::__cxx11::list]’
    7 |     std::sort(container.begin(), container.end(), [](auto&a, auto&b){return a<b;});
      |     ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:17:8:   required from here
   17 |     foo(a);
      |     ~~~^~~
/usr/include/c++/14/bits/stl_algo.h:1906:50: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator’ and ‘std::_List_iterator’)
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67,
                 from /usr/include/c++/14/vector:62,
                 from main.cpp:1:
/usr/include/c++/14/bits/stl_iterator.h:618:5: note: candidate: ‘template constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)’
  618 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:618:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algo.h:1906:50: note:   ‘std::_List_iterator’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1789:5: note: candidate: ‘template constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
 1789 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1789:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algo.h:1906:50: note:   ‘std::_List_iterator’ is not derived from ‘const std::move_iterator<_IteratorL>’
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~

Answer 1

You can use if constexpr together with a requires expresion to use the container's sorting method if it's available (assuming if it exists it is the best for this container), and otherwise attempt to use std::sort.

This works because if constexpr is resolved at compile time, and it can be done so because the requires expression yields a compile time boolean value.

#include <vector>
#include <list>
#include <algorithm>

template <class C> void foo(C& container) {
    if constexpr (requires { container.sort(); }) {
        // Prefer a container's sort method:
        container.sort();
    }
    else {
        // Attempt to use std::sort otherwise:
        std::sort(container.begin(), container.end(), [](auto& a, auto& b) {return a < b; });
    }
}

int main() {
    std::list<int> a{ 0,3,1,2 };
    std::vector<int> b{ 0,3,1,2 };
    foo(a);
    foo(b);
}

Live demo - Godbolt

Note that this can still theoretically fail compilation for a container that doesn't have a sort method and also doesn't support std::sort.
As @LHLaurini commented below there are such containers (std::set, std::map), but there's no reason or need to sort them because they are sorted by nature.

Answer 2

You can also use template specialization.

First, you define a generic mysort function that uses std::sort

template <class C>
void mysort (C& container)  {
    std::sort(container.begin(), container.end(), [](auto&a, auto&b){return a<b;});
}

Then, you can specialize mysort for containers that has a sort member function. This can be done easily with concepts (starting with c++20)

template<class C>
requires requires(C& c) { c.sort(); }
void mysort (C& container)  {
    container.sort();
}

Template specialization can go further if you introduce later a custom container class such as (or if you have to deal with some legacy implementation)

template<typename T>
struct MyList  {
    void sort_optim () {}
};

In such a case, you also provide a specialization for mysort

template<typename T>
void mysort (MyList<T>& container)  {
    container.sort_optim();
}

The advantages:

1. each version of the mysort function deals with only one processing in mind, i.e. there is no monolithic function holding every case (I agree it's not too complex for this use case though...)

2. you don't have to modify the generic and the first specialization of mysort with the introduction of a new type like MyList

Demo