Что действительно делает включение итератора STL, отлаживающего?

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

Проблема

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

• Неинициализированный итератор
• Итератор для элемента, который был стерт
• Итератор для элемента какое физическое местоположение было изменено (перераспределение для вектора )
• Итератор за пределами [начало, конец)

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

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

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 служит триггером для этой возможности, потому что, к сожалению, он замедляет работу программы. Теоретически это довольно просто: каждый итератор становится наблюдателем контейнера, из которого он выпущен, и, таким образом, получает уведомление об изменении.

В Dinkumware это достигается двумя дополнениями:

• Каждый итератор несет указатель на связанный с ним контейнер
• Каждый контейнер содержит связанный список итераторов, которые он создал

И это аккуратно решает наши проблемы:

• ] Неинициализированный итератор не имеет родительского контейнера, большинство операций (кроме присваивания и уничтожения) вызывают утверждение
• Итератор для удаленного или перемещенного элемента был уведомлен (благодаря списку) и знает о его недействительности
• При увеличении и уменьшении итератора он может проверять, что он остается в пределах границ
• Проверить принадлежность 2 итераторов к одному и тому же контейнеру так же просто, как сравнить их родительские указатели
• Проверить действительность диапазона так же просто, как проверить что мы достигаем конца диапазона, прежде чем мы дойдем до конца контейнера (линейная операция для тех контейнеров, которые не доступны случайным образом, поэтому большинство из них)

Стоимость

Стоимость высока, но есть ли правильность цена? Мы можем разбить стоимость:

• дополнительное выделение памяти (поддерживается дополнительный список итераторов): O (NbIterators)
• процесс уведомления об операциях изменения: O (NbIterators) (Примечание что push_back или insert не обязательно аннулируют все итераторы, но erase делает)
• проверка допустимости диапазона: O (min (last-first , контейнер.end () - first))

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

for (iterator_t it = vec.begin();
     it != vec.end();              // Oops
     ++it)
// body

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

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