Conceptual sorting in C ++ 20
It is better to prepare for changes in advance, so I suggest looking at what will go into the C ++ 20 standard, namely the concept .
Concept Status
Nowadays, concepts have the status of a technical specification ( TS: technical specification ): a document describing them ISO / IEC TS 19217: 2015 . Such documents are needed so that before adopting innovations in the language standard, these innovations should be tested and adjusted by the C ++ community. The gcc compiler has supported the technical specification of concepts in experimental mode since 2015.
It is worth noting that the concepts from the technical specification and the concepts from the current draft C ++ 20 differ, but not much. The article discusses a variant of the technical specification.
Theory
Class and function templates may be subject to restrictions . Constraints impose requirements on template arguments. Concepts are named sets of such constraints. Each concept is a Boolean function ( predicate ) that tests these constraints. Verification is performed at the compilation stage when installing a template associated with a concept or restriction. If such a check fails, then the compiler will indicate which template argument failed the check of which constraint.
Practice
Now that you understand the meaning and purpose of the concepts, you can consider the syntax. Concept definitions take 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
concept bool MyConcept = /* ... */;
Instead of a comment, you need to write a constexpr expression that is cast to bool. This expression is the restriction on the template argument. To limit the template to a concept, you need to use its name instead of typename (or class).
For example, for integers:
// (На момент написания статьи подсветка синтаксиса не работала для
// ключевых слов связанных с концепциями)
#include
template // концепция целых чисел
concept bool MyIntegral = std::is_integral::value;
//template
template
bool compare (T a, T b) {
return a < b;
}
void foo () {
compare (123u, 321u); /// OK
compare (1.0, 2.0); /** ОШИБКА: нарушение ограничений концепции MyIntegral
(std::is_integral::value = false)
*/
}
You can put more complex constraints, using demand-expression ( the requires-expression ). The requirement-expression can verify the well-formed expression, the return value of the expression, the presence of types. The syntax is well understood here .
#include
#include
template
concept bool MyComparable = requires (T a, T b) {
a < b; /// Проверяем, что такое выражение правильно
{ a < b } -> bool; /// Проверяем, что сравнение приводится к типу bool
};
template
bool compare (T a, T b) {
return a < b;
}
void foo () {
std::vector vecA = {1, 2, 3}, vecB = {1, 2, 4};
std::unordered_set 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 improved with concepts. Consider this example:
#include
struct NonComparable {};
int main () {
std::vector vector = {{}, {}, {}, {}, {}, {}, {}, {}};
std::sort (vector.begin(), vector.end()); // Ошибка
}
The error is that the NonComparable structure does not have a comparison operation. Can you imagine what the 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 >; _Iterator2 = __gnu_cxx::__normal_iterator >]’:
/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 >; _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 >; _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 >; _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 >; _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 >]’
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 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 a small error in the code, and so large in the compiler. Abydny, yes !?
Such errors can be reduced with the help of concepts, for this we will write a wrapper using them. Sorting takes iterators, so you need to write the concept of Sortable iterator. For such an iterator, you need a few smaller concepts. For example, a comparable object (shown above), an exchanged object:
template
concept bool MySwappable = requires (T a, T b) {
std::swap(a, b); // Можно обменивать
};
roaming object
template
concept bool MyMovable = requires (T a) {
T (std::move(a)); // Можно конструировать перемещением
a = std::move(a); // Можно присваивать перемещением
};
random access iterator
template
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
concept bool MySortableIterator =
MyRAIterator && // Итератор случайного доступа
MyMovable && // Перемещаемый объект
MyComparable && // Сравнимый объект
MySwappable; // Обмениваемый объект
Using it, a wrapper is written:
template
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 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 >]’
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 concept const bool MySortableIterator [with T = __gnu_cxx::__normal_iterator >]’
concept bool MySortableIterator = MyRAIterator && MyMovable &&
^~~~~~~~~~~~~~~~~~
main.cpp:12:14: note: within ‘template concept const bool MyComparable [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 time it’s still not very easy to understand what the error is, but after a few “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 the innovation. Templates will be safer due to restrictions . The code will become more readable thanks to named concepts (the most frequently used ones will be included in the library ). In general, C ++ will expand in its functional (template) part.