Комментарии 28
Реклама, опять реклама :(.
Хотя бы ссылку на "подробности" сделайте нажимаемой, а то все усилия пропадут втуне.
--
Сарказм: не хочу показаться невежливым, но вы свой ник пробовали в переводчик вставить. Ну, на всякий случай.
Тем временем в нормальных языках программирования у итератора есть два метода: next(), возвращающий элемент и hasNext(), сигнализирующий что всё, элементов больше нету. Это даже можно было бы скукожить до одного метода, возвращающего std::optional. Но нет, давайте изобретать костыли с указателями-хрен-знает-куда (и порожать баги вида "случайно сравнили с end от другой коллекции"), дополнительных объектов в виде sentinel и т.д...
То, что в C++ обозначается универсальным образом (парой итераторов), "в нормальных-то языках" требует дополнительных сущностей, если ты, скажем, хочешь работать только с частью диапазона без создания копий - например, в расте это слайсы, Range, и т.д., причем для каких-то контейнеров работает только что-то одно, а для каких-то только что-то другое, писать, так сказать, контейнеронезависимый универсальный код загребешься.
Если я хочу работать с частью диапазона, я создам итератор-обёртку, который скажет что он кончился раньше. Если я захочу работать только с чётными элементами, я создам итератор, который в next() будет делать два шага вперёд. Если я захочу создать бесконечный итератор, в цикле перебирающий коллекцию, я тоже прекрасно могу это сделать. Не нужны никакие дополнительные сущности.
Замечательно, только вот... что если вам нужно, скажем, разбить существующий диапазон на поддиапазоны? В C++ это можно сделать без проблем, имея пару итераторов "начало-конец", а только лишь с предлагаемыми вами убогими недоитераторами это не сделаешь, нужно работать тогда непосредственно с тем, из чего вы такой итератор получили, да и то не всегда это поможет. Например, в C++ можно разбить диапазон, состоящий из пары итераторов, полученных хоть из массива, хоть из вектора, хоть из хешмапы, на поддиапазоны и закинуть обработку этих поддиапазонов по разным потокам, универсальным образом (опять же пара итераторов, никаких проблем). А что делать с вашим недоитератором? Ладно, окей, забьем на универсальность кода, будем работать с частным случаем - с исходным контейнером, скажем, с HashMap из раста, покажите, пожалуйста, как разбить этот HashMap скажем на 2 или 4 поддиапазона для параллельной обработки его элементов без создания копий.
Я правильно понимаю что вы хотите взять end() - begin(), поделить это на N кусков и пойти с ними что-то делать? Есть подозрение что вычисление концов промежуточных диапазонов на большом количестве коллекций (примерно всех, которые основаны не на массиве внутри) выльется в O(n) и перф будет грустить.
UPD: или даже хуже, это O(n) вообще для каких угодно коллекций, потому что у C++-итератора нет операции "сдвинуться на N". А раз речь про O(n) - ну берем begin, проматываем его полностью чтобы узнать размер, дальше мотаем опять от начала до нужных границ :)
Даже если итератор не умеет в random access, то его инкремент как правило весьма дешевая операция. А вот обработка самих элементов, на которые ссылаются эти итераторы, может быть операцией весьма дорогой, так что распараллеливание принесет свои плюсы, даже если придется пройтись O(n) по самим итераторам.
потому что у C++-итератора нет операции "сдвинуться на N"
Вы бредите.
Ну вот я и говорю, оно прекрасно делается с той же самой ассимптотикой имея на руках только лишь begin.
Ну как вы разобьете нечто, что имеет лишь begin и next, возвращающий очередной элемент, на поддиапазоны? А ваши слова про "у итератора в C++ нет операции сдвинуться на N" - это просто бред человека, который не в теме.
А ваши слова про "у итератора в C++ нет операции сдвинуться на N" - это просто бред человека, который не в теме.
И тут вы такой вжух, и ссылку на описание соответствующего метода.
Да, без проблем, это называется RandomAccessIterator. Скажем std::advance имеет специализации для разных типов итераторов, чтобы можно было универсально с ними работать. Меня всегда поражали люди, которые начинают свои "а вот в нормальных языках-то", не удосужившись изучить матчасть.
имеет специализации
Ну начинается. Процитирую вас же: "писать, так сказать, контейнеронезависимый универсальный код загребешься". То есть в C++ специализации - это норм, а в других языках уже не норм.
Впрочем, учитывая вашу манеру общения с переходом на личности, продолжать беседу не имею ни малейшего желания. Хорошего вечера.
То есть в C++ специализации - это норм, а в других языках уже не норм.
Ну так эти специализации уже есть, в обобщенном коде ты просто пишешь std::advance или std::distance и все, все искаропки работает максимально эффективным образом.
Впрочем, учитывая вашу манеру общения с переходом на личности, продолжать беседу не имею ни малейшего желания. Хорошего вечера.
Ну, ясно.
В том же расте у итераторов есть дополнительные методы, такой универсальный диапазон можно организовать с помощью .skip(a).take(b).
Здорово. Вот берем такой дженерик "в том же расте" (ведь это же "нормальный язык-то"?), который принимает итератор на HashMap или BTreeMap и удваивает значение каждого элемента своего диапазона:
fn mul<
I: std::iter::Iterator<Item = (K, V)>,
K,
V: std::ops::DerefMut<Target = T>,
T: std::ops::MulAssign<i32>,
>(
iter: I,
) {
for (_, mut val) in iter {
*val *= 2;
}
}Пример работы. Пожалуйста, распараллельте (точнее, "партиционируйте") его. Ну так, чтобы внутри этой функции этот iter разбивался на несколько поддиапазонов, представленных отдельными итераторами, которые затем, скажем, передавались бы в функцию, символизирующую распараллеливание работы (старт потока). В C++ это - элементарная задача для функции, принимающей классическую пару итераторов begin/end, относящихся к контейнеру любого типа. Продемонстрируйте, пожалуйста, как это сделать в расте, только не словоблудием, а, как выше написал ваш коллега, "и вы тут такой вжух - и пример рабочего кода" (можно даже и без создания настоящих потоков, ожидания и т.д., просто покажите сам процесс партиционирования).
Тут вы правы, обычный итератор так разбить не получится, как минимум потому что никто не запрещает ему вернуть ссылку на один и тот же элемент дважды подряд, что сразу нарушит правило "только одна &mut ссылка на каждый объект".
С помощью rayon можно сделать так: playground
Это, конечно, не делает явное партиционирование, но вполне честно распарралеливает обработку.
С помощью rayon можно сделать так
Да, именно так, нужен "специальный" итератор, нужны изменения в вызывающем коде. Плюс я не пробовал, но что-то мне подсказывает, что если ты внезапно используешь некий "сторонний" контейнер из какого-то библиотечного крейта, то ты не сможешь "просто так взять и" сделать для него impl trait того же rayon'овского IntoParallelRefMutIterator в своем собственном коде, если тебе захочется распараллелить работу с ним.
Только функция next() нарушает принцип единственной ответственности, делает сразу две вещи, и итератор передвигает, и элемент возвращает.
SRP абсолютно про другое.
То есть, функцию next() делает две вещи, но принцип SRP не нарушает? Вот тут нужны прям подробные пояснения.
Я специально дал ссылку. Цитирую дядюшку Мартина:
A class should have only one reason to change
Также
Another wording for the Single Responsibility Principle is: Gather together the things that change for the same reasons. Separate those things that change for different reasons.
Можно хоть миллион вещей запихивать в одну функцию, если они change for the same reasons, и это не будет нарушением SRP.
Предположу, что в случает с next дело больше в гарантиях исключений.
Есть очень хорошая гарантия, когда при выбрасывании исключения ничего другое в значениях не поменялось (т.е. осталось исходное состояние).
В случае с next, если при копировании возвращаемого значения вылетит исключение (а в C++ это очень возможно), то вы получите итератор на новой позиции. И это не очень хорошо.
Поэтому в стандартной библиотеке C++ любят делить собственно движение по контейнеру и возврат/удаление/итд элемента - тогда можно разделить обработку ошибок/исключений.
Если рассматривать другие языки (где копируются не объекты, а указатели, и при этом ошибок быть не может), то там функционал наподобие next применяется и приветствуется. Просто это другие языки :).
Мой основной посыл был в том что end() не нужен ни для чего кроме итерации с конца (для тех коллекций, у которых вообще говоря есть внятное понятие конца), это источник багов. То, для чего он используется, реализуется гораздо безопаснее через манипуляции с начальным итератором. А штуки вида "проитерируемся только по чётным элементам" кроме как через начальный итератор вообще никак не делаются.
Мой основной посыл был в том что
end()не нужен ни для чего кроме итерации с конца (для тех коллекций, у которых вообще говоря есть внятное понятие конца), это источник багов. То, для чего он используется, реализуется гораздо безопаснее через манипуляции с начальным итератором.
Нет, не только для "итерации с конца". Рассмотрим следующий пример. В нем мы запомнили позиции интересующих нас граничных элементов в ordered set ровно один раз в const хранилище и больше не паримся, а при добавлении элементов в этот set дополнительные элементы, оказавшиеся между этими граничными, автоматически попадают в диапазон и обрабатываются (в данном примере - тупо печатаются). Работает все это легко и просто, так сказать, естественным образом. Теперь давайте подумаем, как реализовать это через манипуляции только лишь с начальным итератором? Хранить "длину" диапазона тут не вариант, она динамическая. Сделать в недоитераторе очередной "специальный" ad hoc метод, который бы сравнивал очередной элемент с образцом и считал элемент, совпадающий с образцом, за end? Ну так это тут для иллюстрации set состоит из char'ов, а если будет что-то "сильно побольше"? Кроме того, это путь в никуда, в растовский std::iter::Iterator вон надобавляли 100500 ad hoc методов с синтаксическим сахаром на полсотни экранов (и постоянно добавляют новые в nightly), а все равно элементарных вещей не умеет. Но их понять можно, у них просто других вариантов нет, но в C++-то зачем эту убогость тащить?
Нужно больше костылей
Sentinel C++20. Пишем свой Sentinel