Существует ряд операций с итераторами, которые приводят к неопределенному поведению, цель этого триггера - активировать проверки во время выполнения, чтобы предотвратить его возникновение (используя утверждения).
Выпуск
Очевидная операция - использовать недействительный итератор, но эта недействительность может возникать по разным причинам:
- Унифицированный итератор
- Итератор для стертого элемента
- Итератор элемента, физическое местоположение которого изменилось (перераспределение для
vector)
- Итератор вне
[begin, end)
Стандарт, уточняющий детали для каждого контейнера, какая операция делает недействительным какой итератор.
Существует несколько менее очевидная причина, по которой люди склонны забывать: смешивать итераторы с различными контейнерами:
std::vector<Animal> cats, dogs;
for_each(cats.begin(), dogs.end(), /**/); // obvious bug
Это относится к более общей проблеме: допустимость диапазонов, переданных в алгоритмы.
[cats.begin(), dogs.end()) недопустимо (если один не является псевдонимом для другого) [cats.end(), cats.begin()) недопустимо (если cats пусто ??)
Решение
Решение состоит в добавлении информации к итераторам, чтобы их достоверность и достоверность определенных им диапазонов можно было утверждать во время выполнения, предотвращая возникновение неопределенного поведения.
Символ _HAS_ITERATOR_DEBUGGING служит триггером этой возможности, потому что, к сожалению, он замедляет работу программы. Это довольно просто в теории: каждый итератор состоит из Observer контейнера, из которого он выпущен, и таким образом уведомляется о модификации.
В Dinkumware это достигается двумя дополнениями:
- Каждый итератор несет указатель на связанный с ним контейнер
- Каждый контейнер содержит связанный список созданных им итераторов
И это аккуратно решает наши проблемы:
- У итерализованного итератора нет родительского контейнера, большинство операций (кроме присваивания и уничтожения) вызывают утверждение
- Итератор удаленного или перемещенного элемента был уведомлен (благодаря списку) и знает о его недействительности
- При увеличении и уменьшении итератора он может проверить, что он остается в пределах
- Проверить, что 2 итератора принадлежат одному и тому же контейнеру, так же просто, как сравнить их родительские указатели
- Проверка допустимости диапазона так же проста, как проверка того, что мы достигли конца диапазона, прежде чем достигнем конца контейнера (линейная операция для тех контейнеров, которые не доступны случайным образом, таким образом, большинство из них)
Стоимость
Стоимость велика, но есть ли у правильности цена? Мы можем разбить стоимость, хотя:
- дополнительное выделение памяти (поддерживается дополнительный список итераторов):
O(NbIterators)
- процесс уведомления о мутирующих операциях:
O(NbIterators) (обратите внимание, что push_back или insert не обязательно делает недействительными итераторы, но erase делает)
- проверка допустимости диапазона:
O( min(last-first, container.end()-first) )
Большинство библиотечных алгоритмов, конечно, были реализованы для максимальной эффективности, обычно проверка выполняется раз и навсегда в начале алгоритма, затем запускается непроверенная версия. Тем не менее, скорость может сильно замедлиться, особенно при написании рукописных циклов:
for (iterator_t it = vec.begin();
it != vec.end(); // Oups
++it)
// body
Мы знаем, что строка Oups - плохой вкус, но здесь это еще хуже: при каждом запуске цикла мы создаем новый итератор, а затем уничтожаем его, что означает выделение и освобождение узла для vec список итераторов ... Нужно ли подчеркивать стоимость выделения / освобождения памяти в узком цикле?
Конечно, for_each не столкнется с такой проблемой, что является еще одним убедительным аргументом в пользу использования алгоритмов STL вместо версий с ручным кодированием.