c++ - 启用S​​TL迭代器调试的真正作用是什么？

Question

我已经通过定义在应用程序中启用了迭代器调试

_HAS_ITERATOR_DEBUGGING = 1

我原以为这实际上只是检查 vector 范围，但我感觉它的作用远不止于此。实际上正在执行哪些检查等？

顺便说一下，Dinkumware STL。

Answer 1

迭代器有许多操作会导致未定义的行为，此触发器的目标是激活运行时检查以防止它发生(使用断言)。

问题

显而易见的操作是使用无效的迭代器，但是这种无效可能是由于多种原因引起的:

未初始化的迭代器

迭代器到已删除的元素

迭代器，该元素的物理位置已更改(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中，这是通过两个附加功能来实现的:

每个迭代器都带有一个指向其相关容器

的指针

每个容器都包含它创建的迭代器的链表

这巧妙地解决了我们的问题:

未初始化的迭代器没有父容器，大多数操作(除赋值和销毁操作外)都会触发一个断言

已通知(通过列表)已删除或移动的元素的迭代器，并知道其无效性

在递增和递减迭代器时，它可以检查迭代器是否位于

范围内

检查两个迭代器是否属于同一个容器，就像比较其父指针

一样简单

检查范围的有效性就像检查我们在到达容器的末端之前到达范围的末端一样简单(对于那些不能随机访问的容器，因此大多数都是线性操作的)

费用

成本沉重，但是正确性有代价吗？我们可以分解成本:

额外的内存分配(维护的额外迭代器列表):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算法而不是手工编码版本的又一个引人注目的案例。