Итерация в обратном направлении

Question

Предположим, у меня есть vector<int> myvec, и я хочу перебрать все элементы в обратном порядке. Я могу придумать несколько способов сделать это:

for (vector<int>::iterator it = myvec.end() - 1; it >= myvec.begin(); --it)
{
    // do stuff here
}

for (vector<int>::reverse_iterator rit = myvec.rbegin(); rit != myvec.rend(); ++rit)
{
    // do stuff here
}

for (int i = myvec.size() - 1; i >= 0; --i)
{
    // do stuff here
}

Итак, мой вопрос, когда я должен использовать каждый? Есть ли разница? Я знаю, что первое опасно, потому что если я передам пустой вектор, то myvec.end() - 1 не определено, но есть ли другие опасности или неэффективности с этим?

Answer 1

Версия reverse_iterator показывает намерение и работает во всех контейнерах, независимо от их содержимого.

Первый имеет недостаток, который вы описываете. Он также использует >=, что не будет работать для итераторов без произвольного доступа.

Третий имеет проблему, что i является int. Он не сможет удержать столько, сколько size() может потенциально вернуться. Создание без знака работает (vector<int>::size_type), но тогда у нас та же проблема, что и у решения первого. (0U - 1 -> Funky terminating checks -> :|)

Answer 2

Как правило, ничего из вышеперечисленного. Вместо этого вы должны обычно сидеть и расслабляться в течение нескольких секунд, выяснить, какой алгоритм вы хотите применить, и вообще забыть о написании цикла. Скорее всего, вы будете использовать reverse_iterator с ним, но в зависимости от того, что вы пытаетесь достичь, это не всегда будет так (например, см. std::copy_backwards).

Answer 3

Лично я бы пошел со вторым.

Как вы указали, первый требует, чтобы вы завернули цикл в if (!myvec.empty()), чтобы избежать неопределенного поведения.

В последнем случае вам, вероятно, следует использовать vector<int>::size_type или size_t, и в этом случае >= 0 неправильный, вам нужно будет сделать != (size_t)-1 или подобное.

Версия reverse_iterator, следовательно, чище.

Answer 4

Что касается первой версии, вы также неизбежно закончите уменьшением итератора begin() в конце цикла (неопределенное поведение).

Для этого был создан reverse_iterator.

Третий может работать несколько лучше, если вы используете более спорную форму:

for (size_t i = vec.size(); i --> 0; )

Это может быть идиома, если люди перестанут сопротивляться. Он использует подходящий тип счетчика (без знака) и содержит мнемонику для легкого запоминания и распознавания.

Answer 5

Есть четвертый вариант (не обязательно хороший вариант, но он существует). Вы можете использовать итераторы двунаправленного / произвольного доступа таким образом, чтобы имитировать, как реализованы обратные итераторы, чтобы избежать проблемы с myvec.end()-1 на пустом итераторе:

for (vector<int>::iterator it = myvec.end(); it != myvec.begin(); --it)
{
    // convert the loop controlling iterator to something that points
    //  to the item we're really referring to

    vector<int>::iterator true_it = it;
    --true_it;


    // do stuff here
    //  but always dereference `true_it` instead of `it`
    //  this is essentially similar to the way a reverse_iterator 
    //  generally works

    int& x = *true_it;
}

или даже:

for (vector<int>::iterator it = myvec.end(); it != myvec.begin();)
{
    // decrement `it` before the loop executes rather than after
    //  it's a bit non-idiomatic, but works
    --it;

    int& x = *it;

    // do stuff...
}

Как я уже сказал, это не обязательно хороший вариант (я думаю ответ Джерри Коффина - это подход, на который вы должны обратить внимание в первую очередь), но я думаю, что он представляет интерес, поскольку показывает, как работают обратные итераторы сцены - и это избавляет от необходимости конвертировать reverse_iterator в итератор для тех случаев, когда вы можете использовать итератор с чем-то, что не принимает reverse_iterator (преобразование reverse_iterator s в iterator s всегда кажется у меня болит голова, поэтому я часто избегаю reverse_iterators, чтобы избежать головной боли). Например, если вы хотите вызвать insert () для местоположения, обратный итератор ссылается на:

// if `it` is a reverse iterator, a call to insert might have to look something like:

myvec.insert( --(it.base()), 42 );  // assume that you know the current vector capacity
                                    //  will avoid a reallocation, so the loop's 
                                    //  iterators won't be invalidated

// if `it` is a normal iterator...

myvec.insert( it, 42 );

Answer 6

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