SGI STL笔记（可以用const iterator代替const_iterator吗？）

6096阅读　0评论2012-02-18　Heartwork
分类：C/C++

在C++标准中，对于容器类，需要定义两个内建类型：iterator和const_iterator（详见Working Draft, Standard for Programming Language C （N3242) 23.2.1 General Container Requirement）。

在我们看到vector的源码时，const_iterator这种类型看起来是多余的，因为完全可以通过const iterator（注意，没有下斜线）来实现相应的行为：

  1. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  2. class vector : protected _Vector_base<_Tp, _Alloc>
  3. {
  4. ...
  5. public:
  6.   typedef _Tp value_type;
  7.   typedef value_type* pointer;
  8.   typedef const value_type* const_pointer;
  9.   typedef value_type* iterator;
  10.   typedef const value_type* const_iterator;
  11.   // 我们可以这样定义const_iterator:
  12.   // typedef const iterator const_iterator;
  13. ……
  14. }；
再看一下别的容器类的实现：（list iterator）
  1. // _List_iterator仅仅在接口上做了一层薄薄的封装，具体实现都在_List_iterator_base中了。
  2. // 对实现感兴趣的同学可以在stl_list.h中查看完整实现。
  3. template<class _Tp, class _Ref, class _Ptr>
  4. // 非public继承更好些。
  5. struct _List_iterator : public _List_iterator_base {
  6.   typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
  7.   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  8.   typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;

  10.   typedef _Tp value_type;
  11.   typedef _Ptr pointer;
  12.   typedef _Ref reference;
  13.   typedef _List_node<_Tp> _Node;

  15.   _List_iterator(_Node* __x) : _List_iterator_base(__x) {}
  16.   _List_iterator() {}
  17.   _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
  18.   // iterator类型与const_iterator类型区别的关键所在
  19.   // 虽然operator*是一个const成员函数，但这个const仅仅保护_M_node不能在operator*中被修改，而不是_M_node->_M_data。

   // 只有当reference是某一类型的const reference时，才能保证_M_node->_M_data的安全。

   // const_iterator属于这种情况，见下文list中代码。

  1.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }

   // 与operator*情况相同。

  1. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  2.   pointer operator->() const { return &(operator*()); }
  3. #endif /* __SGI_STL_NO_ARROW_OPERATOR */

  5.   _Self& operator () {
  6.     this->_M_incr();
  7.     return *this;
  8.   }
  9.   _Self operator (int) {
  10.     _Self __tmp = *this;
  11.     this->_M_incr();
  12.     return __tmp;
  13.   }
  14.   _Self& operator--() {
  15.     this->_M_decr();
  16.     return *this;
  17.   }
  18.   _Self operator--(int) {
  19.     _Self __tmp = *this;
  20.     this->_M_decr();
  21.     return __tmp;
  22.   }
  23. };
_List_iterator在list中的使用方式：
  1. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  2. class list : protected _List_base<_Tp, _Alloc> {
  3. ...
  4. public:
  5.   // 通过指定了不同的reference type和pointer type来定了iterator和const_iterator类型
  6.   typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
  7.   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  8. ...
  9. };
看起来我们只要稍稍修改一下_List_iterator就好了：
  1. template<class _Tp> // 不需要额外指定reference type和pointer type
  2. struct _List_iterator : public _List_iterator_base {
  3. ...
  4.   // 去掉const属性，不然无法重载
  5.   reference operator*() { return ((_Node*) _M_node)->_M_data; }
  6.   // 重载operator*，对于dereference const iterator类型，调用此函数
  7.   const reference operator*() const { return ((_Node*) _M_node)->_M_data; }

   // 与operator*情况相同。

  1. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  2.   pointer operator->() { return &(operator*()); }
  3.   const pointer operator->() const { return &(operator*()); }
  4. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  5. ...
  6. };
别忘了，const_iterator可是能够修改使用自增和自减来改变_M_node的！为了达成这个目的，需要修改_List_iterator_base的代码：将_M_node改为mutable，并将自增和自减操作加上const属性。（代码欠奉）

问题来了。

在某些应用场景中，我们需要传入const iterator的reference，但是因为iterator的自增和自减操作是const属性，所以我们不能保证const iterator最后仍然指向初始目标。：（

结论：
const iterator无法在替代const_iterator后保证iterator指针语义的完整性。

const iterator类似于原生指针T * const p这样的类型，即iterator本身的值是不可以修改的，但是你可以修改它所指向的目标。
const_iterator类似于原生指针T const * p这样的类型，即iterator本身的值是可变的，但是它所指向的目标是只读的。

STL通过提供了const_iterator这样的类型，实现了后者这种指针语义的抽象，并提高了设计本身的弹性。
上一篇：SGI STL笔记（难缠的heap算法）
下一篇：SGI STL笔记（list中的sort算法）