Итераторы в C++ (stl) против Java, есть ли концептуальная разница?
Я возвращаюсь к C++ после того, как ненадолго отлучился и пытаюсь отряхнуть старую дыню.
В 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 взял то, что было, и построил вокруг этого соглашение.
Есть ли какая-то тонкость в этом, которую мне не хватает?
«... пытаюсь отряхнуть старую дыню» - гениальная фраза.
Ответы 9
Да, есть большая концептуальная разница. C++ использует разные «классы» итераторов. Некоторые из них используются для произвольного доступа (в отличие от Java), некоторые - для прямого доступа (например, java). В то время как другие используются для записи данных (например, для использования с transform).
См. Концепцию итераторов в Документация по C++:
- Входной итератор
- Итератор вывода
- Вперед итератор
- Двунаправленный итератор
- Итератор произвольного доступа
Они гораздо более интересны и мощны по сравнению с крошечными итераторами Java / C#. Надеюсь, эти соглашения будут кодифицированы с использованием C++ 0x Концепции.
В библиотеке Java есть ListIterator, который является двунаправленным и произвольным.
«Произвольный доступ и двунаправленный» - противоречие. Вы имеете в виду, что ListIterator является двунаправленным и предлагает доступ для чтения и записи.
ПРИМЕЧАНИЕ: ListIterator включает в себя нет все требования «двунаправленного». Он не поддерживает копирование, т. Е. Вы не можете сохранить свое текущее местоположение, чтобы вернуться к нему позже. См. Отдельный ответ ниже.
Итераторы эквивалентны указателям только в тривиальном случае последовательного перебора содержимого массива. Итератор может предоставлять объекты из любого количества других источников: из базы данных, из файла, из сети, из других вычислений и т. д.
Указатель на элемент массива действительно является итератором в массиве.
Как вы говорите, в 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)
Категории итераторов определяют, что вы можете, а что не можете делать с данным итератором.
Возможно, немного более теоретически. Математически коллекции в C++ можно описать как полуоткрытый интервал итераторов, а именно один итератор, указывающий на начало коллекции, и один итератор, указывающий сразу позади на последний элемент.
Это соглашение открывает множество возможностей. Как работают алгоритмы в C++, все они могут применяться к подпоследовательностям более крупной коллекции. Чтобы такая вещь работала в Java, вы должны создать оболочку вокруг существующей коллекции, которая возвращает другой итератор.
Еще один важный аспект итераторов уже упоминался Фрэнком. Есть разные концепции итераторов. Итераторы Java соответствуют итераторам ввода C++, т.е. это итераторы только для чтения, которые могут увеличиваться только на один шаг за раз и не могут идти назад.
С другой стороны, у вас есть указатели C, которые точно соответствуют концепции C++ итератора с произвольным доступом.
В целом, C++ предлагает гораздо более богатую и более чистую концепцию, которую можно применить к гораздо большему количеству задач, чем указатели C или итераторы Java.
В Java есть ListIterator, который может работать в обоих направлениях.
Я знаю, что это старый ответ, но ... 1. Двунаправленный означает, что он движется вперед и назад. 2.Случайный доступ означает, что вы можете обращаться к элементам в произвольном непоследовательном порядке случайный (например, индексированный доступ). 3. Доступ для чтения / записи - это другая концепция, полностью называемая изменчивостью. Итераторы только для чтения могут быть только вперед или назад. Это две независимые переменные. Меня больше интересует вопрос о перемещении итератора или его сбросе и повторном использовании итератора. Sun явно имеет в виду использование интерфейсов, но оно кажется недостаточно развитым.
@SinthiaV Хм. Я не знаю, что делать с этим комментарием. Я, конечно, знаю об этих различиях, и ничто в моем ответе не противоречит этому (кроме того факта, что я использую концепцию C++, когда говорю об «итераторе ввода»; эта концепция действительно смоделирована на итераторе вперед, доступном только для чтения) .
Итераторы библиотеки C++ (часть, ранее известная как STL) предназначены для совместимости с указателями. Java без арифметики указателей могла быть более удобной для программистов.
В C++ приходится использовать пару итераторов. В Java вы используете либо итератор, либо коллекцию. Итераторы должны быть связующим звеном между алгоритмом и структурой данных. Код, написанный для версии 1.5+, редко нуждается в упоминании итераторов, если только он не реализует конкретный алгоритм или структуру данных (в чем у большинства программистов нет необходимости). Поскольку Java использует подмножества динамического полиморфизма и тому подобное, с ними намного проще справиться.
Для меня принципиальное отличие состоит в том, что итераторы Java указывают между элементами, тогда как итераторы C++ STL указывают на элементы.
Итераторы C++ являются обобщением концепции указателя; они делают его применимым к более широкому кругу ситуаций. Это означает, что их можно использовать для таких вещей, как определение произвольных диапазонов.
Итераторы Java являются относительно глупыми перечислителями (хотя и не такими плохими, как C#; по крайней мере, Java имеет ListIterator и может использоваться для изменения коллекции).
Как уже упоминалось, итераторы 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, теряя универсальность и возможность использовать типы контейнеров связанных списков.
Поскольку в этом примере использовалась только механика прямой итерации, я смог поменять местами список с помощью без проблем. Это очень важно для создания общих алгоритмов, таких как поиск, отложенная инициализация и оценка, сортировка и т. д.
Неспособность сохранить состояние наиболее близко соответствует итератору ввода STL C++, на котором построено очень мало алгоритмов.
Да, но какие полезные алгоритмы! std :: find (_if), std :: count и std :: copy являются основой большого количества важного кода.
Этот пример неискренний. Он полагается на = operator, работающий по-разному в Java и C++. В C++ он выполняет копию объекта в новый объект (неглубокий снимок), тогда как в Java (и C#) он копирует ссылку, поэтому обе переменные работают с одним и тем же объектом. Поведение C++ при копировании означает, что cur может быть расширен, не затрагивая a, с использованием синтаксиса выше, в то время как в Java или C# базовый итератор будет изменен. Используя clone(), вы можете иметь такое же поведение на Java.
Есть много хороших ответов о различиях, но я чувствовал, что то, что меня больше всего раздражает с итераторами Java, не было подчеркнуто - вы не можете прочитать текущее значение несколько раз. Это действительно полезно во многих сценариях, особенно при объединении итераторов.
В C++ у вас есть метод для продвижения итератора и чтения текущего значения. Чтение его значения не продвигает итерацию; так что вы можете прочитать его несколько раз. Это невозможно с итераторами Java, и я в конечном итоге создаю оболочки, которые делают это.
Примечание: один простой способ создать оболочку - использовать существующую - PeekingIterator от Guava.
Это точно. Итераторы Java объединяют операции перемещения позиции, получения текущего значения и проверки, если они выходят за пределы допустимого диапазона, тогда как в идеале они должны быть отдельными и отличными.
Вы в значительной степени сами это сказали. В Java концепции диапазона и итератора в значительной степени объединены. В C++ итератор не имеет представления о том, в какой диапазон элементов он входит, и фактически может быть частью нескольких диапазонов (от начала до конца, от начала до конца - 1, от начала + 3 до конца, от начала до начала + 6 и так далее.)