Кэширование конечного итератора - Хорошая идея или Плохая Идея?
Вообще говоря, действительно ли это - хорошая идея кэшировать конечный итератор (конкретно контейнеры 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 или просто некоторых?
7 ответов
В простом случае вектора итератор end изменится при добавлении или удалении элементов из контейнера; однако обычно безопаснее предположить, что если вы изменяете контейнер во время итерации по нему, все итераторы для него станут недействительными. Итераторы могут быть реализованы по-разному в любой данной реализации STL.
Что касается кеширования итератора end - его, безусловно, можно кэшировать, но чтобы узнать, действительно ли он быстрее в вашем случае, лучше всего профилировать свой код и посмотреть . Хотя получение итератора end из вектора , вероятно, является быстрой реализацией с недавней библиотекой и компилятором STL, я работал над прошлыми проектами, в которых кэширование ] end итератор дал нам значительный прирост скорости. (Это было на PlayStation 2, так что отнеситесь к этому с недоверием.)
Если мы говорим об эффективности и скорости: кэширование конечного итератора не требуется из-за оптимизации компилятора и встраивания.
В общем, хорошая идея для кеширования конечного итератора (в частности, Контейнеры STL) для повышения эффективности и скорости?
Если вы используете алгоритмы контейнера STL, кеширование конечного итератора происходит в любом случае (когда вы передаете результат container.end () в качестве параметра).
Если вы изменяете память контейнера (вставляете / удаляете элементы), это плохая идея.
Кроме того, кеширование для повышения эффективности редко имеет смысл: в большинстве случаев end () встроен компилятором, а когда это не так, очень вероятно, что ваша эффективность не зависит от результата end (), поскольку кешировано. YMMV хотя.
Как правило, не имеет значения, кэшируете ли вы конечный итератор. Если вы считаете, что это имеет значение, тогда вы уже должны использовать профилировщик в своем коде и сможете профилировать оба варианта. Я подозреваю, что это может отличаться в зависимости от типа контейнера, но профилировщик будет единственным способом узнать наверняка, учитывая ваш компилятор, оптимизацию и поставщика STL.
Я часто использую этот стиль для итерации контейнеров:
// typedef std::vector<Person> Persons;
Persons::iterator it = persons.begin(), end = persons.end();
for (; it != end; ++it)
{
Person & person = *it;
// ...
}
Удаление элемента из вектора делает недействительными все итераторы после стертой позиции.
Я не уверен насчет других типов контейнеров. В любом случае, я думаю, было бы безопасно предположить, что все итераторы станут недействительными после стирания. Если вам действительно нужна очень конкретная информация, вы всегда можете ее найти. Мне это редко нужно из-за моего довольно консервативного стиля программирования.
Правила признания недействительными (для итераторов) определены очень явно для каждого типа контейнера. Я считаю сайт SGI очень полезным http://www.sgi.com/tech/stl/table_of_contents.html
Специально для векторов, которые я нахожу:
[5] Итераторы вектора становятся недействительными, когда его память перераспределяется. Кроме того, вставка или удаление элемента в середине вектора делает недействительными все итераторы, которые указывают на элементы, следующие за точкой вставки или удаления. Отсюда следует, что вы можете предотвратить аннулирование итераторов вектора, если вы используете функцию Reserve () для предварительного выделения такого объема памяти, который будет когда-либо использоваться вектором, и если все вставки и удаления находятся в конце вектора.
Стирание из контейнера, над которым вы в данный момент выполняете итерацию, всегда является плохой идеей. Фактическое кэширование вашего конечного итератора не изменит этого.
h.