Conceptual sorting in C ++ 20

It is better to prepare for changes in advance, so I suggest looking at what will be included in the C ++ 20 standard, namely, on concepts .

Concept Status

Now concepts have the status of a technical specification ( TS: technical specification ): a document describing ISO / IEC TS 19217: 2015 . Such documents are needed so that before adopting innovations in the language standard, these innovations are tested and adjusted by the C ++ community. The gcc compiler has been supporting experimental concept technical specifications since 2015.

It is worth noting that the concepts from the technical specifications and the concepts from the current draft C ++ 20 are different, but not much. The article discusses the option of technical specifications.

Theory

Class and function templates may be subject to restrictions . Restrictions impose requirements on template arguments. Concepts are named sets of such constraints. Each concept is a Boolean function ( predicate ) that tests these constraints. The check is performed at the compilation stage when the template associated with the concept or constraint is installed. If such a check fails, the compiler will indicate which template argument failed to check which constraint.

Practice

Now that the meaning and purpose of the concepts are clear, we can consider the syntax. Concept definitions have two forms: variable and function. We will be interested in the form of the variable. It is very similar to the definition of a regular template variable, but with the concept keyword.

template<typename T> concept bool MyConcept = /* ... */; 

Instead of a comment, you need to write constexpr expression, which is given to bool. This expression is a constraint on the template argument. To limit a template to a concept, you need to use its name instead of typename (or class).

For example, for integers:

 // (         //     ) #include <type_traits> template<typename T> //    concept bool MyIntegral = std::is_integral<T>::value; //template <typename T> template<MyIntegral T> bool compare (T a, T b) { return a < b; } void foo () { compare (123u, 321u); /// OK compare (1.0, 2.0); /** :    MyIntegral (std::is_integral<double>::value = false) */ } 

You can set more complex restrictions using the requirement-expression ( requires-expression ). An expression request can verify the correctness ( well-formed ) of an expression, the return value of an expression, the presence of types. The syntax is well understood here .

 #include <unordered_set> #include <vector> template<typename T> concept bool MyComparable = requires (T a, T b) { a < b; /// ,     { a < b } -> bool; /// ,      bool }; template<MyComparable T> bool compare (T a, T b) { return a < b; } void foo () { std::vector<int> vecA = {1, 2, 3}, vecB = {1, 2, 4}; std::unordered_set<int> setA = {1, 2, 3}, setB = {1, 2, 4}; compare (vecA, vecB); /// OK compare (setA, setB); /**    MyComparable std::unordered_set    .  ( a < b )  . */ } 

Sorting

How can concepts help in writing sorting? The algorithm itself will remain unchanged, but the sorting pattern can be enhanced with concepts. Consider this example:

 #include <algorithm> struct NonComparable {}; int main () { std::vector<NonComparable> vector = {{}, {}, {}, {}, {}, {}, {}, {}}; std::sort (vector.begin(), vector.end()); //  } 

The error is that the NonComparable structure does not have a comparison operation. Imagine what a compiler error will look like? If not, look under the spoiler.

 [username@localhost concepts]$ g++ -std=c++17 main.cpp In file included from /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algobase.h:71:0, from /opt/rh/devtoolset-7/root/usr/include/c++/7/vector:60, from main.cpp:1: /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >; _Iterator2 = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >]': /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algo.h:81:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]' /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algo.h:1921:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]' /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algo.h:1953:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]' /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algo.h:1968:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]' /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >]' main.cpp:6:44: required from here /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'NonComparable' and 'NonComparable') { return *__it1 < *__it2; } ~~~~~~~^~~~~~~~ In file included from /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algobase.h:67:0, from /opt/rh/devtoolset-7/root/usr/include/c++/7/vector:60, from main.cpp:1: /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&) operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, ^~~~~~~~ /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed: In file included from /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/stl_algobase.h:71:0, from /opt/rh/devtoolset-7/root/usr/include/c++/7/vector:60, from main.cpp:1: /opt/rh/devtoolset-7/root/usr/include/c++/7/bits/predefined_ops.h:43:23: note: 'NonComparable' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>' { return *__it1 < *__it2; } ~~~~~~~^~~~~~~~  .. 

Such errors can be reduced using concepts, for this we write a wrapper using them. Sorting takes iterators, so you need to write the concept of an sortable iterator. For such an iterator, you need a few smaller concepts. For example, a comparable object (shown above), an exchangeable object:

 template<typename T> concept bool MySwappable = requires (T a, T b) { std::swap(a, b); //   }; 

moving object

 template<typename T> concept bool MyMovable = requires (T a) { T (std::move(a)); //    a = std::move(a); //    }; 

random access iterator

 template<typename T> concept bool MyRAIterator = requires (T it) { typename T::value_type; //       it++; //     Random Access  it--; it += 2; it -= 2; it = it + 2; it = it - 2; { *it } -> typename T::value_type; //   }; 

When all the simple concepts are ready, you can define the composite concept of the Sortable Iterator:

 template<typename T> concept bool MySortableIterator = MyRAIterator<T> && //    MyMovable<typename T::value_type> && //   MyComparable<typename T::value_type> && //   MySwappable<typename T::value_type>; //   

With it, a wrapper is written:

 template<MySortableIterator T> void conceptualSort (T begin, T end) { std::sort (begin, end); } 

If you call a "conceptual" sort with an incomparable object,

 struct NonComparable {}; int main () { std::vector<NonComparable> vector = {{}, {}, {}, {}, {}, {}, {}, {}}; conceptualSort (vector.begin(), vector.end()); //  } 

then the compilation error will take only 16 lines:

 [markgrin@localhost concepts]$ g++ -std=c++17 -fconcepts main.cpp main.cpp: In function 'int main()': main.cpp:49:49: error: cannot call function 'void conceptualSort(T, T) [with T = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >]' conceptualSort (vector.begin(), vector.end()); ^ main.cpp:41:6: note: constraints not satisfied void conceptualSort (T begin, T end) { ^~~~~~~~~~~~~~ main.cpp:36:14: note: within 'template<class T> concept const bool MySortableIterator<T> [with T = __gnu_cxx::__normal_iterator<NonComparable*, std::vector<NonComparable> >]' concept bool MySortableIterator = MyRAIterator<T> && MyMovable<typename T::value_type> && ^~~~~~~~~~~~~~~~~~ main.cpp:12:14: note: within 'template<class T> concept const bool MyComparable<T> [with T = NonComparable]' concept bool MyComparable = requires (T a, T b) { ^~~~~~~~~~~~ main.cpp:12:14: note: with 'NonComparable a' main.cpp:12:14: note: with 'NonComparable b' main.cpp:12:14: note: the required expression '(a < b)' would be ill-formed 

Of course, the first times it is still not very easy to understand what the error is, but after several "conceptual" errors, they begin to be read in a few seconds.

Conclusion

Of course, reducing the length of errors is not the only advantage of innovation. Patterns will be safer due to limitations . The code will become more readable thanks to the named concepts (the most frequently used ones will be included in the library ). In general, C ++ will expand in its functional (template) part.