Может закончиться() быть дорогостоящей операцией для stl-контейнеров

В https://doc-snapshots.qt.io/qtcreator-extending/coding-style.html рекомендуется писать для циклов, как показано ниже:

Container::iterator end = large.end();
for (Container::iterator it = large.begin(); it != end; ++it) {
        //...;
}

вместо

for (Container::iterator it = large.begin(); it != large.end(); ++it) {
        //...;
}

Так как я редко видел этот стиль в любом коде, я хотел бы знать, действительно ли последовательный вызов end() добавляет заметные накладные расходы во время выполнения больших циклов над контейнерами stl или компиляторы уже оптимизируют такие случаи.

Изменить: Как многие из очень хороших комментариев отметили: этот вопрос действителен только в том случае, если код внутри цикла не изменяет конечный итератор. В противном случае, конечно, повторный вызов конца является обязательным.

Ответ 1

В стандарте С++ 11 (§ 23.2.1) указывается, что end имеет сложность O (1), поэтому соответствующая реализация будет иметь одинаковые характеристики производительности для обеих версий.

Тем не менее, если компилятор не может доказать, что возвращаемое значение end никогда не изменится, то вытащить end из цикла может быть быстрее на некоторую постоянную величину (как замечает Стив Джессоп, есть много переменных, которые может повлиять на то, истинно это или нет).

Тем не менее, даже если в одном конкретном случае нет абсолютно никакой разницы в производительности, вытаскивание таких тестов из цикла является хорошей привычкой. Еще лучше привыкнуть к использованию стандартных алгоритмов, как говорит @pmr, что полностью оборачивает проблему.

Ответ 2

Это меньше о end, что является дорогостоящим и больше о способности компилятора видеть, что end не будет изменяться через побочный эффект в теле цикла (что он является инвариантом цикла).

Сложность end должна быть постоянной по стандарту. См. Таблицу 96 в N3337 в 23.2.1.

Использование стандартных библиотечных алгоритмов прекрасно обходит всю дилемму.

Ответ 3

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

Ответ 4

Фактически, метод end() является встроенным. Второй не вызывает его каждый раз, я не думаю, что end() дает какое-либо отставание в производительности.

Ответ 5

std::vector.end() (например) возвращает итератор по значению. Во втором цикле вы создаете объект в каждом цикле. Стандарт кодирования говорит вам не создавать объект, если вам это не нужно. Компилятор может быть умным и оптимизировать код для вас, однако это не гарантия. Гораздо лучшее решение - использование алгоритмов stl. Они уже оптимизированы, и ваш код будет более читабельным. Остерегайтесь того, что две петли эквивалентны, только если вы не изменили коллекцию.

P.S. очень вероятно, что разница в производительности очень минимальна

Ответ 6

Для тех, кто читает это сейчас, вопрос стал несколько спорным вопросом с С++ 11.

Я не был уверен, отвечает ли этот ответ как ответ, потому что он фактически не затрагивает точку вопроса. Но я действительно считаю правильным отметить, что проблема, поднятая здесь, будет редко встречаться на практике для программиста на С++ 11, и я бы наверняка нашел этот ответ полезным несколько лет назад. Поэтому этот ответ нацелен на читателя, который просто хочет узнать лучший способ итерации через все элементы в контейнере STL (vector, list, deque и т.д.).

Предполагая, что OP хочет получить доступ к каждому элементу в контейнере, мы можем легко обойти весь вопрос о том, достаточно ли определить end, чем вызов Container::end(), написав диапазон для цикла:

Container container; // my STL container that has been filled with stuff

// (note that you can replace Container::value_type with the value in the container)

// the standard way
for (Container::value_type element : container) {
    // access each element by 'element' rather than by '*it'
}

// or, if Container::value_type is large
Container container; // fill it with something
for (Container::value_type& element : container) {
    //
}

// if you're lazy
Container container; // fill it with something
for (auto element : container) {
    //
}

ОП задал вопрос о том, стоит ли компромисс между кратностью простого сравнения it с Container::end() на каждой итерации и производительности объявления переменной end и сравнения того, что на каждом шаге стоит того. Поскольку циклы, основанные на диапазонах, обеспечивают простую, легкую для записи и легко читаемую альтернативу, которая также происходит внутри, объявляет итератор end вместо вызова метода Container::end() на каждом шаге, количество случаев, в которых нам нужно чтобы остановиться на этом вопросе, было сокращено до ограниченного числа случаев.

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

{
  auto && __range = range_expression ; 
  for (auto __begin = begin_expr,
        __end = end_expr; 
      __begin != __end; ++__begin) { 
    range_declaration = *__begin; 
    loop_statement 
  } 
}

Ответ 7

Зависит от реализации, но я не думаю, что end() дает большую часть отставания в производительности.