DEBUG下，VS 2010的vector和相关迭代器的安全检查和记录功能

本文分析DEBUG配置下，VS 2010中std::vector和相关迭代器提供的安全检查和记录功能。有的功能非常耗时。幸好在RELEASE配置下，这些功能都被预编译指令去掉了。当然这也说明，针对VC程序的效率测试必须采用RELEASE版本，否则测试结果很难说明问题。

std::vector和std::vector迭代器的类图

其中，_Vector_iterator<_Myvec>是std::vector<_Ty，_Alloc>::begin()返回的类型，

_Vector_const_iterator<_Myvec>是相应的const iterator

迭代器的有效性检查

在DEBUG配置下，_Vector_const_iterator负责检查迭代器的有效性：

在迭代器递增、递减、解引用等操作的时候，检查迭代器是否在vector的合法范围内。 两个迭代器比较大小的时候，验证它们迭代器是同一个vector的迭代器。

比如以下取值函数，就是检查指针是否越界。

reference operator*() const

{ // return designated object

#if _ITERATOR_DEBUG_LEVEL == 2

// 这里检查指针没有越界

if (this->_Getcont() == 0

|| this->_Ptr == 0

|| this->_Ptr < ((_Myvec *)this->_Getcont())->_Myfirst

|| ((_Myvec *)this->_Getcont())->_Mylast <=this->_Ptr)

{ // report error

_DEBUG_ERROR("vector iterator not dereferencable");

_SCL_SECURE_OUT_OF_RANGE;

}

迭代器的单向链表

std::vector<_Ty,_Alloc>通过基类_Vector_val<_Ty,_Alloc>包含了一个_Container_proxy对象，_Container_proxy::_Myfirstiter指向了一个单向链表P的头指针，P中包含一个vector对象的所有迭代器的指针。因此

新建一个迭代器，需要向P的头部插入一个指针，这是在常数时间完成的。销毁一个迭代器，需要从P中删除迭代器对应的指针。由于只保存了单向链表P的头指针，这具有线性的时间复杂度（见下面的代码）。如果一个容器的迭代器对象非常多，（比如hash_map的内部实现），则会非常耗时。

// 把迭代器指针从单向列表中删除

void _Iterator_base12::_Orphan_me()

{ // cut ties with parent

#if _ITERATOR_DEBUG_LEVEL == 2

if (_Myproxy != 0)

{ // 从链表的头指针向后遍历，找到当前元素的前一个元素

_Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;

while (*_Pnext != 0 && *_Pnext !=this)

_Pnext = &(*_Pnext)->_Mynextiter;

if (*_Pnext == 0)

_DEBUG_ERROR("ITERATOR LIST CORRUPTED!");

*_Pnext = _Mynextiter;

_Myproxy = 0;

}

#endif /* _ITERATOR_DEBUG_LEVEL == 2 */

}