启用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中,这是通过两个附加项实现的:

• 每个迭代器携带一个指向其相关容器的指针
• 每个容器都包含它创建的迭代器的链接列表

这很好地解决了我们的问题:

• 单元化迭代器没有父容器,大多数操作(除了赋值和销毁)都将触发断言
• 已删除或移动元素的迭代器已得到通知(感谢列表),并知道其无效性。
• 在递增和递减迭代器时,它可以检查迭代器是否在界限内。
• 检查两个迭代器是否属于同一个容器与比较它们的父指针一样简单
• 检查一个范围的有效性就像在到达容器的末端之前检查我们是否到达了范围的末端一样简单(对于那些不随机访问的容器,线性操作,因此大多数容器都是如此)

成本

成本很高,但是正确性有代价吗?但我们可以分解成本:

• 额外内存分配(保留迭代器的额外列表): O(NbIterators)
• 变异操作通知流程: o(n迭代器) (注意 push_back 或 insert 不一定使迭代器无效,但是 erase 做)
• 范围有效性检查: O( min(last-first, container.end()-first) )

当然,大多数库算法都是为了最大限度地提高效率而实现的,通常在算法开始时一次性完成检查,然后运行未检查的版本。然而,速度可能会严重减慢,尤其是手写循环:

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

我们知道 乌普斯 行的味道不好,但这里更糟:在循环的每次运行中,我们都创建一个新的迭代器,然后销毁它,这意味着为 vec 的迭代器列表…我是否必须强调在一个紧凑的循环中分配/释放内存的成本?

当然,A for_each 不会遇到这样的问题,这是使用STL算法而不是手工编码版本的另一个引人注目的例子。

据我所知:

_ has-iterator调试将在运行时显示一个对话框,以断言任何不正确的迭代器使用,包括:

1)元素被擦除后在容器中使用的迭代器

2)调用.push()或.insert()函数后向量中使用的迭代器

根据 http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

C++标准描述了哪个成员函数导致迭代器对容器无效。两个例子是:

• 从容器中删除元素会导致元素的迭代器无效。
• 增大向量的大小(push或insert)会导致迭代器在向量容器中无效。