Зачем использовать итераторы вместо индексов массива?
Возьмите следующие две строки кода:
for (int i = 0; i < some_vector.size(); i++)
{
//do stuff
}
И это:
for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
some_iterator++)
{
//do stuff
}
Мне сказали, что второй способ предпочтительнее. Почему именно это?
25 ответов
Первая форма эффективна, только если vector.size() - быстрая операция. Это верно для векторов, но не для списков, например. Кроме того, что вы планируете делать в теле цикла? Если вы планируете получить доступ к элементам, как в
T elem = some_vector[i];
тогда вы делаете предположение, что контейнер имеет operator[](std::size_t) определены. Опять же, это верно для вектора, но не для других контейнеров.
Использование итераторов приблизит вас к независимости контейнера. Вы не делаете предположений о способности произвольного доступа или быстро size() операция, только то, что контейнер имеет возможности итератора.
Вы могли бы улучшить свой код, используя стандартные алгоритмы. В зависимости от того, чего вы пытаетесь достичь, вы можете использовать std::for_each(), std::transform() и так далее. Используя стандартный алгоритм, а не явный цикл, вы избегаете повторного изобретения колеса. Ваш код, вероятно, будет более эффективным (если выбран правильный алгоритм), верным и пригодным для повторного использования.
Это часть современного процесса идеологической обработки C++. Итераторы - это единственный способ итерировать большинство контейнеров, поэтому вы можете использовать его даже с векторами, чтобы получить правильное мышление. Серьезно, это единственная причина, по которой я это делаю - я не думаю, что когда-либо заменял вектор на контейнер другого типа.
Вау, это все еще получает отрицание после трех недель. Я предполагаю, что не стоит быть немного насмешливым.
Я думаю, что индекс массива более читабелен. Он соответствует синтаксису, используемому в других языках, и синтаксису, используемому для старомодных массивов Си. Это также менее многословно. Эффективность должна быть плохой, если ваш компилятор хорош, и вряд ли есть случаи, когда это все равно имеет значение.
Несмотря на это, я все еще часто использую итераторы с векторами. Я считаю, что итератор является важной концепцией, поэтому я продвигаю его, когда могу.
Потому что вы не привязываете свой код к конкретной реализации списка some_vector. если вы используете индексы массива, это должна быть какая-то форма массива; если вы используете итераторы, вы можете использовать этот код в любой реализации списка.
Представьте, что some_vector реализован с использованием связанного списка. Затем запрос элемента в i-м месте требует выполнения операций i для прохождения списка узлов. Теперь, если вы используете итератор, вообще говоря, он приложит все усилия, чтобы быть максимально эффективным (в случае связанного списка, он будет поддерживать указатель на текущий узел и перемещать его в каждой итерации, требуя только разовая операция).
Так что это обеспечивает две вещи:
- Абстракция использования: вы просто хотите перебрать некоторые элементы, вам все равно, как это сделать
- Спектакль
Я собираюсь быть здесь защитником дьяволов, а не рекомендовать итераторов. Основная причина, почему весь исходный код, над которым я работал, от разработки приложений для настольных компьютеров до разработки игр, не требовал использования итераторов. Все время, когда они не требовались, и, во-вторых, скрытые предположения, путаница кода и ночные кошмары отладки, которые вы получаете с итераторами, делают их ярким примером того, чтобы не использовать его в любых приложениях, требующих скорости.
Даже с точки зрения обслуживания они - беспорядок. Это не из-за них, а из-за псевдонимов, которые происходят за сценой. Откуда я знаю, что вы не реализовали свой собственный список виртуальных векторов или массивов, который делает что-то совершенно отличное от стандартов. Знаю ли я, какой тип сейчас используется во время выполнения? Вы перегрузили оператора, у меня не было времени проверить весь ваш исходный код. Черт, я вообще знаю, какую версию STL вы используете?
Следующая проблема, с которой вы столкнулись при работе с итераторами, - это утечка абстракций, хотя существует множество веб-сайтов, которые подробно обсуждают это с ними.
Извините, я не видел и до сих пор не видел никакой точки в итераторах. Если они абстрагируют от вас список или вектор, тогда как на самом деле вы уже должны знать, с каким вектором или списком вы имеете дело, если вы этого не сделаете, тогда вы просто будете готовиться к некоторым отличным сеансам отладки в будущем.
Возможно, вы захотите использовать итератор, если вы собираетесь добавлять / удалять элементы в векторе, пока вы итерируете его.
some_iterator = some_vector.begin();
while (some_iterator != some_vector.end())
{
if (/* some condition */)
{
some_iterator = some_vector.erase(some_iterator);
// some_iterator now positioned at the element after the deleted element
}
else
{
if (/* some other condition */)
{
some_iterator = some_vector.insert(some_iterator, some_new_value);
// some_iterator now positioned at new element
}
++some_iterator;
}
}
Если вы используете индексы, вам придется перетасовывать элементы вверх / вниз в массиве для обработки вставок и удалений.
Разделение проблем
Очень приятно отделить код итерации от основной проблемы цикла. Это почти дизайнерское решение.
Действительно, итерация по индексу связывает вас с реализацией контейнера. Запрашивая контейнер для начала и конца итератора, включает код цикла для использования с другими типами контейнера.
Кроме того, в std::for_each Кстати, вы СКАЖИТЕ коллекции, что делать, а не спрашиваете что-то о ее внутренностях
Стандарт 0x вводит замыкания, которые значительно упростят использование этого подхода - взгляните на выразительную силу, например, Ruby's [1..6].each { |i| print i; }...
Спектакль
Но, возможно, гораздо более очевидная проблема заключается в том, что, используя for_each Подход дает возможность распараллелить итерацию - блоки потоков Intel могут распределить блок кода по числу процессоров в системе!
Примечание: после обнаружения algorithms библиотека, и особенно foreachЯ потратил два или три месяца на то, чтобы написать смехотворно маленькие операторские структуры-помощники, которые сведут с ума ваших коллег-разработчиков. После этого я вернулся к прагматичному подходу - маленькие петлевые тела не заслуживают foreach больше не надо:)
Обязательным для прочтения справочником по итераторам является книга "Extended STL".
У GoF есть небольшой абзац в конце паттерна Iterator, в котором говорится об этой марке итерации; это называется "внутренний итератор". Посмотрите здесь тоже.
Еще одна приятная вещь об итераторах заключается в том, что они лучше позволяют вам выражать (и применять) ваши const-предпочтения. Этот пример гарантирует, что вы не будете изменять вектор в середине цикла:
for(std::vector<Foo>::const_iterator pos=foos.begin(); pos != foos.end(); ++pos)
{
// Foo & foo = *pos; // this won't compile
const Foo & foo = *pos; // this will compile
}
Помимо всех других отличных ответов... int может быть недостаточно большим для вашего вектора. Вместо этого, если вы хотите использовать индексирование, используйте size_type для вашего контейнера:
for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
Foo& this_foo = myvector[i];
// Do stuff with this_foo
}
Потому что это более объектно-ориентированный. если вы выполняете итерацию с индексом, вы предполагаете:
а) что эти объекты упорядочены
б) что эти объекты могут быть получены с помощью индекса
c) что приращение индекса затронет каждый элемент
d) что этот индекс начинается с нуля
С итератором вы говорите: "Дайте мне все, чтобы я мог с ним работать", не зная, что лежит в основе реализации. (В Java есть коллекции, к которым нельзя получить доступ через индекс)
Кроме того, при использовании итератора не нужно беспокоиться о выходе за пределы массива.
Я, вероятно, должен указать, что вы также можете позвонить
std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);
Итераторы STL в основном существуют, поэтому алгоритмы STL, такие как sort, могут быть независимыми от контейнера.
Если вы просто хотите перебрать все записи в векторе, просто используйте стиль цикла индекса.
Это меньше печатать и легче анализировать для большинства людей. Было бы хорошо, если бы в C++ был простой цикл foreach, не выходя за рамки с помощью магии шаблонов.
for( size_t i = 0; i < some_vector.size(); ++i )
{
T& rT = some_vector[i];
// now do something with rT
}
'
Я не думаю, что это имеет большое значение для вектора. Я предпочитаю использовать индекс самостоятельно, так как считаю его более читабельным, и вы можете использовать произвольный доступ, например, переместиться вперед на 6 пунктов или прыгнуть назад, если это будет необходимо.
Я также хотел бы сделать ссылку на элемент внутри цикла, как это, чтобы не было много квадратных скобок вокруг:
for(size_t i = 0; i < myvector.size(); i++)
{
MyClass &item = myvector[i];
// Do stuff to "item".
}
Использование итератора может быть полезным, если вы считаете, что в будущем вам может понадобиться заменить вектор списком, а также это выглядит более стильно для фанатов STL, но я не могу думать ни о какой другой причине.
Узнав немного больше о предмете этого ответа, я понимаю, что это было немного упрощением. Разница между этим циклом:
for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
some_iterator++)
{
//do stuff
}
И этот цикл:
for (int i = 0; i < some_vector.size(); i++)
{
//do stuff
}
Это довольно минимально. На самом деле, синтаксис выполнения циклов таким образом, мне кажется, растет:
while (it != end){
//do stuff
++it;
}
Итераторы открывают некоторые довольно мощные декларативные функции, и в сочетании с библиотекой алгоритмов STL вы можете делать довольно интересные вещи, которые выходят за рамки администрирования индекса массива.
Вторая форма представляет то, что вы делаете более точно. В вашем примере, на самом деле вас не волнует значение i - все, что вам нужно, это следующий элемент в итераторе.
Индексация требует дополнительного mul операция. Например, для vector<int> vКомпилятор конвертирует v[i] в &v + sizeof(int) * i,
Никто еще не упомянул, что одним из преимуществ индексов является то, что они не становятся недействительными, когда вы добавляете в непрерывный контейнер, такой как std::vector, так что вы можете добавлять элементы в контейнер во время итерации.
Это также возможно с итераторами, но вы должны вызвать reserve()и, следовательно, нужно знать, сколько элементов вы добавите.
Если у вас есть доступ к функциям C++11, вы также можете использовать диапазон на основеforцикл для перебора вашего вектора (или любого другого контейнера) следующим образом:
for (auto &item : some_vector)
{
//do stuff
}
Преимущество этого цикла заключается в том, что вы можете получить доступ к элементам вектора напрямую через itemпеременная, не рискуя испортить индекс или допустить ошибку при разыменовании итератора. Кроме того, заполнитель auto избавляет вас от необходимости повторять тип элементов контейнера, что приближает вас к решению, не зависящему от контейнера.
Заметки:
- Если вам нужен индекс элемента в вашем цикле и
operator[]существует для вашего контейнера (и достаточно быстро для вас), то лучше пойти первым путем. - На основе диапазона
forцикл не может использоваться для добавления / удаления элементов в / из контейнера. Если вы хотите это сделать, лучше придерживайтесь решения, данного Брайаном Мэтьюзом. - Если вы не хотите изменять элементы в своем контейнере, вам следует использовать ключевое слово
constследующее:for (auto const &item : some_vector) { ... }.
Во время итерации вам не нужно знать номер элемента для обработки. Вам просто нужен элемент, и итераторы делают такие вещи очень хорошо.
- Если вам нравится быть ближе к металлу / не доверять деталям их реализации, не используйте итераторы.
- Если вы регулярно переключаете один тип коллекции на другой во время разработки, используйте итераторы.
- Если вам трудно вспомнить, как выполнять итерации разных видов коллекций (возможно, у вас есть несколько типов из нескольких разных внешних источников), используйте итераторы, чтобы объединить средства, с помощью которых вы проходите по элементам. Это относится, например, к переключению связанного списка со списком массивов.
На самом деле, это все, что нужно сделать. Это не так, как если бы вы в любом случае добились большей краткости, и если краткость действительно является вашей целью, вы всегда можете прибегнуть к макросам.
Я не использую итераторы по той же причине, по которой мне не нравятся операторы foreach. При наличии нескольких внутренних циклов достаточно сложно отслеживать глобальные переменные / переменные-члены без необходимости запоминать все локальные значения и имена итераторов. Я считаю полезным использовать два набора индексов для разных случаев:
for(int i=0;i<anims.size();i++)
for(int j=0;j<bones.size();j++)
{
int animIndex = i;
int boneIndex = j;
// in relatively short code I use indices i and j
... animation_matrices[i][j] ...
// in long and complicated code I use indices animIndex and boneIndex
... animation_matrices[animIndex][boneIndex] ...
}
Я даже не хочу сокращать такие вещи, как "animation_matrices[i]", к какому-то случайному "anim_matrix"-named-iterator, например, потому что тогда вы не можете ясно видеть, из какого массива происходит это значение.
Уже несколько хороших моментов. У меня есть несколько дополнительных комментариев:
Предполагая, что мы говорим о стандартной библиотеке C++, "вектор" подразумевает контейнер произвольного доступа, который имеет гарантии на C-массив (произвольный доступ, непрерывное расположение памяти и т. Д.). Если бы вы сказали "some_container", многие из приведенных выше ответов были бы более точными (независимость от контейнера и т. Д.).
Чтобы устранить любые зависимости от оптимизации компилятора, вы можете переместить some_vector.size() из цикла в индексированном коде, например, так:
const size_t numElems = some_vector.size(); для (size_t я = 0; я
Всегда предварительно увеличивайте итераторы и обрабатывайте постинкременты как исключительные случаи.
Так предполагая и индексируемая std::vector<> Подобно контейнеру, нет веской причины предпочитать один другому, последовательно проходя через контейнер. Если вам приходится часто обращаться к старым или новым элементарным индексам, то индексированная версия является более подходящей.
В общем, использование итераторов является предпочтительным, поскольку их используют алгоритмы, а поведение можно контролировать (и неявно документировать), изменяя тип итератора. Вместо итераторов можно использовать расположения массивов, но синтаксическое различие будет выпадать.
Обе реализации верны, но я бы предпочел цикл for. Поскольку мы решили использовать Vector, а не какой-либо другой контейнер, использование индексов было бы лучшим вариантом. Использование итераторов с векторами потеряло бы само преимущество размещения объектов в непрерывных блоках памяти, что облегчает их доступ.
Даже лучше, чем "говорить процессору, что делать" (обязательно), "говорить библиотекам, что вы хотите" (функционал).
Поэтому вместо использования циклов вы должны изучить алгоритмы, представленные в stl.
Я всегда использую индекс массива, потому что многие из моих приложений требуют что-то вроде "отображать уменьшенное изображение". Поэтому я написал что-то вроде этого:
some_vector[0].left=0;
some_vector[0].top =0;<br>
for (int i = 1; i < some_vector.size(); i++)
{
some_vector[i].left = some_vector[i-1].width + some_vector[i-1].left;
if(i % 6 ==0)
{
some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
some_vector[i].left = 0;
}
}
Я чувствовал, что ни один из ответов здесь не объясняет, почему мне нравятся итераторы как общая концепция по сравнению с индексированием в контейнерах. Обратите внимание, что большая часть моего опыта использования итераторов на самом деле исходит не из C++, а из языков программирования более высокого уровня, таких как Python.
Интерфейс итератора предъявляет меньше требований к потребителям вашей функции, что позволяет потребителям делать с ней больше.
Если все, что вам нужно, это возможность пересылки итераций, разработчик не ограничивается использованием индексируемых контейнеров - он может использовать любой класс, реализующий operator++(T&), operator*(T) а также operator!=(const &T, const &T).
#include <iostream>
template <class InputIterator>
void printAll(InputIterator& begin, InputIterator& end)
{
for (auto current = begin; current != end; ++current) {
std::cout << *current << "\n";
}
}
// elsewhere...
printAll(myVector.begin(), myVector.end());
Ваш алгоритм работает в том случае, если он вам нужен - итерация по вектору, - но он также может быть полезен для приложений, которые вы не обязательно ожидаете:
#include <random>
class RandomIterator
{
private:
std::mt19937 random;
std::uint_fast32_t current;
std::uint_fast32_t floor;
std::uint_fast32_t ceil;
public:
RandomIterator(
std::uint_fast32_t floor = 0,
std::uint_fast32_t ceil = UINT_FAST32_MAX,
std::uint_fast32_t seed = std::mt19937::default_seed
) :
floor(floor),
ceil(ceil)
{
random.seed(seed);
++(*this);
}
RandomIterator& operator++()
{
current = floor + (random() % (ceil - floor));
}
std::uint_fast32_t operator*() const
{
return current;
}
bool operator!=(const RandomIterator &that) const
{
return current != that.current;
}
};
int main()
{
// roll a 1d6 until we get a 6 and print the results
RandomIterator firstRandom(1, 7, std::random_device()());
RandomIterator secondRandom(6, 7);
printAll(firstRandom, secondRandom);
return 0;
}
Попытка реализовать оператор квадратных скобок, который делает что-то похожее на этот итератор, будет надуманной, в то время как реализация итератора относительно проста. Оператор квадратных скобок также влияет на возможности вашего класса, которые вы можете индексировать к любой произвольной точке, что может быть сложно или неэффективно реализовать.
Итераторы тоже поддаются декорированию. Люди могут писать итераторы, которые используют итератор в своем конструкторе и расширяют его функциональность:
template<class InputIterator, typename T>
class FilterIterator
{
private:
InputIterator internalIterator;
public:
FilterIterator(const InputIterator &iterator):
internalIterator(iterator)
{
}
virtual bool condition(T) = 0;
FilterIterator<InputIterator, T>& operator++()
{
do {
++(internalIterator);
} while (!condition(*internalIterator));
return *this;
}
T operator*()
{
// Needed for the first result
if (!condition(*internalIterator))
++(*this);
return *internalIterator;
}
virtual bool operator!=(const FilterIterator& that) const
{
return internalIterator != that.internalIterator;
}
};
template <class InputIterator>
class EvenIterator : public FilterIterator<InputIterator, std::uint_fast32_t>
{
public:
EvenIterator(const InputIterator &internalIterator) :
FilterIterator<InputIterator, std::uint_fast32_t>(internalIterator)
{
}
bool condition(std::uint_fast32_t n)
{
return !(n % 2);
}
};
int main()
{
// Rolls a d20 until a 20 is rolled and discards odd rolls
EvenIterator<RandomIterator> firstRandom(RandomIterator(1, 21, std::random_device()()));
EvenIterator<RandomIterator> secondRandom(RandomIterator(20, 21));
printAll(firstRandom, secondRandom);
return 0;
}
Хотя эти игрушки могут показаться обыденными, нетрудно представить себе использование итераторов и декораторов итераторов для выполнения мощных вещей с простым интерфейсом - украшения итератора с прямым доступом для результатов базы данных с помощью итератора, который создает объект модели из одного результата, например. Эти шаблоны позволяют выполнять итерацию бесконечных наборов с эффективным использованием памяти и с помощью фильтра, подобного тому, который я написал выше, потенциально ленивую оценку результатов.
Частью мощи шаблонов C++ является интерфейс вашего итератора, который при применении к подобным массивам C фиксированной длины превращается в простую и эффективную арифметику с указателями, что делает его абстракцией с действительно нулевой стоимостью.