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

Question

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

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

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

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

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 взял то, что существовало и строил вокруг него конвенции.

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

Answer 1

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

См концепцию итераторы в C++ Documentation:

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

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

Answer 2

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

Answer 3

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

Как вы говорите, на 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)

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

this example Рассмотрим:

// 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, теряя универсальность и возможность использовать типы контейнеров связанных списков.

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

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

Answer 9

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

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

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