Итераторы в C++ (stl) и Java, есть ли концептуальная разница?

Я возвращаюсь к С++ после некоторого отсутствия и пытаюсь стряхнуть пыль со старой дыни.

В Java Iterator — это интерфейс к контейнеру, имеющему методы: hasNext(), next() и remove(). Наличие hasNext() означает, что он имеет понятие предела для проходимого контейнера.

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

В стандартной библиотеке шаблонов C++ итераторы представляют тип данных или класс, который поддерживает operator++ и operator==, но не имеет встроенной концепции ограничения, поэтому перед переходом к следующему элементу требуется сравнение. Предел должен быть проверен пользователем, сравнивающим два итератора в обычном случае, когда второй итератор является концом контейнера.

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for (iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

Здесь интересно то, что в C++ указатель является итератором массива. STL взяла то, что уже существовало, и построила вокруг этого соглашение.

Есть ли еще какая-то тонкость, которую я упускаю?


person JeffV    schedule 11.09.2008    source источник
comment
Ты примерно сам это сказал. В Java концепции диапазона и итератора в значительной степени объединены. В C++ итератор не имеет представления о том, частью какого диапазона элементов он является, и фактически может быть частью нескольких диапазонов (от начала до конца, от начала до конца-1, от начала+3 до конца, от начала до начала+6). и так далее.)   -  person jalf    schedule 02.12.2008
comment
...пытаться стряхнуть пыль со старой дыни -- блестящая фраза.   -  person kevinarpe    schedule 07.05.2012


Ответы (9)


Да, есть большая концептуальная разница. C++ использует разные "классы" итераторов. Некоторые используются для произвольного доступа (в отличие от Java), некоторые используются для прямого доступа (например, java). В то время как другие используются для записи данных (для использования, скажем, с transform).

См. концепцию итераторов в документации по C++:

  • Итератор ввода
  • Выходной итератор
  • Вперед итератор
  • Двунаправленный итератор
  • Итератор произвольного доступа

Они намного интереснее и мощнее по сравнению с тщедушными итераторами Java/C#. Надеемся, что эти соглашения будут систематизированы с использованием концепций C++0x.

person Frank Krueger    schedule 11.09.2008
comment
В библиотеке Java есть ListIterator, который является произвольным доступом и двунаправленным. - person Tom Hawtin - tackline; 11.09.2008
comment
«произвольный доступ и двунаправленность» — это противоречие. Вы имеете в виду, что ListIterator является двунаправленным и предлагает доступ для чтения и записи. - person Konrad Rudolph; 11.09.2008
comment
ПРИМЕЧАНИЕ. ListIterator не включает все требования «двунаправленности». Он не поддерживает копирование, т. е. вы не можете сохранить свое текущее местоположение, чтобы вернуться к нему позже. См. отдельный ответ ниже. - person Aaron; 02.10.2008

Возможно, немного более теоретически. Математически коллекции в C++ можно описать как полуоткрытый интервал итераторов, а именно один итератор, указывающий на начало коллекции, и один итератор, указывающий сразу за последним элементом.

Это соглашение открывает массу возможностей. Алгоритмы работают в C++ так, что все они могут быть применены к подпоследовательностям большой коллекции. Чтобы такая вещь работала в Java, вы должны создать оболочку вокруг существующей коллекции, которая возвращает другой итератор.

Другой важный аспект итераторов уже упоминался Франком. Существуют разные концепции итераторов. Итераторы Java соответствуют итераторам ввода C++, т. е. они являются итераторами только для чтения, которые могут увеличиваться только на один шаг за раз и не могут идти назад.

С другой стороны, у вас есть указатели C, которые точно соответствуют концепции итератора произвольного доступа C++.

В целом C++ предлагает гораздо более богатую и чистую концепцию, которую можно применять к гораздо более широкому кругу задач, чем указатели C или итераторы Java.

person Konrad Rudolph    schedule 11.09.2008
comment
В Java есть ListIterator, который может работать в обоих направлениях. - person akuhn; 17.04.2009
comment
Я знаю, что это старый ответ, но... 1. Двунаправленный означает, что он движется вперед и назад. 2. Произвольный доступ означает, что вы можете обращаться к элементам в произвольном, непоследовательном, случайном порядке (например, в индексированном доступе). 3. Доступ для чтения/записи — это совсем другая концепция, называемая изменчивостью. Итераторы только для чтения могут быть только прямыми или только обратными. Это две независимые переменные. Меня больше интересует вопрос перемещения итератора или его сброса и повторного использования итератора. Sun явно имеет в виду использование, связанное с интерфейсами, но оно кажется недостаточно развитым. - person Sinthia V; 14.09.2013
comment
@SinthiaV Хм. Я не уверен, что делать с этим комментарием. Я, конечно, знаю об этих различиях, и ничто в моем ответе не противоречит этому (кроме того факта, что я использую концепцию С++, когда говорю об «итераторе ввода»; эта концепция действительно смоделирована на только для чтения) вперед итератор). - person Konrad Rudolph; 14.09.2013

Как уже упоминалось, итераторы Java и C# описывают смешанное положение (состояние) и диапазон (значение), в то время как итераторы C++ разделяют концепции положения и диапазона. Итераторы C++ представляют «где я сейчас» отдельно от «куда я могу пойти?».

Итераторы Java и C# копировать нельзя. Вы не можете восстановить предыдущую позицию. Обычные итераторы C++ могут.

Рассмотрим этот пример:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

Нажмите на ссылку выше, чтобы увидеть вывод программы.

Этот довольно глупый цикл проходит через последовательность (используя только семантику прямого итератора), печатая каждую непрерывную подпоследовательность из 3 элементов ровно один раз (и пару более коротких подпоследовательностей в конце). Но если предположить, что N элементов и M элементов в строке вместо 3, этот алгоритм все равно будет иметь приращения итератора O (N * M) и пространство O (1).

Итераторам в стиле Java не хватает возможности сохранять позицию независимо. Вы либо

  • потерять O (1) пространство, используя (например) массив размера M для хранения истории при повторении
  • нужно будет пройти по списку N раз, что составит O(N^2+N*M) времени
  • или использовать конкретный тип Array с функцией-членом GetAt, потеряв универсальность и возможность использовать типы контейнеров связанных списков.

Поскольку в этом примере использовалась только механика прямой итерации, я смог поменяться местами в списке без проблем. Это критически важно для создания общих алгоритмов, таких как поиск, отложенная инициализация и оценка, сортировка и т. д.

Неспособность сохранять состояние наиболее точно соответствует итератору ввода C++ STL, на котором построено очень мало алгоритмов.

person Aaron    schedule 02.10.2008
comment
Да, но какие полезные алгоритмы! std::find(_if), std::count и std::copy лежат в основе большого количества важного кода. - person Mark Ruzon; 30.10.2009
comment
Этот пример неискренний. Он основан на том, что = operator работает по-разному в Java и C++. В C++ он выполняет копирование объекта в новый объект (неглубокий снимок), а в Java (и C#) копирует ссылку, поэтому обе переменные работают с одним и тем же объектом. Поведение C++ при копировании означает, что cur можно расширить, не затрагивая a, используя приведенный выше синтаксис, в то время как в Java или C# базовый итератор будет изменен. Используя clone(), вы можете иметь такое же поведение в Java. - person BeeOnRope; 20.02.2016

Указатель на элемент массива действительно является итератором в массиве.

Как вы сказали, в Java итератор знает больше о базовом контейнере, чем в C++. Итераторы C++ являются общими, и пара итераторов может обозначать любой диапазон: это может быть поддиапазон контейнера, диапазон нескольких контейнеров (см. http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf или http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) или даже диапазон чисел (см. http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

Категории итераторов определяют, что вы можете и что не можете делать с данным итератором.

person Anthony Williams    schedule 11.09.2008

Для меня принципиальное отличие состоит в том, что итераторы Java указывают между элементами, тогда как итераторы C++ STL указывают на элементы.

person Douglas Leeder    schedule 11.09.2008

Итераторы C++ — это обобщение концепции указателя; они делают его применимым к более широкому кругу ситуаций. Это означает, что их можно использовать для таких вещей, как определение произвольных диапазонов.

Итераторы Java — относительно тупые перечислители (хотя и не такие плохие, как в C#; по крайней мере, в Java есть ListIterator и его можно использовать для изменения коллекции).

person DrPizza    schedule 12.09.2008

Есть много хороших ответов о различиях, но я чувствовал, что вещь, которая меня больше всего раздражает в итераторах Java, не была подчеркнута: вы не можете читать текущее значение несколько раз. Это действительно полезно во многих сценариях, особенно когда вы объединяете итераторы.

В С++ у вас есть метод для продвижения итератора и чтения текущего значения. Чтение его значения не продвигает итерацию; чтобы можно было перечитывать несколько раз. Это невозможно с итераторами Java, и в итоге я создаю оболочки, которые делают это.

Дополнительное примечание: один из простых способов создать оболочку — использовать существующую — PeekingIterator из Гуавы.

person Neo M Hacker    schedule 29.04.2015
comment
Это точно. Итераторы Java объединяют операции перемещения позиции, извлекая текущее значение и проверяя, находятся ли они за пределами диапазона, когда в идеале они должны быть разделены и различны. - person beldaz; 16.08.2017

Итераторы эквивалентны указателям только в тривиальном случае последовательного перебора содержимого массива. Итератор может предоставлять объекты из любого количества других источников: из базы данных, из файла, из сети, из какого-то другого расчета и т. д.

person Marcus Downing    schedule 11.09.2008

Итераторы библиотеки C++ (часть, ранее известная как STL) предназначены для совместимости с указателями. Java без арифметики указателей могла быть более удобной для программистов.

В С++ вам придется использовать пару итераторов. В Java вы либо используете итератор, либо коллекцию. Итераторы должны быть связующим звеном между алгоритмом и структурой данных. Код, написанный для версии 1.5+, редко требует упоминания итераторов, если только он не реализует определенный алгоритм или структуру данных (в чем большинству программистов нет необходимости). Поскольку Java использует динамические подмножества полиморфизма и тому подобное, с ними намного проще обращаться.

person Tom Hawtin - tackline    schedule 11.09.2008