Зачем использовать итераторы вместо индексов массивов?

Возьмите следующие две строки кода:

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
}

Мне сказали, что второй способ предпочтительнее. Почему именно это?

Первая форма эффективна, только если 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, в котором говорится об этом типе итерации; это называется «внутренний итератор». Посмотрите здесь тоже.

Потому что это более объектно-ориентированный. если вы выполняете итерацию с индексом, вы предполагаете:

а) что эти объекты упорядочены
б) что эти объекты могут быть получены с помощью индекса
в) что приращение индекса будет поражать каждый элемент
г) что этот индекс начинается с нуля

С итератором вы говорите: «Дайте мне все, чтобы я мог с ним работать», не зная, что лежит в основе реализации. (В Java есть коллекции, к которым нельзя получить доступ через индекс)

Кроме того, при использовании итератора не нужно беспокоиться о выходе за пределы массива.

Еще одна приятная вещь об итераторах заключается в том, что они лучше позволяют вам выражать (и применять) ваши 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
}

Я, вероятно, должен указать, что вы также можете позвонить

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, но я не могу думать ни о какой другой причине.

Вторая форма представляет то, что вы делаете более точно. В вашем примере, на самом деле вам не важно значение i - все, что вам нужно, это следующий элемент в итераторе.

Узнав немного больше о предмете этого ответа, я понимаю, что это было немного упрощением. Разница между этим циклом:

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

Индексация требует дополнительной mulоперации. Например, для vector<int> v, компилятор преобразует v[i]в &v + sizeof(int) * i.

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

Никто еще не упомянул, что одним из преимуществ индексов является то, что они не становятся недействительными, когда вы добавляете в непрерывный контейнер, такой как std::vector , так что вы можете добавлять элементы в контейнер во время итерации.

Это также возможно с итераторами, но вы должны позвонить reserve(), и, следовательно, должны знать, сколько элементов вы добавите.

Уже несколько хороших моментов. У меня есть несколько дополнительных комментариев:

1. Предполагая, что мы говорим о стандартной библиотеке C ++, «вектор» подразумевает контейнер произвольного доступа, который имеет гарантии на C-массив (произвольный доступ, непрерывное расположение памяти и т. Д.). Если бы вы сказали «some_container», многие из приведенных выше ответов были бы более точными (независимость от контейнера и т. Д.).

2. Чтобы устранить любые зависимости от оптимизации компилятора, вы можете переместить some_vector.size () из цикла в индексированном коде, например, так:

   const size_t numElems = some_vector.size ();
   для (size_t я = 0; я 

3. Всегда предварительно увеличивайте итераторы и обрабатывайте постинкременты как исключительные случаи.

Таким образом, предполагая и индексируя std::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 ++ 11 , вы также можете использовать цикл на основе диапазонаfor для перебора вашего вектора (или любого другого контейнера) следующим образом:

for (auto &item : some_vector)
{
     //do stuff
}

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

Ноты:

• Если вам нужен индекс элемента в вашем цикле и он operator[]существует для вашего контейнера (и достаточно быстр для вас), тогда лучше идти первым путем.
• Цикл на основе диапазона forне может использоваться для добавления / удаления элементов в / из контейнера. Если вы хотите сделать это, то лучше придерживайтесь решения, данного Брайаном Мэтьюсом.
• Если вы не хотите , чтобы изменить элементы в контейнере, то вы должны использовать ключевое слово constследующим образом : for (auto const &item : some_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;
    }

}

Обе реализации верны, но я бы предпочел цикл for. Поскольку мы решили использовать Vector, а не какой-либо другой контейнер, использование индексов было бы лучшим вариантом. Использование итераторов с векторами потеряло бы само преимущество объектов в непрерывных блоках памяти, что облегчает их доступ.

Я чувствовал, что ни один из ответов здесь не объясняет, почему я люблю итераторы как общую концепцию индексации в контейнеры. Обратите внимание, что большая часть моего опыта использования итераторов на самом деле не из 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 фиксированной длины , превращается в простую и эффективную арифметику указателей , что делает его действительно абстракцией с нулевой стоимостью.