Подтвердить что ты не робот

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

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

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

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

В стандартной библиотеке шаблонов С++ итераторы, похоже, представляют тип данных или класс, которые поддерживают оператор ++ и 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
}

Интересная часть здесь заключается в том, что в С++ указатель является итератором для массива. STL взял то, что существовало и строил вокруг него соглашение.

Это какая-то дальнейшая уловка тому, что мне не хватает?

4b9b3361

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

// 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";
}

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

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

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

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

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

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

Ответ 4

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

Как вы говорите, в Java итератор имеет больше знаний о базовом контейнере, чем в С++. Итераторы С++ являются общими, а пара итераторов может обозначать любой диапазон: это может быть поддиапазон контейнера, диапазон по нескольким контейнерам (см. 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)

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

Ответ 5

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

Ответ 6

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

Java-итераторы являются относительно немыми перечислениями (хотя и не такими плохими, как С#, по крайней мере, Java имеет ListIterator и может использоваться для мутирования коллекции).

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

Замечание: один простой способ создать оболочку - использовать существующую - PeekingIterator из Guava.