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

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

19 голосов
/ 19 марта 2012

On 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 иликомпиляторы уже оптимизируют такие случаи.

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

Ответы [ 7 ]

18 голосов
/ 19 марта 2012

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

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

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

7 голосов
/ 19 марта 2012

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

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

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

3 голосов
/ 19 марта 2012

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

2 голосов
/ 19 марта 2012

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

0 голосов
/ 26 марта 2014

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

Я не был уверен, квалифицируется ли этот ответ как ответ, потому что он на самом деле не касается сути вопроса. Но я действительно считаю правильным указать, что проблема, поднятая здесь, будет редко встречаться на практике для программиста на C ++ 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 и сравнения этого значения на каждом шаге. Поскольку циклы for на основе диапазона предоставляют простую, легкую в написании и легкую для чтения альтернативу, которая также внутренне объявляет итератор end, а не вызывает метод Container::end() на каждом шаге, количество случаев, когда нам нужно Чтобы остановиться на этом вопросе было сведено к ограниченному числу случаев.

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

{
  auto && __range = range_expression ; 
  for (auto __begin = begin_expr,
        __end = end_expr; 
      __begin != __end; ++__begin) { 
    range_declaration = *__begin; 
    loop_statement 
  } 
}
0 голосов
/ 19 марта 2012

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

PS Очень вероятно, что разница в производительности очень минимальная

0 голосов
/ 19 марта 2012

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

...