Кэширование конечного итератора - хорошая идея или плохая идея?

Question

Вообще говоря, это хорошая идея, чтобы кэшировать конечный итератор (в частности, контейнеры STL) в целях эффективности и скорости? например, в следующем бите кода:

std::vector<int> vint;
const std::vector<int>::const_iterator end = vint.end();
std::vector<int>::iterator it = vint.begin();

while (it != end)
{
   ....
   ++it;
}

При каких условиях конечное значение будет недействительным? удаление из контейнера приведет к тому, что конец будет признан недействительным в во всех STL контейнерах или только в некоторых?

Answer 1

В простом случае vector итератор end будет меняться при добавлении или удалении элементов из контейнера; тем не менее, обычно безопаснее предположить, что если вы изменяете контейнер во время его итерации, все итераторы становятся недействительными. Итераторы могут быть реализованы по-разному в любой данной реализации STL.

Что касается кэширования итератора end - это, безусловно, допустимо для кэширования, но чтобы выяснить, действительно ли он быстрее в вашем случае, лучше всего вам профилировать свой код и посмотреть. Хотя извлечение итератора end из vector, вероятно, является быстрой реализацией с недавней библиотекой и компилятором STL, у меня есть , работавший в прошлых проектах, где кэширование итератора end дало нам значительное повышение скорости , (Это было на PlayStation 2, так что возьмите зерно соли.)

Answer 2

Если мы говорим об эффективности и скорости: кэширование конечного итератора не требуется из-за оптимизации компилятора и встраивания.

Answer 3

Правила аннулирования (для итераторов) определены очень явно для каждого типа контейнера. Я считаю сайт SGI очень полезным http://www.sgi.com/tech/stl/table_of_contents.html

Специально для векторов я нахожу:

[5] Итераторы вектора становятся недействительными, когда его память перераспределяется. Кроме того, вставка или удаление элемента в середине вектора делает недействительными все итераторы, которые указывают на элементы после точки вставки или удаления. Из этого следует, что вы можете предотвратить аннулирование итераторов вектора, если вы используете Reserve () для предварительного выделения столько памяти, сколько будет использовать вектор, и если все вставки и удаления находятся в конце вектора.

Answer 4

Вообще говоря, является ли хорошей идеей кэшировать конечный итератор (в частности, контейнеры STL) для целей эффективности и скорости?

Если вы используете алгоритмы контейнеров STL, кэширование концаИтератор в любом случае происходит (когда вы передаете результат container.end () в качестве параметра).

Если вы изменяете память контейнера (вставляете / удаляете элементы), это плохая плохая идея.

Кроме того, кэширование для эффективности редко имеет большой смысл: в большинстве случаев end () указывается компилятором, а когда это не так, очень вероятно, что ваша эффективность не зависит от end (), в результатекэшируются.YMMV хотя.

Answer 5

Стирание из контейнера, над которым вы сейчас выполняете итерацию, всегда плохая идея. Фактическое кэширование вашего конечного итератора не изменит этого.

ч.

Answer 6

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

Answer 7

Я часто использую этот стиль для итерации контейнеров:

// typedef std::vector<Person> Persons;
Persons::iterator it = persons.begin(), end = persons.end();
for (; it != end; ++it)
{
    Person & person = *it;
    // ...
}

Стирание элемента из вектора делает недействительными все итераторы после стертой позиции.

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

Answer 8

Это действительно очень зависит от того, что вы делаете в коде ....

Если компилятор может доказать, что vint.end() не изменится, то это может не иметь значения, но вы во власти оптимизаций компилятора, и насколько ясен код ....

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

Это 2019 год, и циклы for-range в основном эквивалентны вашему коду: https://en.cppreference.com/w/cpp/language/range-for

{
    auto && __range = range_expression ;
    auto __begin = begin_expr ;
    auto __end = end_expr ;
    for ( ; __begin != __end; ++__begin) {

        range_declaration = *__begin;
        loop_statement

    }
}

, что, кстати, означает, что если вы на самом деле не интересовались it, но *it, вы можете положить конец (без каламбура) дилемме и просто написать:

std::vector<int> vint;
for(auto&& e : vint)
{
   .... // use `e` instead of `*it`.
}