Concept для контейнеров/алгоритмов.

d-yaroshev
d-yaroshev

В качестве точки отсчета предлагаю посмотреть на Elements Of Programming (EoP) в которой вводится несколько concepts, например регулярный тип. Похоже, что понятие регулярного типа в том же смысле, в котором оно было в EoP сейчас в целом принято сообществом.
Идейно Regular означает следующее: у нас есть множество (в математическом смысле) всех возможных значений типа, и объект соответсвует одному из них. Из этого следует семантика равенства: два регулярных объекта равны, если они соотвтествуют одному и тому же значению.
Иногда регулярные типы еще называют value types (или говорят о value semantics).

К более формальному списку требований. Тип является регулярным, если он:

  • Destructible.
  • DefaultConstructible. Конструктор по умолчанию создает объект в partially formed state - ему можно только присвоить новое значение или уничтожить.
  • Copiable. Если объект a является копией объекта b, то они равны.
  • Movable. Объект, из которого был move, находится в patially formed state. (Это не из EoP, но EoP не работает с move semantics, Sean Parent определял так и мне кажется что это разумно, в любом случае - я не об этом).
  • EqualitiyComarable.

STL изначально рассчитывался на регулярные типы. unique_ptr, с точки зрения синтаксиса, не является регулярным, но очень хорошо себя чувствует с stl. Изначально у меня была идея, давайте попробуем убрать часть ограничений с Regular, которых будет достаточно для большинства операций. Введем concept Unique - Regular без копирования. Тогда Regular будет усилением Unique и часть операций будут доступны только если тип не только Unique но и Regular (подобным образом EoP опредялет операции сравнения только для TotallyOrdered типов). Есть проблемы.

Насколько разумно выглядит данный код?

bool operator==(const Unique& x, const Unique& y) {
  return &x == &y;
}

Можно даже написать интересный алгоритм:

// (&v is in between begin and end pointers).
template <ContigiousIterator I,
          Unique V>
  requires std::is_same_v<ValueType<I>(), V>
I find(I f, I l, const V& v) {
  if (f == l) return l;
  auto* f_ptr = &*f;
  auto* l_ptr = f_ptr + (l - f);
  if (std::less<>{}(&v, f_ptr) ||   // It's only valid to compare pointers from one array
      (!std::less<>{}(&v, l_ptr))   // but std::less is defined everywhere.
     return l;
  return f + (&v - f_ptr);
}

Те получаем поиск в векторе за константное время)

Когда валиден ли данный код? Когда у нас семантически нет операции копирования. Отсутствие операции несет смысл.

Можно попробовать вспомнить про nullptr, но а) - это не отвечает на фундаментальный вопрос почему так в общем случае делать нельзя для unique_ptr и б)  - для регулярных типов сравнение в partially formed state не является осмысленной операцией. Наличие специального пустого значения это опять таки другой, хотя и полезный concept.

На самом деле вопрос к данному коду заключается в следующем, хотим ли мы чтобы работало вот это:

template <typename T>
auto find_ptr(const std::vector<std::unique_ptr<T>>& vec, T* x) {
  std::unique_ptr<T> tmp {&x};
  auto it = find(vec.begin(), vec.end(), tmp);
  tmp.release();
  return it;
}

 

 

Мне кажется, что не смотря на то что этот код нарушает инварианты unique_ptr, я бы ожидал такой код будет работать.

Все потому что семантически unique_ptr - это указатель и отсутствие операции копирования - это пометка когда вызывать удаление, а не его смысл. А указатель являетя регулярным типом. Что не означает, что Unique не является полезным concept и что unique_ptr в некоторых контекстах может быть так использован.

В EoP на ряду с регулярными объектами обсуждаются регулярные функции. Регулярная функция - это, грубо говоря, функция, результат которой зависит только от входных аргументов (printf не является регулярной, std::sort является, есть строгое определение). Иногда такие функции называют pure (не все согласятся про std::sort, это сейчас не столь важно). Две регулярные функции равны если для любого набора входных данных их результаты совпадают. Я говорю про регулярные функции потому что принципиально невозможно определить функцию проверки на равенство. Однако это не значит, что не существует понятия равенства. То есть копируемость std::function не страдает от того, что мы не можем определить полноценный operator==. Типы, для которых не возможно определить operator== EoP называет SemiRegular.

Мне кажется, что в случае с unique_ptr мы можем поступить так же - операцию копирования невозможно реализовать, но это не значит что у нее нет смысла.

Можно вспомнить про другие типы, у которых нет, например, конструктора по умолчанию. Это не значит, что мы должны запрещать их складывать в вектор, это просто значит что конструктор по умолчанию "подразумевается, но не существует".

Предлагаю расширить concept SemiRegular до: у данного типа семантически есть все операции регулярного типа, но не все их них реализованы (или даже возможно реализовать) в коде. Если у типа есть в интерфейсе данная операция, то она имеет регулярную семантику. Получается что тело такой concept должно состоять исключительно из комментария, так как у нас нет аксиом, но все равно выглядит разумно.

Тогда например вектор может выглядеть как-то так:

template <SemiRegular T, /**/>
class vector {
public:
  requires DefaultConstructible<T>
  vector(size_type)
// ...
};

Альтернативно можно было бы сказать что все маленькие ограничения на типы подразумевают SemiRegular.

0
рейтинг
3 комментария
yndx-antoshkka
Последний черновик предложения по по Ranges open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4651.pdf

Пока я не понимаю, зачем ослаблять требования SemiRegular. SemiRegular для vector - слишком сильное ограничение. Основные требования к типу T для вектора должны быть наподобие (Movable<T> && is_nothrow_constructible_v<T>) || Assignable<T>. Остальные ограничения должны накладываться на конкретный метод класса vector. Подскажите, что я упустил?
yndx-antoshkka
d-yaroshev
yndx-antoshkka, movable, nothrow_constructbile итд - это не concept. Точнее это плохой concept.

Одна из идей concepts в том чтобы описывать группу требований к типам для группы алгоритмов, причем требования к типам должны быть связаны.

Если тип CopyConstructible он должен быть CopyAssignable, MoveConstructibe и MoveAssignable.

Вот такой тип, например:
```
struct awful_type {
awful_type(const awful_type&) = default;
awful_type& operator=(const awful_type&) = default;
awful_type(awful_type&&) = delete;
awful_type& operator=(awful_type&&) = delete;
};
```
Не должен проходить проверку при вызове алгоритмов, потому что
а) - этот тип скорее всего имеет что-то очень странное в виду под операциями копирования/присваивания и мы не знаем как с этим странным работать
б) - ограничивает нашу возможность по разному реализовывать алгоритмы, например
```
T x = y;
```
и
```
T x = T(y);
```
Становятся разными вещами.

Это одна из основных вещей, которые мы пытаемся избежать с concepts, а именно - облегчить написание generic кода.

По факту мое предложение заключается в том, что все алгоритмы/контейнеры должны требовать некоторый общий concept, который подразумевает разумность операций.
Иногда некоторые из этих операций невозможно/очень сложно определить, такое бывает, но если мы определяем операцию, она должна нести вполне определенную семантику за собой.

Я предложил расширить SemiRegular, потому что ровно это SemiRegular сейчас и делает, только для операции operator==. Однако SemiRegular могло бы быть хорошим именем в целом, для любой операции которой нет.
d-yaroshev
yndx-antoshkka
d-yaroshev, ок. Давайте рассмотрим картину в целом:
1) Никто не даст ломать стандартные контейнеры. И если сейчас они работают с move-only type или с copy_constructible only типами, или еще с какой-то экзотикой - то так это и останется. Более того, некоторые контейнеры могут инстанцироваться ForwardDeclared типами. Так что концепт SemiRegular для типа T при инстанцировании контейнера сразу и не применишь.
2) В данный момент в комитете старательно отделяют compile-time требования к типам контейнеров от всего остального, чтобы проще было прикрепить концепты к контейнерам. И прикреплять будут "плохие" концепты, так как нет выбора (см пункт 1)
3) Если вы действительно заинтересованы в контейнерах на правильных концептах, то одной идеи Semiregular концепта будет мало. Нужно как и в случае с ranges, продумать ВСЁ целиком:
* добавить функционал к имеющимся контейнерам, да такой, чтобы все захотели этим пользоваться
* попутно, желательно, решить существующие проблемы контейнеров
* тщательно продумать ВСЕ концепты
* написать работающий прототип для ВСЕХ контейнеров
* показать, почему такой подход лучше
* написать proposal

С последней частью я могу помочь, но 4/5 работы по остальным пунктам придётся делать вам.
yndx-antoshkka
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).