Pull to refresh

Концептуальная сортировка в С++20

Reading time 7 min
Views 11K

К изменениям лучше готовиться заранее, поэтому предлагаю посмотреть на то, что войдет в стандарт C++20, а именно на концепции.


Статус концепций


Сейчас концепции имеют статус технической спецификации(TS: technical specification): документ их описывающий ISO/IEC TS 19217:2015. Такие документы нужны, чтобы перед принятием нововведений в стандарт языка, эти нововведения были опробованы и скорректированы сообществом С++. Компилятор gcc поддерживает техническую спецификацию концепций в экспериментальном режиме с 2015 года.


Стоит заметить, что концепции из технической спецификации и концепции из текущего черновика С++20 различаются, но не сильно. В статье рассматривается вариант технической спецификации.


Теория


Шаблоны классов и функций могут быть связаны с ограничениями. Ограничения накладывают требования на аргументы шаблона. Концепции это именованные наборы таких ограничений. Каждая концепция является булевой функцией(предикатом), проверяющей эти ограничения. Проверка производится на этапе компиляции при инстацировании шаблона связанного с концепцией или ограничением. Если такая проверка не проходит, то компилятор укажет какой аргумент шаблона провалил проверку какого ограничения.


Практика


Теперь когда понятны смысл и назначение концепций можно рассмотреть синтаксис. Определения концепций имеют две формы: переменной и функции. Нас будет интересовать форма переменной. Она очень похожа на определение обычной шаблонной переменной, но с ключевым словом concept.


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

Вместо комментария нужно написать constexpr выражение, которое приводится к bool. Это выражение и есть ограничение на аргумента шаблона. Что бы ограничить шаблон концепцией, нужно вместо typename(или class) использовать её название.


Например, для целых чисел:


// (На момент написания статьи подсветка синтаксиса не работала для
//  ключевых слов связанных с концепциями)
#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)
                          */
}

Можно ставить более сложные ограничения, используя требование-выражение(requires-expression). Требование-выражение умеет проверять правильность(well-formed) выражения, возвращаемое значение выражения, наличие типов. Синтаксис хорошо разобран тут.


#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 ) не выполнено.
                           */
}

Сортировка


Как же концепции помогут в написании сортировки? Сам алгоритм останется неизменным, но шаблон сортировки можно улучшить с помощью концепций. Рассмотрим такой пример:


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

Ошибка заключается, в том что у структуры NonComparable нет операции сравнения. Представляете как будет выглядеть ошибка компилятора? Если нет, то загляните под спойлер.


gcc(7.2.1) CentOS
[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; }
                ~~~~~~~^~~~~~~~
и т.д.

Такая маленькая ошибка в коде и такая большая у компилятора. Абыдно, да!?


Такие ошибки можно сократить с помощью концепций, для этого напишем враппер их использующий. Сортировка принимает итераторы, поэтому нужно написать концепцию Сортируемый итератор. Для такого итератора, нужно несколько концепций поменьше. Например, сравнимый объект(приведен выше), обмениваемый объект:


template<typename T>
concept bool MySwappable = requires (T a, T b) {
    std::swap(a, b); // Можно обменивать
};

перемещаемый объект


template<typename T>
concept bool MyMovable = requires (T a) {
    T (std::move(a)); // Можно конструировать перемещением
    a = std::move(a);  // Можно присваивать перемещением

};

итератор случайного доступа


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; // Можно разыменовать
};

Когда все простые концепции готовы, можно определить составную концепцию Сортируемого итератора:


template<typename T>
concept bool MySortableIterator =
    MyRAIterator<T> &&                       // Итератор случайного доступа
    MyMovable<typename T::value_type> &&     // Перемещаемый объект
    MyComparable<typename T::value_type> &&  // Сравнимый объект
    MySwappable<typename T::value_type>;     // Обмениваемый объект

С его помощью пишется враппер:


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

Если вызывать "концептуальную" сортировку с несравниваемым объектом,


struct NonComparable {};

int main () {
    std::vector<NonComparable> vector = {{}, {}, {}, {}, {}, {}, {}, {}};
    conceptualSort (vector.begin(), vector.end()); // Ошибка
}

то ошибка компиляции будет занимает всего 16 строк:


gcc(7.2.1) CentOS
[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

Конечно, первые разы все равно не очень просто понять в чем ошибка, но после нескольких "концептуальных" ошибок они начинают читаться за несколько секунд.


Заключение


Конечно, сокращение длины ошибок не единственное преимущество нововведения. Шаблоны станут безопаснее благодаря ограничениям. Код станет более читаемым благодаря именнованным концепциям(самые часто используемые войдут в библиотеку). В целом С++ расширится в своей функциональной(шаблонной) части.

Tags:
Hubs:
+29
Comments 106
Comments Comments 106

Articles