У попередніх постах я описав проблеми, з якими зіткнувся при створенні бібліотеки для роботи з інтервалами. Зараз я опишу вам моє рішення: покращення концепції інтервалів, які дозволяють створювати інтервали з обмежувачами і нескінченні інтервали, що чудово вписуються в ієрархію стандартної бібліотеки без втрати продуктивності.
У кінці попереднього поста я підсумував недоліки існуючих інтервалів:
інтервали з обмежувачами і нескінченні інтервали генерує поганий код
їм доводиться моделювати більш слабкі концепції, ніж вони могли б
легко можна передати нескінченний інтервал в алгоритм, який його не перетравить
їх важко використовувати
інтервали, які можуть бути нескінченними або дуже великими, можуть викликати переповнення в difference_type
Перша проблема особливо важка, тому почнемо з неї.
Концепція інтервалів
Для початку, давайте суворо визначимо поняття інтервалу. У стандарті C++ це слово використовується всюди, але ніде не визначається. Можна зрозуміти, що інтервал – це щось, з чого можна отримати begin і end, пару ітераторів, які влаштовані так, що до end можна дістатися, почавши з begin. У термінах моєї пропозиції формалізувати цю концепцію можна так:
using std::begin;
using std::end;
template < typename T>
using Iterator_type =
decltype(begin(std::declval<T>()));
template < typename T>
concept bool Range =
requires(T range) {
{ begin(range) } -> Iterator_type<T>;
{ end(range) } -> Iterator_type<T>;
requires Iterator<Iterator_type<T>>;
};
Також є поліпшення концепції інтервалу Range, які називаються InputRange, ForwardRange, і т. д. На ділі вони просто більше вимагають від своїх ітераторів. Нижче показана вся ця ієрархія.
Ці концепції є основою для бібліотек Boost.Range (http://www.boost.org/libs/range)
Проблема 1: Генерація поганого коду
Якщо пам’ятаєте, для реалізації інтервалів як з обмежувачем, так і нескінченних, у вигляді пари ітераторів, ітератор end повинен бути особливим. І такий ітератор являє собою більше концепцію, ніж фізичне положення елемента в послідовності. Можна представляти його, як елемент з позицією «останній + 1» – різниця лише в тому, що ви не дізнаєтеся, де його позиція, поки не досягнете її. Оскільки тип сигнального ітератора такою ж, як у звичайного, потрібна перевірка на етапі виконання програми, щоб визначити, чи є даний ітератор сигнальним. Це призводить до повільного порівнянні ітераторів і незручним реалізаціями методів.
Концепція инкременторов(Iterable)
Для чого потрібні ітератори? Ми збільшуємо їх, разыменовываем і порівнюємо, так адже? А що можна зробити з сигнальним ітератором? Не особливо багато чого. Його позиція не змінюється, його можна разыменовать, оскільки його позиція завжди «останній + 1». Але його порівняти з ітератором. Виходить, що сигнальний ітератор – слабкий ітератор.
Проблема з інтервалами в тому, що ми намагаємося перетворити сигнальний ітератор в звичайний. Але він ним не є. Так і не будемо це робити – нехай вони будуть іншого типу.
Концепція Range вимагає, щоб begin і end були одного типу. Якщо можна їх зробити різними, це вже буде більш слабка концепція – концепція Iterable. Инкременторы – вони як ітератори, тільки у begin і end різні типи. Концепція:
template<typename T>
using Sentinel_type =
decltype(end(std::declval<T>()));
template < typename T>
concept bool Iterable =
requires(T range) {
{ begin(range) } -> Iterator_type<T>;
{ end(range) } -> Sentinel_type<T>;
requires Iterator<Iterator_type<T>>;
requires EqualityComparable<
Iterator_type<T>, Sentinel_type<T>>;
};
template < typename T>
concept bool Range =
Iteratable<T> &&
Same<Iterator_type<T>, Sentinel_type<T>>;
Природно, концепція Range входить в концепцію Iterable. Вона просто уточнює її, додаючи обмеження на рівність типів begin і end.
Так виглядає ієрархія, якщо ми розглядаємо інтервали, инкременторы і ітератори, але зовсім не обов’язково саме так визначати їх у програмі. Зауважте, що «интервальность» – тобто, схожість типів begin і end, ортогональна силі ітератора begin. Коли нам треба включати в код моделювання RandomAccessRange, ми можемо сказати requires RandomAccessIterable && Range і просто змінити всю концепцію.
Різниця між, наприклад, BidirectionalIterable і ForwardIterable в концепції, моделюється ітератором begin з Iterable.
Iterable і алгоритми STL
Але постійте – адже алгоритми STL не будуть працювати з инкременторами, тому що їм потрібно, щоб у begin і end було один тип. Так і є. Тому я прошерстил весь STL, щоб перевірити, що можна переписати. Наприклад, std::find
template<class InputIterator, class Value>
InputIterator
find(InputIterator first, InputIterator last,
Value const & value)
{
for (; first != last; ++first)
if (*first == value)
break;
return first;
}
Зараз std::find використовує Ranges. Але зауважте, що алгоритм не намагається поміняти позицію ітератора end. Алгоритм пошуку можна легко змінити так, щоб він працював з Iterables замість Ranges:
template<class InputIterator, class Sentinel, class Value>
InputIterator
find(InputIterator first, Sentinel last,
Value const & value)
{
for (; first != last; ++first)
if (*first == value)
break;
return first;
}
Ось і все – зміна настільки мале, що його навіть важко помітити.
Так які алгоритми C++98 можна пристосувати до роботи з Iterables замість Ranges? Виявляється, майже всі. Легше перерахувати ті, які не піддаються. Це:
- copy_backward
- алгоритми роботи з множинами і пірамідами (push_heap, pop_heap, make_heap, sort_heap)
- inplace_merge
- nth_element
- partial_sort і partial_sort_copy
- next_permutation і prev_permutation
- random_shuffle
- reverse і reverse_copy
- sort і stable_sort
- stable_partition
Інші півсотні вимагають чисто механічного зміни в коді. Визначивши концепцію Iterable так, як вона визначається в Range, ми даємо будь-якого алгоритму, що працює з Iterable, можливість точно так само працювати і з Ranges. Це корисно і важливо – для ітераторів написано дуже багато коду, щоб робити для них якусь несумісну абстракцію.
Доказ у Perf
І що ми отримаємо? Повернемося до наших З-рядками. Я описав клас c_string_range і знайшов, що перебір символів генерує поганий код. Почнемо знову, тільки за допомогою range_facade, щоб побудувати Iterable замість Range.
using namespace ranges;
struct c_string_iterable
: range_facade<c_string_iterable>
{
private:
friend range_core_access;
const char *sz_;
const char & current() const { return *sz_; }
void next() { ++sz_; }
bool done() const { return *sz_ == 0; }
bool equal(c_string_iterable const &that) const
{ return sz_ == that.sz_; }
public:
c_string_iterable(const char *s)
: sz_(sz) {}
};
Код вийшов набагато простіше, ніж старий. Всю роботу робить range_facade. Ітератор і сигнальний ітератор реалізовані у вигляді примітивів. Щоб перевірити його, я згенерувати оптимізований машинний код для наступних функцій, одна з яких використовує старий клас c_string_range, а інша – новий c_string_iterable:
// Range-based
int range_strlen(
c_string_range::iterator begin,
c_string_range::iterator end)
{
int i = 0;
for(; begin != end; ++begin)
++i;
return i;
}
// Iterable-based
int iterable_strlen(
range_iterator_t<c_string_iterable> begin,
range_sentinel_t<c_string_iterable> end)
{
int i = 0;
for(; begin != end; ++begin)
++i;
return i;
}
Навіть не знаючи асемблера, можна зрозуміти різницю.
|
|
Код з инкременторами набагато крутіше. І він практично ідентичний з ассемблером, отриманим ітераторів «голого».
Ітератори, сигнальні ітератори і паритетність
Але що означає порівняння двох об’єктів різних типів на еквівалентність?
Трохи для непосвячених: N3351 визначає, в яких випадках припустимі порівняння різних типів. Недостатньо, щоб синтаксис «x==y» був припустимо і видавав булевское значення. Якщо у х і в будуть різні типи, то ці типи повинні бути самі по собі EqualityComparable, і у них має бутизагальний тип, до якого їх можна перетворити, і він також повинен бути EqualityComparable. Припустимо, ми порівнюємо char і short. Це можливо, оскільки вони EqualityComparable, і їх можна перетворити в int, який теж EqualityComparable.
Ітератори можна порівнювати, а сигнальні ітератори порівнюються тривіальним чином. Складність в тому, щоб знайти для них загальний тип. Взагалі, у кожного ітератора і сигнального є загальний тип, який можна створити так: припустимо існування нового типу ітератора I, який представляє собою тип-суму, і містить або ітератор, або сигнальний ітератор. Коли їх порівнюють, він веде себе семантично так, ніби їх обох спочатку перетворили в два об’єкти типу I, назвемо їх lhs і rhs, і потім порівняли по наступній табличці:
| lhs сигнальный итератор? | rhs сигнальный итератор? | lhs == rhs? |
| true | true | true |
| true | false | done(rhs.iter) |
| false | true | done(lhs.iter) |
| false | false | lhs.iter == rhs.iter |
Ця табличка нагадує ту, яка вийшла при аналізі поведінки оператора порівняння c_string_range::iterator. Це не випадково – то був особливий випадок цієї, більш загальної, схеми. Вона підтверджує інтуїтивне висновок, який ви вже можете помітити, переглянувши два моїх класу, c_string_range і c_string_iterable. Один – пара ітераторів, інший – пара ітератор/сигнальний, але їх схема роботи схожі. Ми відчуваємо, що можливо побудувати еквівалентний Range будь Iterable, якщо пожертвувати дещицею швидкодії. І тепер ми знайшли підтвердження цьому.
Можливість порівнювати ітератори і сигнальні ітератори безпосередньо дозволяє нам використовувати систему типів C++ для оптимізації великий категорії ітерацій, прибираючи розгалуження в операторі порівняння паритетності.
Заперечення
Ідея дати різні типи begin і end не нова, і придумав її не я. Я дізнався про неї від Дейва Абрахамса (Dave Abrahams) багато років тому. Нещодавно подібну ідею подав Дітмар Кюэль (Dietmar Kuehl) у списку розсилки Ranges, а у відповідь на його лист Шон Пэрент (Sean Parent) висловив наступне заперечення:
Мені здається, ми покладаємо на ітератори занадто багато. Алгоритми, що працюють з закінченням на підставі перевірки сигнального ітератора або на підставі підрахунку – це різні сутності. См. copy_n() і copy_sentinel()
stlab.adobe.com/copy_8hpp.html
Щодо інтервалів – я впевнений, що можна побудувати його за допомогою:
- пари ітераторів
- ітератора і кількість
- ітератора і сигналу
І в цьому випадку copy(r, out) може видати потрібний алгоритм.
Якщо я правильно його зрозумів, він говорить про існування трьох паралельних концепцій інтервалів: IteratorRange, CountedRange і SentinelRange. І ці ієрархії не потрібно намагатися зв’язати між собою. Алгоритм копіювання повинен містити три різні реалізації, по одній на кожну концепцію. Тоді доведеться потроїти близько 50 алгоритмів – і це надто багато повторення в коді.
Гірше того, деякі алгоритми засновані на уточнених концепціях. Наприклад, libc++ алгоритм rotate обирає одну з трьох реалізацій, в залежності від того, ви передаєте йому прямі, двосторонні або ітератори довільного доступу. А для включення трьох різних реалізацій Iterator, Counted і SentinelRanges знадобилося б 9 алгоритмів rotate! При всій повазі, це божевілля.
Підсумки
На початку посту я навів список проблем, пов’язаних з інтервалами з парними итераторами. Я показав нову концепцію, Iterable, яка займається питаннями швидкодії і порушив питання складнощів реалізації інтервалів. Поки я не описав, як ця концепція працює з нескінченними інтервалами, про що ми поговоримо в четвертому, фінальному пості.
Весь код можна знайти у сховищі на github.