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

StackOverflow https://stackoverflow.com/questions/56347

  •  09-06-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

Есть ли еще какие-то тонкости, которые мне не хватает?

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

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

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

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

Как уже упоминалось, итераторы 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";
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top