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

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

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

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>
{
...
public:
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  // 我们可以这样定义const_iterator:
  // typedef const iterator const_iterator;
……
}；

再看一下别的容器类的实现：（list iterator）

// _List_iterator仅仅在接口上做了一层薄薄的封装，具体实现都在_List_iterator_base中了。
// 对实现感兴趣的同学可以在stl_list.h中查看完整实现。
template<class _Tp, class _Ref, class _Ptr>
// 非public继承更好些。
struct _List_iterator : public _List_iterator_base {
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;

  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef _List_node<_Tp> _Node;

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

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

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

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

   // 与operator*情况相同。

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

  _Self& operator  () {
    this->_M_incr();
    return *this;
  }
  _Self operator  (int) {
    _Self __tmp = *this;
    this->_M_incr();
    return __tmp;
  }
  _Self& operator--() {
    this->_M_decr();
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    this->_M_decr();
    return __tmp;
  }
};

_List_iterator在list中的使用方式：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
...
public:
  // 通过指定了不同的reference type和pointer type来定了iterator和const_iterator类型
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
...
};

看起来我们只要稍稍修改一下_List_iterator就好了：

template<class _Tp> // 不需要额外指定reference type和pointer type
struct _List_iterator  : public _List_iterator_base {
...
  // 去掉const属性，不然无法重载
  reference operator*() { return ((_Node*) _M_node)->_M_data; }
  // 重载operator*，对于dereference const iterator类型，调用此函数
  const reference operator*() const { return ((_Node*) _M_node)->_M_data; }

   // 与operator*情况相同。

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

别忘了，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这样的类型，实现了后者这种指针语义的抽象，并提高了设计本身的弹性。