Что на самом деле делает включение отладки итератора STL?

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

Проблема

Очевидной операцией является использование недопустимого итератора, но эта невалидность может возникать по разным причинам:

• Неинициализированный итератор
• Итератор к элементу, который был стерт
• Итератор к элементу, физическое расположение которого изменилось (перераспределение для 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();              // Oops
     ++it)
// body

Мы знаем, что строка Oops — дурной вкус, но здесь все еще хуже: при каждом запуске цикла мы создаем новый итератор, а затем уничтожаем его, что означает выделение и освобождение узла для списка итераторов vec. .. Должен ли я подчеркивать стоимость выделения/освобождения памяти в тесном цикле?

Конечно, for_each не столкнулся бы с такой проблемой, что является еще одним убедительным доводом в пользу использования алгоритмов STL вместо версий, написанных вручную.

Насколько я понимаю:

_HAS_ITERATOR_DEBUGGING будет отображать диалоговое окно во время выполнения, чтобы подтвердить любое неправильное использование итератора, включая:

1) Итераторы, используемые в контейнере после стирания элемента

2) Итераторы, используемые в векторах после вызова функции .push() или .insert()

Согласно http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

Стандарт C++ описывает, какие функции-члены делают итераторы контейнера недействительными. Два примера:

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