Інтервали в С++, частина 2: Нескінченні інтервали

У попередньому пості ми намагалися впихнути інтервали з обмежувачами в STL, і переконалися, що результат залишає бажати кращого. Зараз ми спробуємо зробити це з нескінченними інтервалами, щоб прийти до аналогічного висновку. Але це вправа направить нас до концепції супер-інтервалів, які будуть включати в себе і інтервали з обмежувачами, і нескінченні, і пари ітераторів, що нагадують STL'ві.

Нескінченні інтервали
Необхідність нескінченних інтервалів обґрунтувати трохи складніше. Програмісти на С++ рідко стикаються з бесконечностями. В інших мовах це трапляється часто-густо. В Haskell можна створити нескінченний список цілих чисел, просто набравши [1..]. Це просто «ледачий список», елементи в якому створюються за вимогою. Всі нескінченні інтервали ледачі.

Для чого це може знадобитися? Припустимо, в алгоритмі, строящем новий список з N перших елементів іншого. Або ви захочете заархівувати в zip нескінченний список за допомогою кінцевого. Тоді ви отримаєте кінцевий список пар елементів. Це абсолютно нормальна практика.

Було б круто мати підтримку нескінченних списків у бібліотеці загального призначення.

Нескінченні інтервали/STL
Можна уявити собі нескінченні інтервали інтервали з обмежувачами, де умова обмеження завжди повертає false. Пам'ятаючи про це, реалізуємо нескінченний список цілих чисел, які починаються з заданого числа, і закінчується «ніколи».

struct iota_range
{
private:
int i_;
public:
using const_iterator = struct iterator
: boost::iterator_facade<
iterator, int const,
std::forward_iterator_tag
>
{
private:
bool sentinel_;
int i_;
friend class boost::iterator_core_access;
friend struct iota_range;
iterator(int i) : sentinel_(false), i_(i) {}
bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}
void increment() 
{
++i_;
}
int const & dereference() const
{
return i_;
}
public:
iterator() : sentinel_(true), i_(0) {}
};
constexpr explicit iota_range(int i = 0)
: i_(i)
{}
iterator begin() const
{
return iterator{i_};
}
iterator end() const
{
return iterator{};
}
constexpr explicit bool operator() const
{
return true;
}
};


З таким списком можна зробити наступне:

// Spew all the ints. WARNING: THIS NEVER ENDS!
for( int i : iota_range() )
std::cout << i << 'n';


iota_range – прямий інтервал; тобто, його ітератори побудовані за моделлю ForwardIterator. В них зберігається ціле число і булевское значення, яке говорить про те, є чи ітератор сигнальним. Ітератор begin не сигнальний, а end – сигнальний. Тому вони ніколи не будуть рівними, і ми будемо вважати цілі числа цілу вічність.

Що трапилося по дорозі в нескінченність
Правда, при роботі з таким інтервалом ви з'ясуєте, що щось працює, як очікувалося, а що-то відлітає в гіперпростір і не повертається. Простий приклад: std::distance. Вам повинно вистачити розуму, щоб не робити наступне:

iota_range iota;
// Oops!
auto dist = std::distance(iota.begin(), iota.end());


Менш очевидно, що вам не можна, взагалі, ніколи, ні за що, передавати таке інтервал в будь-який алгоритм бінарного пошуку – binary_search, lower_bound, upper_bound і equal_range. Незважаючи на те, що iota_range – це відсортований інтервал прямої. Бінарні алгоритми ділять інтервали, а поділ нескінченного інтервалу на виході має дати нескінченний інтервал. Чекати цього доведеться довго.

Швидкодія
Читачів минулого посту, можливо, покоробила реалізація iota_range::iterator::equal. Оскільки iota_range ніколи не повинен зупинитися у своїх ітераціях, умова припинення має бути константою. Замість цього ми робимо наступне:

bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}


Дві перевірки там, де їх має бути нуль! Минулого разу я показав, що це призводить до небажаних ефектів у створеному коді.

Можливі нескінченні інтервали
Крім проблеми з нескінченними циклами є ще одна, яка, на жаль, існує в STL. Візьмемо мого улюбленого хлопчика для биття std::istream_iterator. Це ітератор введення, тому з них необхідно пов'язати difference_type. У книзі «Elements of Programming» Олександр Степанов (батько STL та Generic Programming) говорить про це так:

DistanceType повертає цілий тип, досить великий, щоб виміряти будь-яку послідовність додатків допустимого саксессора.

Для istream_iterator difference_type буде std::ptrdiff_t. Розглянемо такий код:

std::istream& sin = ...;
std::istream_iterator<char> it{sin}, end;
std::ptrdiff_t dis = std::distance(it, end); 


Код допустимий і логічний. Він виокремлює символи з istream, підраховує їх, і позбавляється від них. Уявіть, що sin отримує символи з мережі, і цей код працює кілька днів, отримуючи мільярди символів. Що трапиться, якщо ptrdiff_t виявиться недостатньо великим для результату? Відповідь: невизначений поведінку. На практиці – сміття, але в принципі – все, що завгодно.

Мене це трохи збиває з пантелику. У ітератора difference_type повинен бути достатньо великим, щоб утримувати проміжок між двома будь-якими итераторами. Оскільки потоки введення в принципі кордонів не мають, то не існує знакового цілого, досить великого для них. Доводиться визнати, що допустимість операції збільшення istream_iterator обмежена розміром difference_type, або що difference_type задано невірно.

Попередній висновок
Нескінченні інтервали – річ корисна, але у них є проблема з тим, як вони визначені в STL. Можна було б заборонити нескінченні інтервали, але проблема навіть більше цього. І деякі з проблем, що існують і сьогодні. Важко виправити проблему з переповненням difference_type в STL (окрім як просити людей дотримуватися обережності), але можна подумати, не допоможе нам новий інтерфейс для інтервалів.

От поки всі проблеми, які я зустрів з інтервалах з парою ітераторів за принципом STL:

  • інтервали з обмежувачами і нескінченні інтервали генерує поганий код,
  • їм доводиться моделювати більш слабкі концепції, ніж вони могли б,
  • їх важко використовувати,
  • дуже просто передати нескінченний інтервал в алгоритм, який його не перетравить,
  • інтервали, які можуть бути нескінченними або дуже великими, можуть викликати переповнення в difference_type.


В наступному пості я опишу основи концепції моєї нової бібліотеки інтервалів, яка б'є в корінь усіх цих проблем. Не перемикайтеся.

Знову невеликий презент для добралися до кінця. Ще п'ять квитків зі знижкою 30% промокоду Infinite Ranges

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.