Цепочные iteratorы для C ++

Python’s itertools реализует цепной iterator, который по существу объединяет несколько разных iteratorов, чтобы обеспечить все, от одного iteratorа.

Есть что-то подобное в C ++? Быстрый взгляд на библиотеки ускорения не показал ничего подобного, что для меня удивительно. Трудно ли реализовать эту функциональность?

Пришел к этому вопросу, исследуя аналогичную проблему.

Даже если вопрос старый, теперь во время C ++ 11 и boost 1.54 это довольно легко сделать, используя библиотеку Boost.Range . В нем есть функция join -function , которая может объединяться в два диапазона в один. Здесь вы можете взять штрафные санкции за производительность, поскольку в качестве категории нового диапазона используется наименьшая концепция общего диапазона (например, диапазон одиночного прохода или дальность вперед и т. Д.), А во время итерации iterator может быть проверен, если ему нужно перейти к новому диапазону, но ваш код можно легко написать, например:

 #include  #include  #include  #include  int main() { std::deque deq = {0,1,2,3,4}; std::vector vec = {5,6,7,8,9}; for(auto i : boost::join(deq,vec)) std::cout << "i is: " << i << std::endl; return 0; } 

В C ++ iterator обычно не имеет смысла вне контекста начала и конца диапазона. Сам iterator не знает, где начинаются и заканчиваются. Поэтому, чтобы сделать что-то подобное, вам вместо этого нужно объединить диапазоны iteratorов – диапазон – это пара (начало, конец) iteratorов.

Взгляните на документацию boost :: range . Он может предоставлять инструменты для построения цепочки диапазонов. Единственное отличие состоит в том, что они должны быть одного типа и возвращать одинаковый тип iteratorа. Возможно, также будет возможно сделать этот дополнительный родословный для объединения разных типов диапазонов с чем-то вроде any_iterator, но, возможно, нет.

Я написал один раньше (на самом деле, просто для объединения двух пар iteratorов вместе). Это не так сложно, особенно если вы используете iterator_facade boost.

Создание входного iteratorа (что эффективно делает chain Python) – простой первый шаг. Поиск правильной категории для iteratorа, связывающего комбинацию разных категорий iteratorов, остается как упражнение для читателя ;-).

То, что вы в основном ищете, – это iterator фасада, который абстрагирует прохождение через несколько последовательностей.

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

Если это так, вы можете посмотреть на any_iterator из adobe labs: http://stlab.adobe.com/classadobe_1_1any__iterator.html

Этот iterator даст вам возможность итерации по любому типу последовательности во время выполнения. Для цепочки у вас будет вектор (или массив) из 3-х кортежей any_iterators, т. Е. Три any_iterators для каждого диапазона, который вы соединяете вместе (вам нужно три, чтобы перебирать вперед или назад, если вы просто хотите перебрать вперед два, будет достаточно).

Предположим, что вы хотите цепную итерацию через последовательность целых чисел:

(Недопустимый код psuedo-c ++)

typedef adobe :: any_iterator AnyIntIter;

struct AnyRange {AnyIntIter begin; AnyIntIter curr; Конец AnyIntIter; };

Вы можете определить диапазон, например:

int int_array [] = {1, 2, 3, 4}; AnyRange sequence_0 = {int_array, int_array, int_array + ARRAYSIZE (int_array)};

Класс RangeIterator будет иметь std :: vector.

  class RangeIterator { public: RangeIterator() : curr_range_index(0) {} template  void AddAnyRange(Container& c) { AnyRange any_range = { c.begin(), c.begin(), c.end() }; ranges.push_back(any_range); } // Here's what the operator++() looks like, everything else omitted. int operator++() { while (true) { if (curr_range_index > ranges.size()) { assert(false, "iterated too far"); return 0; } AnyRange* any_range = ranges[curr_range_index]; if (curr_range->curr != curr_range->end()) { ++(curr_range->curr); return *(curr_range->curr); } ++curr_range_index; } } private: std::vector ranges; int curr_range_index; };  

Однако я хочу отметить, что это решение происходит очень медленно. Лучший, более похожий на C ++ подход – это просто сохранить все указатели на объекты, на которых вы хотите работать, и повторить их. Кроме того, вы можете применить функтора или посетителя к своим диапазонам.

Не в стандартной библиотеке. У Boost может быть что-то.

Но на самом деле такая вещь должна быть тривиальной для реализации. Просто сделайте себе iterator с вектором iteratorов в качестве участника. Какой-то очень простой код для оператора ++, и вы там.

Проверить библиотеки шаблонов просмотров (VTL) . Он может не предоставлять «прикованный iterator» напрямую. Но я думаю, что у него есть все необходимые инструменты / шаблоны для реализации вашего собственного «цепного iteratorа».


На странице VTL:

Представление представляет собой контейнерный адаптер, который предоставляет интерфейс контейнера для

  1. части данных или
  2. перегруппировка данных или
  3. преобразованные данные или
  4. подходящая комбинация наборов данных

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

По сравнению с интеллектуальными iteratorами представления – это просто умные фабрики iteratorов.

Никакой функциональности в boost, которая реализует это, насколько мне известно, я сделал довольно обширный поиск.

Я думал, что на прошлой неделе я бы это легко реализовал, но я столкнулся с проблемой: STL, который поставляется с Visual Studio 2008, когда включена проверка диапазона, не позволяет сравнивать iteratorы из разных контейнеров (т. Е. Вы не можете сравнивать somevec1.end () с somevec2.end ()). Внезапно стало намного сложнее реализовать это, и я еще не совсем решил, как это сделать.

Я писал другие iteratorы в прошлом, используя iterator_facade и iterator_adapter от boost, которые лучше, чем писать «сырые» iteratorы, но я все еще нахожу, что написание пользовательских iteratorов на C ++ довольно беспорядочно.

Если кто-то может опубликовать некоторый псевдокод о том, как это можно было бы сделать / без / сравнения iteratorов из разных контейнеров, я был бы очень обязан.

  • Итерация с циклом цикла или while?
  • Значение проверки существует в std :: map - C ++
  • Как реализовать iterator стиля STL и избежать распространенных ошибок?
  • Разница между Iterator и Listiterator?
  • Как связаны iteratorы и указатели?
  • Сортировка вектора в порядке убывания
  • Что произойдет, если вы увеличите iterator, равный концевому iteratorу контейнера STL
  • Зачем использовать iteratorы вместо индексов массива?
  • Почему генераторы не поддерживают map ()?
  • Java: добавление элементов в коллекцию во время итерации
  • Правила аннулирования Iterator
  • Давайте будем гением компьютера.