Бывает, требуется сгенерировать диапазон чисел из какого-либо алгоритма. Будь то диапазон чисел, просто расположенных по возрастанию, или лишь нечетные числа, или только простые и т.п. Некоторые операции можно оптимизировать, запоминая значения для расчета следующего числа, точно как это делается с числами Фибоначчи. В этой статье я расскажу, как оборачивать такие расчеты в итераторы, чтобы получались мощные, красиво инкапсулированные алгоритмы.
Числа Фибоначчи
Ряд чисел Фибоначчи широко известен. Генерация этих чисел – классический пример рекурсии, но, как минимум, в стандартных императивных языках, итеративная версия получается мощнее:
size_t fib(size_t n)
{
size_t a {0};
size_t b {1};
for (size_t i {0}; i < n; ++i) {
const size_t old_b {b};
b += a;
a = old_b;
}
return b;
}Таким образом очень просто сгенерировать любое число Фибоначчи. Но если для решения той или иной задачи нужно сгенерировать все числа Фибоначчи вплоть до некоторого предела, это решение уже не назовешь удобным. При подсчете числа Фибоначчи
N, а затем N+1, содержимое переменных a и b можно было бы переиспользовать, поскольку каждое число Фибоначчи есть сумма двух предыдущих чисел того же ряда.В данном случае удобно было бы иметь класс, управляющий неким состоянием Фибоначчи, чтобы с его помощью быстро получать именно следующее число.
Многие из нас просто реализовали бы класс
fibonacci_number с некоторым методом next(), методом current() – и использовали его. Это, конечно, хорошо, но я предлагаю сделать еще один шаг и напоминаю: ведь именно так работают итераторы. Реализовав эту функциональность на языке итераторов, ее можно использовать в комбинации с STL, значительно повысив удобочитаемость кода.Итераторы
Что нужно сделать, чтобы реализовать простейший возможный итератор?
Вот что имеет к нам компилятор C++, если мы хотим перебрать класс контейнера:
for (const auto &item : vector) {
/* тело цикла */
}
Такое объявление цикла существует со времен C++11. Компилятор сделает из него вот такой эквивалентный код:
{
auto it (std::begin(vector));
auto end (std::end(vector));
for (; it != end; ++it) {
const auto &item (*it);
/* тело цикла */
}
}Смотрим на расширенный цикл – и видим, что нужно реализовать. Во-первых, нужно различать объекты двух видов:
vector – это итерируемый диапазон, а it — итератор.Итерируемый диапазон должен реализовывать функции
begin() и end(). Эти функции возвращают объекты итератора.Обратите внимание: в примере кода возвращается не vector.begin() и vector.end(), а
std::begin(vector) и std::end(vector). Эти функции STL действительно вызывают vector.begin() и end(), но они более универсальны, то есть, также применимы с необработанными массивами и автоматически делают что надо, чтобы получить начальный и конечный итераторы.Вот что должно быть реализовано в классе
iterator:- оператор *, выполняющий разыменование указателя (указатели – также полноценные итераторы!)
- оператор ++ (префиксный), делающий инкремент итератора до следующего элемента
- оператор !=, необходимый для проверки того, а не следует ли завершить цикл – то есть, не достиг ли
itпозиции, указанной вend.
Чтобы реализовать какой бы то ни было алгоритмически генерируемый диапазон, для начала нужно сделать итератор, который, в сущности, скрывает переменные и сам алгоритм в реализации
operator++. Затем итерируемый класс просто предоставит начальный и конечный итераторы, обеспечив, таким образом, циклы for в стиле C++11.class iterator
{
// ... переменные состояния ...
public:
// Конструктор
iterator& operator++() { /* инкремент */ return *this; }
T operator*() const { /* вернуть значение или ссылку */ }
bool operator!= const (const iterator& o) { /* сравнить состояния */ }
}Простейший на свете итератор – счетный; он просто оборачивает целочисленную переменную, оборачивает ее в operator++ и возвращает целое число в
operator*. operator!= затем просто сравнит это число с числом из другого итератора.А теперь перейдем к итератору Фибоначчи.
Итератор Фибоначчи
class fibit
{
size_t i {0};
size_t a {0};
size_t b {1};
public:
constexpr fibit() = default;
constexpr fibit(size_t b_, size_t a_, size_t i_)
: i{i_}, a{a_}, b{b_}
{}
size_t operator*() const { return b; }
constexpr fibit& operator++() {
const size_t old_b {b};
b += a;
a = old_b;
++i;
return *this;
}
bool operator!=(const fibit &o) const { return i != o.i; }
};При помощи этого итератора уже можно перебрать числа Фибоначчи:
fibit it;
// Поскольку оператор сравнения сравнивает только переменную "i",
// определяем итератор с одними нулями, но для "i" устанавливаем значение
// 20, чтобы на нем перебор завершился
const fibit end {0, 0, 20};
while (it != end) {
std::cout << *it << std::endl;
++it;
}
// Либо делаем это красиво как в STL: (сначала включаем <iterator>)
std::copy(it, end, std::ostream_iterator<size_t>{std::cout,"\n"});Чтобы все было красиво, как в C++11, нам нужен итерируемый класс:
class fib_range
{
fibit begin_it;
size_t end_n;
public:
constexpr fib_range(size_t end_n_, size_t begin_n = 0)
: begin_it{fibit_at(begin_n)}, end_n{end_n_}
{}
fibit begin() const { return begin_it; }
fibit end() const { return {0, 0, end_n}; }
};А теперь можно написать…
for (const size_t num : fib_range(10)) {
std::cout << num << std::endl;
}
… и вывести на экран 10 первых чисел Фибоначчи
Что делает функция
fibit_at? Это функция constexpr, которая по возможности продвигает итератор Фибоначчи во время компиляции, чтобы он дошел до того числа Фибоначчи, которое требуется пользователю:constexpr fibit fibit_at(size_t n)
{
fibit it;
for (size_t i {0}; i < n; ++i) {
++it;
}
return it;
}Например, эта функция позволяет перебрать числа в ряду Фибоначчи от сотого до сто пятого без необходимости высчитывать первые 100 чисел Фибоначчи во время выполнения, так как мы можем подготовить нужную стартовую позицию уже во время компиляции.
При работе с C++17
fibit_at бесполезна, так как ее можно заменить на std::next(fibit{}, n), поскольку в C++17 STLstd::next – это функция constexpr.Чтобы гарантировать, что 100-е число в ряду Фибоначчи уже будет высчитано, когда компилятор станет записывать на диск бинарную программу, можно просто внести диапазон в переменную
constexpr:constexpr const fib_range hundred_to_hundredfive {105, 100};
for (size_t num : hundred_to_hundredfive) {
// Делаем что-нибудь
}
Комбинируем итератор Фибоначчи с алгоритмами STL
Допустим, нам нужен вектор с первыми 1000 числами Фибоначчи. Мы уже обернули алгоритм Фибоначчи в удобный класс итератора, и теперь можем использовать его с любым STL-алгоритмом из пространства имен
std:std::vector<size_t> fib_nums;
fib_nums.resize(1000);
constexpr const fib_range first1000 {1000};
std::copy(std::begin(first1000), std::end(first1000), std::begin(fib_nums));Очень красиво и удобно. Однако, код в том виде, как он представлен здесь, не скомпилируется, поскольку мы не задали метку итератора. Делается это просто: пусть
fibit явно унаследует std::iterator<std::forward_iterator_tag, size_t>.std::iterator, будучи базовым для нашего класса fibit, просто добавит несколько определений типов, которые помогут алгоритмам STL разобраться, что это за итератор. Для итераторов определенного типа в конкретных ситуациях существуют иные реализации алгоритмов STL, производительность которых оптимизирована (от пользователя это аккуратно скрыто!).Метка
std::forward_iterator означает, что перед нами итератор, который можно просто продвигать шаг за шагом – и он будет двигаться только вперед, но не назад.Итоги
Многие алгоритмы, генерирующие числовые диапазоны, можно реализовать в виде итераторов, что совершенно естественно. В C++ есть вкусный синтаксический сахар для итераторов, благодаря чему из них получаются органичные интерфейсы для абстракций.
Вместе с алгоритмами STL и любыми STL-совместимыми структурами данных из них получается удобочитаемый мощный код, который легко тестировать и поддерживать.
В статье рассказано об итераторе, а не обычном указателе данных. Реализация алгоритма интересна тем, что на этапе инкремента вычисляется нечто более сложное, нежели новая позиция внутреннего указателя на следующий элемент. Интересно, что таким образом можно инстанцировать некоторый итерируемый объект, определяющий диапазон – а для этого необходимы серьезные вычисления. Но они выполнены не будут, пока кто-нибудь специально не запросит результат (а код, запрашивающий результат, даже не «знает», какой алгоритм при этом неявно выполняется, поскольку эта информация скрыта за простым интерфейсом итератора).
Такой стиль связан с ленивыми вычислениями – это мощный и красивый принцип из чисто функциональных языков программирования.
Комментарии (43)
Shamov
16.12.2016 15:23+1К сожалению, этот "итератор" (на самом деле, генератор) не будет работать со стандартными алгоритмами
std::generateиstd::generate_n. Особую пикантность ситуации придаёт то, что в том примере, который автор выбрал для демонстрации того, как хорошо "итератор" комбинируется со стандартными алгоритмами, делается как раз то, для чего и предназначены данные алгоритмы. Проще говоря, в примере, который должен был продемонстрировать бесшовную интеграцию со стандартными алгоритмами, автор использует неправильный алгоритм и демонстрирует костыльный способ интеграции с ним.
Mingun
16.12.2016 18:40Гм. Так а что нужно доработать, чтобы он всё-таки заработал со стандартными алгоритмами
std::generateиstd::generate_n?
stack_trace
16.12.2016 21:30+1Мне кажется, вы всё же немного не справедливы. Генераторы удобны для заполнения коллекций, но не для алгоритмов. Если вам просто надо проивести ряд вычислений или операций над некой последовательностью, тогда запись
for (auto num : numbers(4, 10)) { ... }
намного удобнее, чище, нагляднее и несколько безопаснее, нежели что-то вроде
auto generator = numbers(4, 10); for (i = 0; i < generator.size(); ++i) { auto num = generator(); ... }Shamov
17.12.2016 00:01+1Запись можно сделать какую угодно. Но всё-таки штука, которая генерирует значения на лету, называется "генератор". А "итераторами" принято называть штуки, которые итерируют по уже существующим значениям. При этом можно совершенно спокойно добавить в генератор поддержку фич итератора. Но, во-первых, желательно, чтобы он при этом оставался генератором (т.е. самим собой). А, во-вторых, нужно понимать, что ты делаешь генератор, мимикрирующий под итератор, а не настоящий итератор.
Ещё Конфуций призывал называть вещи своими именами. Очень незаурядный, надо сказать, человек был. В историю вошёл благодаря своей мудрости.
playermet
17.12.2016 21:22+1Но всё-таки штука, которая генерирует значения на лету, называется «генератор». А «итераторами» принято называть штуки, которые итерируют по уже существующим значениям.
Все генераторы являются итераторами, и они не связаны с генерацией значений на лету.
Ещё Конфуций призывал называть вещи своими именами.
Только определения при этом нужно использовать общепринятые, иначе они никак не помогут в общении.Shamov
17.12.2016 22:15Человек есть животное на двух ногах, лишённое перьев.
— ПлатонОтнюдь. Генератор псевдослучайных чисел не является итератором. Также итератором не является генератор электрического тока. Генератор документации doxygen не является итератором, хотя часто применяется в итеративной разработке. (Наверное, в нём всё-таки есть что-то от итератора.)
Тем не менее, все эти вещи называются генераторами. Совпадение? Не думаю. Всё дело в том, что они что-то — внимание! — ГЕНЕРИРУЮТ. Т.е. они сами являются источником этого чего-то. Применительно к программированию этим чем-то являются значения… именно их генерируют генераторы… т.е. генераторы сами являются источником значений. В отличие от итераторов, которые итерируют по тем значениям, которые являются по отношению к ним внешними.
playermet
18.12.2016 01:02Генератор псевдослучайных чисел не является итератором. Также итератором не является генератор электрического тока. Генератор документации doxygen не является итератором, хотя часто применяется в итеративной разработке.
Это все очень хорошо, но в программировании есть отдельный термин «генератор» не имеющий никакого отношения к перечисленному, и именно о нем сейчас идет речь.
т.е. генераторы сами являются источником значений. В отличие от итераторов, которые итерируют по тем значениям, которые являются по отношению к ним внешними.
По такой логике и переменная не переменная, если значение ей не переменять. Но как я и говорил выше, следует использовать устоявшиеся значения терминов, а не выдумывать новые, иначе никто не поймет что имелось ввиду.Shamov
18.12.2016 10:59-1К сожалению, это не так. Как бы вам не хотелось того, чтобы генераторы в программировании не имели никакого отношения к иным генераторам, они его всё-таки имеют. Связь проявляется на уровне языка. Точно такое же слово для обозначения было выбрано отнюдь не потому, что в языке закончились свободные слова и нужно было взять любое из имеющихся, наделив его абсолютно новым значением, никак не связанным с предыдущими.
Переменная, значение которой вы изменить можете, но не делаете этого, называется переменной. А вот переменная, значение которой вы не можете изменить, уже называется иначе — константой. Для названий гораздо большее значение имеет то, чем предмет является объективно, а не то, как вы с ним взаимодействуете.
Когда-то давно я читал книгу о том, как устроено американское школьное образование. Тогда мне казалось невероятным, что образование может быть устроено таким образом. Ведь, по сути, это не было образованием как таковым. Дети не получали в школе даже самых элементарных знаний. Теперь я уже не так уверен. Всё-таки какие-то знания американские выпускники получали. По крайней мере, они точно должны понимать, что генераторы генерируют, а итераторы итерируют. Ведь они там чуть ли не каждую неделю пишут какое-нибудь эссе. А значит какой-то базовый уровень владения языком у них должен быть.
playermet
19.12.2016 00:11Как бы вам не хотелось того, чтобы генераторы в программировании не имели никакого отношения к иным генераторам, они его всё-таки имеют
Вас куда-то относит от темы. Я вам о том, что не соотносил генераторы электрического тока с итераторами, а вы в ответ пытаетесь угадывать чего я хочу…
Переменная, значение которой вы изменить можете, но не делаете этого, называется переменной. А вот переменная, значение которой вы не можете изменить, уже называется иначе — константой. Для названий гораздо большее значение имеет то, чем предмет является объективно, а не то, как вы с ним взаимодействуете.
Правильно. Поэтому генераторы остаются генераторами, даже если они вообще не возвращают никаких значений, но потому что могут в принципе. Генераторы — это ассиметричные сопрограммы. Или, как еще говорят, функции с поведением итератора. Ничего более.
А значит какой-то базовый уровень владения языком у них должен быть.
К чему вообще это и весь последний абзац?Shamov
19.12.2016 01:06-1Сопрограммы — это просто один из способов реализации генераторов. Причём характерный только для питона. В других языках сопрограмм либо до сих пор нет, либо они появились недавно, а ведь генераторы и раньше как-то делали. Более того, лично я считаю, что сопрограммы вообще не являются ничем, кроме синтаксического сахара. Ничего принципиального нового они не привносят. Промежуточное состояние приостановленной функции я без труда могу хранить в отдельной структуре и передавать его в каждый следующий вызов функции. Я имею в виду то, что я могу сделать это непринуждённо… т.е. вообще не напрягаясь. Это не то же самое, что эмулировать таблицу виртуальных методов в Си. Последнее представляет собой определённый геморрой. А вот сопрограммы — "это изи" (как говорит современная молодёжь).
Последний абзац был лирическим отступлением. Это такой повествовательный приём. Не берите в голову. Считайте, что я сделал это отступление просто потому, что могу...
playermet
19.12.2016 13:02+2Сопрограммы — это просто один из способов реализации генераторов.
Эмм, нет. Откуда вы берете такую дезинформацию? Можно привести пример книги или авторитетной статьи, которая это утверждает?
Причём характерный только для питона
У питона есть официальный референс, и там прямым текстом сказано чем в этом языке считается генератор. А именно — «A function which returns a generator iterator. It looks like a normal function except that it contains yield expressions for producing a series of values usable in a for-loop or that can be retrieved one at a time with the next() function.».
В других языках сопрограмм либо до сих пор нет, либо они появились недавно
Это утверждение неверно. Генераторами в Perl, PHP, Ruby, JS официально считается то же, что и в Python. Неофициальные библиотеки для других языков используют эту же интерпретацию. При этом есть десятки других языков с корутинами, но термин «генератор» они не используют в принципе, даже в случаях в которых предлагаете его использовать вы. И почти все вышеописанное появилось далеко не вчера. Такое же значения термина повсеместно и на stackowerflow, а википедия напрямую сравнивает между собой корутины и генераторы. Так почему мы должны считать генераторами что-то другое, чем описанной мной выше?
Более того, лично я считаю, что сопрограммы вообще не являются ничем, кроме синтаксического сахара.
Тогда и все языки программирования следует считать синтаксическим сахаром над бинарным исполняемым кодом. Ведь все что они делают можно повторить и на нем.Shamov
19.12.2016 13:23-2Я вообще не понимаю, почему мы говорим о сопрограммах и корутинах. Да, они используются для создания генераторов, потому что это удобно. Кто с этим спорит? Нужно отойти на шаг назад. В чём вообще исходная проблема?
playermet
19.12.2016 13:48+1Я вообще не понимаю, почему мы говорим о сопрограммах и корутинах.
Потому что по общепринятой терминологии генератор — это усеченная в возможностях сопрограмма. Все возможные пруфы и аргументы были предоставлены, но вы почему-то отказываетесь это принимать.
Да, они используются для создания генераторов
Нет, не используются. Вы хотя бы переходили по ссылкам, что я скинул? Я даже один абзац полностью в комментарий вставил, чтобы вы не пропустили.
В чём вообще исходная проблема?
В прививании термину «генератор» самопальное значение.Shamov
19.12.2016 14:31-1Мне не нужно переходить по ссылкам, чтобы понимать, что в общем смысле генератор — это то, что генерирует значения. Ну, а если говорить конкретно про питон, то там это слово используется в специальном значении. Согласно приведённой вами же цитате, в питоне генератором называется функция, которая возвращает генерирующий итератор. Тем не менее, даже эта узкая питоновская трактовка всё равно связана с генерацией значений. И это неудивительно. Генерация значений — это ключевой момент в генераторе. Не важно, что он делает в дополнение к этому, но он обязательно должен делать что-то связанное с генерацией значений. В противном случае это не генератор.
playermet
19.12.2016 20:43Мне не нужно переходить по ссылкам, чтобы понимать, что в общем смысле генератор — это то, что генерирует значения.
В общем я понял что смысла в продолжении монолога нет. До свидания.Shamov
19.12.2016 21:16-1Наконец-то! Удивительно, что потребовалось столько времени, чтобы понять, что на таком фуфле меня не развести. В том, что генераторы генерируют значения, я абсолютно уверен.
qw1
18.12.2016 08:46+1Раз уж вспомнили Платона, то легко представить, что в его мире идей находится бесконечная таблица чисел Фибоначчи, и этот объект — именно итератор, ходящий по ней. Поэтому идея такого итератора не вызывает у меня отторжения.
Если посмотреть на сигнатуры, то генератор — это нечто, имеющееoperator(), а итератор —operator++. То есть, для итератора логично предположить и симметричныйoperator--. Этим я и предлагаю отличать генераторы от итераторов — наличием вычислимого (возможно, трудновычислимого) предыдущего элемента.
Например, у односвязного списка есть предыдущий элемент, хотя нет эффективногоoperator--, а у последовательности случайных чисел — предыдущий не имеет смысла.Shamov
18.12.2016 12:05+1В мире идей Платона генератор псевдослучайных чисел тоже имел бы свою таблицу чисел и ходил бы по ней. Значит ли это, что его следует называть "итератор по псевдослучайным числам"? Или всё-таки мир идей Платона имеет не такое существенное значение?
Наличием
operator--отличаются разные типы итераторов —bidirectionalиforward.qw1
18.12.2016 12:41+1Я предложил семантическое различие. Реализация может быть любой.
Если для задачи важно, какое псевдослучайное значение было перед этим (например, при взломе криптосистем) — это итератор. Если вы работаете с псевдослучайными последовательностями как со случайными — это генератор.Shamov
18.12.2016 13:20-1Если название вещи будет зависеть не от её собственных свойств, а от того способа взаимодействия с вещью, который используется в данный момент, то это будет название не самой этой вещи, а всего лишь название её отображения, имеющее смысл только в рамках текущей задачи.
Само по себе это не бред. Но в сочетании с отсылкой к Платону образуется неконсистентная позиция. В споре "номиналисты vs. реалисты" вы, как бы, находитесь сразу на обеих сторонах. Существование мира идей Платона — это реализм. А представление о том, что самих идей в чистом виде не существует, а существуют лишь прикладные понятия (отражения на стенах платоновской пещеры) — это номинализм.
Кроме того, не совсем понятно, зачем нам нужно другое семантическое различие, когда одно у нас уже есть. Генераторы — это штуки, которые генерируют значения. Т.е. мы не привязываем к ним уже существующие значения. А итераторы — это штуки, которые итерируют по заранее подготовленному набору значений. Неизбежным следствием того, что они итерируют является то, что они не генерируют. А это крайне важно с точки зрения методологии. Дистинктивность — необходимое условие существования отдельного понятия. Если у вещи есть отдельное название, то значит обязательно должно существовать какое-то дистинктивное свойство, отличающее эту вещь от всех прочих.
iCpu
20.12.2016 07:19+1Если название вещи будет зависеть не от её собственных свойств, а от того способа взаимодействия с вещью, который используется в данный момент, то это будет название не самой этой вещи, а всего лишь название её отображения, имеющее смысл только в рамках текущей задачи.
Есть курица, она бегает, щиплет траву, кудахтает и несёт яйца.
А ещё есть еда, которая куриные крылья в кляре, куриный бульон и салат из копчёной куриной грудки с ананасами. А ещё еда — это говядина, фрукты, зелень, и если очень приспичит, кожаный ремень.
То же самое и тут, у нас есть итератор, позволяющий передвигаться по известной последовательности. Как она представлена, контейнером или алгоритмом, в общем, не важно, если i-тый шаг всегда будет возвращать одно и то же i-тое значение. Числа Фибоначчи, цифры числа Пи или числа Эйлера, от того, как вы их храните, их сущность и значение не меняются.
Другое дело, генератор, выходные значения которого зависят от начального состояния. Например, генератор псевдослучайных величин в зависимости от инициализатора может выдавать непересекающиеся множества. Генераторы, однако — тоже итераторы, просто их мерность больше, чем мерность публичного итератора.
Так что в данном случае вы не правы.Shamov
20.12.2016 07:37-1Ещё как важно. Когда последовательность представлена контейнером, и вы итерируете непосредственно по элементам этой последовательности — это простой итератор. А когда последовательность задана функцией, и вы итерируете по значениям аргумента, генерируя сами элементы на лету — это генерирующий итератор (т.е. генератор).
iCpu
20.12.2016 08:29+1Допустим. Интересно, если бы значения последовательности кешировались бы в контейнер, вы бы по прежнему настаивали на том, что это генератор, или уже перешли бы к термину «итератор с инициализатором»? Или «генератор с буфером»? И где бы прошла грань? По линии раздела итератора?
Я веду к тому, что граница между итераторами и генераторами очень зыбкая, и уповать только на «вычисление элемента» — весьма глупо. Есть, например, итераторы по шифрованным последовательностям, они в куда? Вроде бы контейнеры, но без начальной инициализации ключом не работают, да и производят вычисления над каждым очередным элементом. Именно поэтому лично мне использование термина «генератор» в этом контексте кажется глупым. Если уж и разделять генераторы и итераторы, то по возможности контролировать момент перехода от текущего значения к следующему. Иначе разделение просто нельзя провести и тему можно закрывать.Shamov
20.12.2016 08:47-1Так они и кешируются в том генераторе, который описан в статье. Не все, а только последние два. Но принципиальной разницы нет. Это просто особенность реализации.
Граница очень чёткая. Генератор создаёт элементы последовательности сам, а итератор ходит по готовым… они были созданы внешней по отношению к нему логикой. По большому счёту, в этом и заключается предназначение любого итератора — отделить логику обхода элементов от самих элементов. Если она не отделена, то значит это не итератор.
Итератор по шифрованной последовательности я бы отнёс к итераторам. Процесс расшифровки в большей степени относится к обходу, чем к хранению.
iCpu
20.12.2016 10:59По-хорошему, генератор не должен иметь состояния и должен же выдавать полную последовательность элементов из входных параметров, а итератор должен лишь позволять двигаться по контейнеру. То, что генератор может быть итеративным — уже нарушение синтетики, так как в генераторе сохраняется состояние, чего быть не должно. Но одно дело синтетика, а другое — удобство.
Иными словами, я частично принимаю ваши доводы, но всё ещё не согласен с чистым термином «генератор». Хотя бы потому, что «генератором» так же зовётся всеми любимый Lorem Ipsum, не предполагающий итераций. «Итеративный генератор» уже лучше, так как раскрывает суть, но хотелось бы чего-нить по поэтичнее.Shamov
20.12.2016 12:08-1Тогда я немного уточню свою позицию. Чистый итератор — это когда вообще нет генерации. Только итерация по готовым значениям. (I have a pen.) Чистый генератор — это когда никакой итерации нет вообще. Подаём на вход аргумент и получаем на выходе соответствующее ему значение. (I have an apple.) Соединяем их вместе и получаем генерирующий итератор (apple-pen).
И, по-хорошему, для итераторов по шифрованным последовательностям нужно отдельное название — трансформирующий итератор. Ведь, по сути, они трансформируют значения из шифрованной формы в расшифрованную. Формула, которая в них содержится, работает исключительно с формой значений, а не с их содержанием. И такой трансформирующий итератор аналогичным образом состоит из двух частей — чистого трансформатора (pineapple) и чистого итератора (pen).
И даже можно представить себе конструкцию, которая будет генерировать ключи, итерируя по последовательности натуральных чисел, а затем использовать эти ключи для расшифровки в процессе итерации по зашифрованной последовательности (pen-pineapple-apple-pen).
iCpu
20.12.2016 12:20Лично меня устраивает такой подход, однако он перечёркивает ваш корневой комментарий.
В таком случае технически ph_piter прав в своей терминологии, хоть и немного не точен. (I have a hub). Ваше же замечание хоть и имеет толику смысла, всё же несправедливо в своей категоричности (I have some porn). Было бы неплохо, если бы вы как-либо популяризировали этот подход, добавив статью на вики, но в рамках комментов тема раскрыта.
[ roscomnadzor ]Shamov
20.12.2016 13:10-1Мой наезд на автора вызван тем, что он неверно расставил акценты. Сделав генерирующий итератор, он назвал его итератором. Как будто, итераторность — это главное свойство. В то время как в итераторной части нет абсолютно ничего интересного, а вся суть заключается в генераторном аспекте.
Со своей стороны я готов признать лишь то, что был неточен в тот момент, когда назвал генераторный итератор просто генератором. Просто мне кажется очевидным, что когда говоришь о генераторе в контексте итеративного процесса, само собой подразумевается, что это генерирующий итератор. Лично я никогда не заморачиваюсь на точности терминологии. Когда привязываешь генератор к последовательности или контейнеру, понятно, что он становится итерирующим. Нет смысла это как-то специально оговаривать. Можно спокойно продолжать называть его генератором.
yatagarasu
18.12.2016 16:27+1В общем-то вы сами запутались в своих собственных абстракциях.
Все значения последовательности Фибоначчи вполне «уже» существуют, не зависимо от того посчитали мы их или нет. У них есть вполне определенная очередность. Так что по ним вполне возможно итерировать как вперед так и назад.
Генераторы скщнствуют для более абстрактных «последовательностей», для которых очередность элементов либо не определена либо не имеет смысла. Два генератора невозможно сравнить, два итератора — вполне.Shamov
18.12.2016 19:06-1А, ну-ка, проитерируйте по числам Фибоначчи назад больше, чем на два шага, значения которых сохранены в генераторе.
На самом деле, мне, конечно, понятно, из-за чего у вас (и не только) возникает путаница. Описанный автором генератор одновременно является и итератором по неявно существующей последовательности натуральных чисел (номеров чисел Фибоначчи). И только в этой его итераторной части его имеет смысл сравнивать с другим итератором. Та же часть, которая отвечает непосредственно за числа Фибоначчи, безусловно, является генератором. И сравнивать её с чем-либо не имеет смысла. Причём даже сам автор это понимает. В его ограничительном итераторе предыдущие числа равны нулю. Полноценным генератором он не является. Вы не можете получить из него соответствующее число Фибоначчи. Хотя можете двигать его как вперёд, так и назад, меняя тем самым границу диапазона.
lemelisk
19.12.2016 00:14+2А, ну-ка, проитерируйте по числам Фибоначчи назад больше, чем на два шага, значения которых сохранены в генераторе.
Это несложно:Fn-2 = Fn - Fn-1Shamov
19.12.2016 07:10Ну да, логично. Зная два соседних числа, можно продвигаться назад точно так же, как и вперёд. Об этом я не подумал. Но тогда возникает другой вопрос. Почему чувак из статьи сделал только
forward-итератор? Почему не сделалbidirectional? Или хотя бы ещё иreverseотдельно… и функции перехода отforwardкreverseи обратно? Ведь если это не генератор, а итератор, то все эти вещи, как бы, тоже не помешают...
bfDeveloper
16.12.2016 18:49+3Здесь должна быть эта ссылка:
https://github.com/ericniebler/range-v3
Библиотека диапазонов, которая покрывает не только рассмотренный случай генераторов, но и более сложные операции. Вообще очень полезна вся линейка постов, автор которых Eric Niebler.
TargetSan
Увы, в стандарте до сих пор нет хоть какой-то подборки готовых адаптеров итераторов. Зато с 17-го есть зета-функция Римана — ну очень важная и нужная абсолютно всем программистам на С++.
erwins22
Удивитесь, но она есть и в tensorflow,
Да и добавление математических функций ни у кого не должно вызывать возражений, а так вызов такой функции можно будет эффективно транслировать на графическую карту через OpenAcc.
TargetSan
Это был горький сарказм если что. Про то, что в стандарт засунули то, что могло спокойно сидеть в tensorflow и дальше. Зато нет целой кучи базовых строительных блоков.
Зета-функция, полиномы Лежандра и т.п. безусловно важные и нужные штуки — но применяемые в довольно узкой области.
erwins22
Там множество комитетов и они фактически независимы.
Вы хотите, что бы был единый комитет согласовывающий все изменения, все нюансы?
Добавление мат функций никак не задерживает процесс принятия других изменений.
TargetSan
Увы, я в курсе, что там куча комитетов.
Я хотел бы, чтобы велась разработка не стандарта, а референсного компилятора с участием всех заинтересованных сторон. Я так же в курсе, что "не судьбец".
То, что их добавление не задерживает принятие стандарта, не повод их в стандарт добавлять. Ещё 200 страниц к талмуду. Причём с пользой для очень узкого круга пользователей.
erwins22
Из 10 человек, которые писали/пишут на С++ у ВСЕХ(мои знакомые) возникала такая потребность в мат функциях (редко).
А вот потребности в готовых итераторов не возникало ни у кого.
TargetSan
Ладно, давайте закроем тему. Иначе сейчас будем спорить, у кого выборка репрезентативней.