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 */
}