尽量用iterator代替const_iterator

http://blog.csdn.net/mymtm/archive/2010/07/02/5708677.aspx

http://hi.baidu.com/flouse/blog/item/9444c41681d92d1a962b4346.html

写一个iterator 并不难，并且它是扩展C++ 标准运行库的一个自然方式。但如果想做正确，还是应该知道一些关键点的。

正如大多C++ 编程人员所知的，每个标准容器类都提供四种迭代器类型。对于container 而言，iterator 的作用相当于T* ，而const_iterator 则相当于const T* （你可能也见过T const* 这样的写法：它们意思一样[ ）。增加一个iterator 或者const_iterator 可以在一个从容器开头趋向尾部的遍历中让你移动到容器的下一个元素。reverse_iterator 与const_reverse_iterator 同样相当于对应的T* 和const T* ，所不同的是，增加reverse_iterator 或者const_reverse_iterator 会在从尾到头的遍历中让你移动到容器的下一个元素。

首先让我演示两个东西。第一，看看vector 的insert 和erase 的样式：

iterator insert(iterator position, const T& x);

iterator erase(iterator position);

iterator erase(iterator rangeBegin, iterator rangeEnd);

每个标准容器都包含了和这差不多的函数，虽然返回类型因容器类型的不同而不同。需要注意的是：这些方法只接受iterator 类型的参数，而不是const_iterator 、reverse_iterator 或const_reverse_iterator 。总是iterator 。虽然容器类支持四种迭代器类型，但其中的一种类型有着其他所没有的特权。那就是iterator ，iterator 比较特殊。

我要让你看的第二个东西是这张图，它显示了几种迭代器之间存在的转换关系：

图中显示了从iterator 到const_iterator 、从iterator 到reverse_iterator 和从reverse_iterator 到const_reverse_iterator 可以进行隐式转换。并且，reverse_iterator 可以通过调用其base 成员函数转换为iterator 。const_reverse_iterator 也可以类似地通过base 转换成为const_iterator 。一个图中无法显示的事实是：通过base 得到的也许并非你所期待的iterator 。

让我们再进一步了解iterator 、const_iterator 、const iterator 三者之间的区别，通过下面的代码段来说明：

vector ivec;

vector::iterator citer0 = ivec.begin();

vector::const_iterator citer1 = ivec.begin();

const vector::iterator citer2 = ivec.begin();

vector ivec;

vector::iterator citer0 = ivec.begin();

vector::const_iterator citer1 = ivec.begin();

const vector::iterator citer2 = ivec.begin();

*citer0 = 1;   //right

*citer1 = 1;   //error 不能用const_iterator 改变其中元素

*citer2 = 1;   //right

++citer0;      //right

++citer1;      //right 改变迭代器，而不是其中的元素

++citer2;      //error

// 总而言之：常量迭代器不是常量迭代型。这意味着你能够改变常量迭代器的长度（例如：用++ 来增加长度）。然而，你不能改变常量迭代器所指向的对象的值。

你应该发现了没有办法从一个const_iterator 转换得到一个iterator ，也无法从const_reverse_iterator 得到reverse_iterator 。这一点非常重要，因为这意味着如果你有一个const_iterator 或者const_reverse_iterator ，你会发现很难让它们和容器的一些成员函数合作。那些成员函数要求iterator ，而你无法从const 迭代器类型反过来得到iterator 。当你需要指出插入位置或删除的元素时，const 迭代器几乎没有用 。

但是，千万不要傻乎乎的宣称const 迭代器一无是处。不，它们可以与算法默契配合，因为算法通常并不关心迭代器是什么类型，只要是适当的种类就可以了，很多容器的成员方法也接受const 迭代器。只有insert 和erase 的一些形式有些吹毛求疵。

我的意思是如果你要指出插入的位置或删除的元素时，const 迭代器“ 几乎” 没有用。这暗示了并不是完全没用。那是真的。如果你找到了一个方法可以从const_iterator 或const_reverse_iterator 得到一个iterator ，那么它们就有用。而且这是很有可能的。但这种方法并不总是行得通，而且就算可行，完成的方法也很不直观，也很缺乏效率。这个转换的方法我们将在下文中讨论，现在我们先总结一下尽量使用iterator 取代const 类型的迭代器的理由：

• insert 和erase 的一些版本要求iterator 。如果你需要调用这些函数，你就必须产生iterator ，而不能用const 或reverse iterators 。
• 不可能把const_iterator 隐式转换成iterator ，我们将会在 中讨论从一个const_iterator 产生一个iterator 的技术并不普遍适用，而且不保证高效。

现在我们有足够的理由来相信 “尽量使用iterator 取代const 类型的迭代器”这句话是有道理的，但是，很多情况下我们不得不使用const_iterator

//Polynomial 是一个多项式类，下面是它的一个相加操作符重载

Polynomial Polynomial::operator + (const Polynomial &polyn2) const {

      Polynomial result;

      list::const_iterator p1;

bool erased;

for (p1 = terms.begin(); p1 != terms.end(); p1++)   //??

          result.terms.push_back(*p1);

for (p1 = polyn2.terms.begin(); p1 != polyn2.terms.end(); p1++)

          result.terms.push_back(*p1);

      list::iterator p2, p3, p4;

for (p3 = result.terms.begin(); p3 != result.terms.end();){

for (p2 = p3, p2++, erased = false ; p2 != result.terms.end(); p2++){

if (*p3 == *p2){

                    p3->coeff += p2->coeff;

                    p2 = result.terms.erase(p2);

if (p3->coeff == 0){

                        p3 = result.terms.erase(p3);

                        erased = true ;

                    }

               }             

if (erased || p2 == result.terms.end()) break ;

          }

if (!erased) p3++;

      }

      result.terms.sort();

return result;

}

我们可以看到，由于进行了这样的声明 ( 安全式的声明 ) ：

Polynomial Polynomial::operator + (const Polynomial &polyn2) const

所以， p1 不得不用 const_iterator

list::const_iterator p1;

p1 = terms.begin();

p1 = polyn2.terms.begin();

上面我们已指出有些容器成员函数只接受 iterator 作为参数，而不是 const_iterator 。那么，如果在只有一个 const_iterator 的情况下，而又要在它所指向的容器位置上插入新元素呢？也就是如何把 const_iterator 转化为 iterator 呢？但是问题是并不存在从 const_iterator 到 iterator 之间的隐式转换，所以我们必须成为这次行动的主角。

As the old saying goes: “每当无路可走的时候，就举起大锤！”。在 C++ 的世界里，这句话里的大锤就是：映射。这种想法很可耻。真不知道是哪儿学来的。

让我们面对困扰在你面前的问题。看看当你把一个 const_iterator 映射为 iterator 时会发生什么：

typedef deque IntDeque;          // 方便的typedef

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator ConstIter;

ConstIter ci;           // ci 是const_iterator

...

Iter i(ci);                        // 错误！没有从const_iterator 到iterator 隐式转换的途径

Iter i(const_cast (ci));     // 仍是个错误！不能从const_iterator 映射为iterator ！

事实表明，把 const 迭代器映射为迭代器是病态的。

我们并不会就这样束手无策，有一种安全的、可移植的方法获取它所对应的 iterator[ ，而且，用不着陷入类型系统的转换。下面是解决思路的本质，虽然在它编译前还要稍作修改：

typedef deque IntDeque;          // 和以前一样

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator ConstIter;

IntDeque   d;

ConstIter ci;

...   // 让ci 指向d

Iter i(d.begin());           // 初始化i 为d.begin()

// 把i 移到指向ci 位置（但请留意下面关于为什么在它编译前要调整的原因）

advance(i, distance (i, ci));

这种方法看上去非常简单，直截了当，也很让人吃惊吧。要得到与 const_iterator 指向同一位置的 iterator ，首先将 iterator 指向容器的起始位置，然后把它向前移到和 const_iterator 距离容器起始位置的偏移量一样的位置即可！这个任务得到了两个函数模板 advance 和 distance 的帮助，它们都在 中声明。 distance 返回两个指向同一个容器的 iterator 之间的距离； advance 则用于将一个 iterator 移动指定的距离。如果 i 和 ci 指向同一个容器，那么表达式 advance(i, distance(i, ci)) 会将 i 移动到与 ci 相同的位置上。

如果这段代码能够通过编译，它就能完成这种转换任务。但似乎事情并不那么顺利。想知道为什么，先来看看 distance 的定义：

template

typename iterator_traits::difference_type

distance(InputIterator first, InputIterator last);

不要被这个函数的长达个字符的返回类型卡住，也不用理会 difference_type 是什么东西。取而代之的是，把注意力集中在参数的类型 InputIterator ：

当遇到 distance 调用时，你的编译器需要根据使用的实参类型推断出 InputIterator 的类型。再来看看我所说的不太正确的 distance 调用（如下）：

advance(i, distance(i, ci));               // 调整i ，指向ci 位置

上面的调用有两个参数传递给distance ，i 和ci 。i 的类型是Iter ，即deque::iterator 的typedef 。对编译器来说，这表明调用distance 的InputIterator 是deque::iterator 。但ci 是ConstIter ，即deque::const_iterator 的typedef 。这表明那个InputIterator 是deque::const_iterator 。InputIterator 不可能同时有两种不同的类型，所以调用distance 失败。一般会造成一些冗长的出错信息，可能会也可能不会说明是编译器无法得出InputIterator 是什么类型。

要顺利地调用 distance ，你需要排除歧义。最简单的办法就是显式的指明 distance 调用的模板参数类型，从而避免编译器自己得出它们的类型：

advance(i, distance(i, ci));

我们现在知道了怎么通过 advance 和 distance 获取 const_iterator 相应的 iterator 了。但另一个我们现在一直避开却很值的考虑的实际问题是：这个技巧的效率如何？答案很简单。取决于你所转换的究竟是什么样的迭代器。对于随机访问的迭代器（比如 vector 、 string 和 deque 的）而言，这是常数时间的操作。对于双向迭代器（也就是，所有其它容器和包括散列容器的一些实现）而言，这是线性时间的操作。

因为它可能花费线性时间的代价来产生一个和 const_iterator 等价的 iterator ，并且因为如果不能访问 const_iterator 所属的容器这个操作就无法完成。从这个角度出发，它反过来要我们重新审视从 const_iterator 产生 iterator 的设计。事实上那样的考虑再次激发了那个条款，它建议你当处理容器时“尽量用 iterator 代替 const 迭代器” 。

---

Effective STL 条款26：尽量用iterator代替const_iterator，reverse_iterator和const_reverse_iterator

正如你所知的，每个标准容器类都提供四种迭代器类型。对于container而言，iterator的作用相当于T*，而const_iterator则相当于const T*（你可能也见过T const*这样的写法：它们意思一样^[1] ）。增加一个iterator或者const_iterator可以在一个从容器开头趋向尾部的遍历中让你移动到容器的下一个元素。 reverse_iterator与const_reverse_iterator同样相当于对应的T*和const T*，所不同的是，增加reverse_iterator或者const_reverse_iterator会在从尾到头的遍历中让你移动到容器的下一个元素。

让我向你演示两个东西。第一，看看vector的insert和erase的样式：

iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);

每个标准容器都包含了和这差不多的函数，虽然返回类型因容器类型的不同而不同。需要注意的是：这些方法只接受iterator类型的参数，而不是 const_iterator、reverse_iterator或const_reverse_iterator。总是iterator。虽然容器类支持四种迭代器类型，但其中的一种类型有着其他所没有的特权。那就是iterator，iterator比较特殊^[2] 。

我要让你看的第二个东西是这张图，它显示了几种迭代器之间存在的转换关系：

图中显示了从iterator到const_iterator、从iterator到reverse_iterator和从 reverse_iterator到const_reverse_iterator可以进行隐式转换。并且，reverse_iterator可以通过调用其base成员函数转换为iterator。const_reverse_iterator也可以类似地通过base转换成为 const_iterator。一个图中无法显示的事实是：通过base得到的也许并非你所期待的iterator。我们将会在条款28 中详细讨论这一点。

你应该发现了没有办法从一个const_iterator转换得到一个iterator，也无法从const_reverse_iterator得到reverse_iterator。这一点非常重要，因为这意味着如果你有一个const_iterator或者 const_reverse_iterator，你会发现让南让它们和容器的一些成员函数合作。那些成员函数要求iterator，而你无法从const 迭代器类型反过来得到iterator。当你需要指出插入位置或删除的元素时，const迭代器几乎没有用。

千万不要傻乎乎的宣称const迭代器一无是处。不，它们可以与算法默契配合，因为算法通常并不关心迭代器是什么类型，只要是适当的种类（category）就可以了，很多容器的成员方法也接受const迭代器。只有insert和erase的一些形式有些吹毛求疵。

我写的是如果你要指出插入的位置或删除的元素时，const迭代器“几乎”没有用。这暗示了并不是完全没用。那是真的。如果你找到了一个方法可以从 const_iterator或const_reverse_iterator得到一个iterator，那么它们就有用。那经常是有可能的。但这种方法并不总是行得通，而且就算可行，完成的方法也很不直观，也很缺乏效率。这个主题将足够充实一个它自己的条款，所以如果你对这个细节感兴趣的话，请转到条款27 。现在，我们已经有足够的理由相信应该尽量使用iterator取代const或者reverse类型的迭代器：

• insert和erase的一些版本要求iterator。如果你需要调用这些函数，你就必须产生iterator，而不能用const或reverse iterators。
• 不可能把const_iterator隐式转换成iterator，我们将会在条款27 中讨论从一个const_iterator产生一个iterator的技术并不普遍适用，而且不保证高效。
• 从reverse_iterator转换而来的iterator在转换之后可能需要相应的调整，在条款28 中我们会讨论何时需要调整以及调整的原因。

所有这些东西联合起来就能看出，如果你尽量使用iterator代替const或reverse类型的迭代器，可以使得容器的使用更简单，更高效而且可以避免潜在的bug。

事实上，你可能会更多地面临在iterator与const_iterator之间的选择.iterator与reverse_iterator之间的选择显而易见——依赖于从前到后或从后到前的遍历。你可以选择你需要的一种，而且即使你选择了reverse_iterator，当你要调用需要 iterator的容器成员函数时，你仍然可以通过base得到相应的iterator（可能需要一些调整，参见条款28 ）。

当在iterator和const_iterator之间作选择的时候，你有更充分的理由选择iterator，即使const_iterator 同样可行而且即使你并不需要调用容器类的任何成员函数。其中的令人讨厌的原因包括iterator与const_iterator之间的比较。我希望我们都可以赞成这是合理的代码：

typedef deque   IntDeque;    // typedef可以极大地简化
typedef IntDeque::iterator Iter;    // STL容器类和iterator
typedef IntDeque::const_iterator ConstIter;   // 的操作。
Iter   i;
ConstIter ci;
...       // 同一个容器
if (i == ci)
...      //  比较iterator和const_iterator

我们所做的只是同一个容器中两个迭代器之间的比较，这是STL中最基本的动作。唯一的变化是等号的一边的类型是 iterator，而另一边的类型是const_iterator。这应该不是问题，因为iterator应该在比较之前隐式的转换成 const_iterator，真正的比较应该在两个const_iterator之间进行。

对于设计良好的STL实现而言，情况确实如此。但对于其它一些实现，这段代码甚至无法通过编译。原因在于，这些实现将const_iterator 的operator==作为 const_iterator的一个成员函数而不是非成员函数。而问题的解决之道显得非常有趣：只要像这样交换两个iterator的位置：

if (ci==i)...      / / 当上面比较无法通过编译时的解决方法

不仅是比较是否相等，只要你在同一个表达式中混用iterator和const_iterator（或者 reverse_iterator和const_reverse_iterator），这样的问题就可能会出现。比如，当你试图在两个随机存取迭代器之间进行减法操作时：

if (i-ci >= 3) ...     / / 如果i与ci之间至少有三个元素...

如果迭代器的类型不同，你的（正确的）代码可能会被（错误地）拒绝。你可以想见解决的方法（交换i和ci的位置），但这次，不只是用i-ci替换ci-i了：

if (ci+3 <= i) ...   // 当上面的代码无法通过编译时的解决方法

避免这类问题的最简单的方法是减少混用不同类型的迭代器的机会，换句话说，又回到了尽量用iterator代替 const_iterator。从const correctness的角度来看（一个固然有价值的角度），仅仅为了避免一些潜在的STL实现的弊端（而且，这些弊端都有较为直接的解决途径）而抛弃 const_iterator显得有欠公允。但综合考虑到iterator与一些容器类成员函数的粘连关系，从实践得出const_iterator没有 iterator好用的结论是很难避免的。更何况，有时并不值得卷入const_iterator的麻烦中去。

^[1] 关于这个主题的完整的文章，请参考1999年2月《Embedded Systems Programming》上刊登的《const T vs. T const》，作者是Dan Saks。

^[2] “iterator 比较特殊”的原因并不清楚。HP的最早的STL实现包含了带有iterator参数的insert和erase，而这个设计问题在标准化的过程中并没有重新考虑。但是在以后，这可能会改变，因为程序库工作组发布了#180记录，说明了“这个问题在下一个标准版本中会作为综合回顾的const问题而被考虑” （C++程序库问题可以从 看到）

---

Effective STL 条款27：用distance和advance把const_iterator转化成iterator

条款26 中指出有些容器成员函数只接受iterator作为参数，而不是const_iterator。那么，如果你只有一个const_iterator，而你要在它所指向的容器位置上插入新元素呢？也就是如何把const_iterator转化为iterator呢？因为正如条款26 所解释的，并不存在从const_iterator到iterator之间的隐式转换，所以你必须成为这次行动的主角。

我知道你在想什么。你正在想，“每当无路可走的时候，就举起大锤！”。在C++的世界里，你的意思只能是：映射(casting)。这种想法很可耻。真不知道你是哪儿学来的。

让我们面对困扰在你面前的问题。看看当你把一个const_iterator映射为iterator时会发生什么：

typedef deque IntDeque;    //  typedef, 简化代码。
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
ConstIter ci;      //  ci是const_iterator
...
Iter i(ci);      //  错误！没有从const_iterator 到iterator隐式转换的途径
Iter i(const_cast(ci));    // 错误！没有从const_iterator 到iterator隐式转换的途径

这里只是以deque为例，但是用其它容器类——list、set、multiset、map、multimap甚至条款25 描述的hash表容器^[1] ——的结果一样。使用映射的行也许 在vector或string的代码时能够编译，但这是我们马上要讨论的非常特殊的情形。

包含映射的代码不能通过编译的原因在于，对于这些容器而言，iterator和const_iterator是完全不同的类。它们之间并不比 string和complex具有更多的血缘关系。在两个毫无关联的类之间进行const_cast映射是荒谬的，所以 reinterpret_cast、static_cast甚至C风格的映射也会导致同样的结果。

唉，不能编译的代码对于vector和string容器来说也许能够通过编译。那是因为通常情况下大多数实现都会采用真实的指针作为那些容器的迭代器。就这种实现而言，vector::iterator是T*的typedef，而vector:: const_iterator是const T*的typedef，string::iterator是char*的typedef，而string::const_iterator是const char*的typedef。在这种实现的情况下，用const_cast把const_iterator映射成iterator当然可以编译而且没有问题，因为const_iterator与iterator之间的const_cast映射被最终解释成const T*到T*的映射。但是，即使是在这种实现中，reverse_iterator和const_reverse_iterator也是真正的类，所以你仍然不能直接用const_cast把const_reverse_iterator映射成reverse_iterator。而且，正如条款50 解释的，这些实现通常只会在Release模式时才使用指针表示vector和string的迭代器^[2] 。所有这些事实表明，把const迭代器映射为迭代器是病态的，即使是对vector和string来说也时，因为移植性很值得怀疑。

如果你得到一个const_iterator并且可以访问它所指向的容器，那么有一种安全的、可移植的方法获取它所对应的iterator，而且，用不着陷入类型系统的转换。下面是解决思路的本质，虽然在它编译前还要稍作修改：

typedef deque IntDeque;    // 和以前一样
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque    d;
ConstIter ci;
...       // 让ci 指向d
Iter i(d.begin());      //  初始化i为d.begin()
advance(i, distance(i, ci));   // 调整i，指向ci位置（但请留意下面关于为什么在它编译前要修改的原因）

这种方法看上去非常简单，直截了当，也很让人吃惊吧。要得到与const_iterator指向同一位置的iterator，首先将 iterator指向容器的起始位置，并且让它移到和const_iterator距离容器起始位置的偏移量一样的位置即可！这个任务得到了两个实用算法 advance和distance的帮助，它们都在中声明。distance返回两个指向同一个容器的iterator 之间的距离；advance则用于将一个iterator移动指定的距离。如果i和ci指向同一个容器，那么表达式advance(i, distance(i, ci))会将i移动到与ci相同的位置上。

如果这段代码能够通过编译，它就能完成这种转换任务。但似乎事情并不那么顺利。想知道为什么，先来看看distance的定义：

template
typename iterator_traits::difference_type
distance(InputIterator first, InputIterator last);

不要被这个函数的长达56个字符的返回类型卡住，也不用理会difference_type是什么东西。取而代之的是，把注意力集中在参数的类型InputIterator：

template
typename iterator_traits::difference_type

---

<>
当我们对普通iterator类型解引用时，得到对某个元素的非const引用，而如果我们对const_iterator类型解引用时，则可以得到一个指向const对象的引用，如同任何常量一样，该对象不能进行重写。
例如，如果text是vector类型，程序员想要遍历它，输出每个元素,但不更改里面的元素，可以这样编写程序：

//  use const_iterator because we won't change the elements
for (vector::const_iterator iter = text.begin(); iter != text.end(); ++iter)
    cout << *iter << endl;         // print each element in text

除了是从迭代器读取元素值而不是对它进行赋值之外，这个循环与前一个相似。由于这里只需要借助迭代器进行读，不需要写，这里把iter定义为 const_iterator类型。当对const_iterator类型解引用时，返回的是一个const值。不允许用const_iterator进行赋值：

for (vector::const_iterator iter = text.begin();iter != text.end(); ++ iter)

    *iter = " ";    // error: *iter is const

使用const_iterator类型时，我们可以得到一个迭代器，它自身的值可以改变，但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值，但不能对该元素值赋值。
不要把const_iterator对象与const的iterator对象混淆起来。声明一个const迭代器时，必须初始化迭代器。一旦被初始化后，就不能改变它的值：

vector nums(10); // nums is nonconst
const vector::iterator cit = nums.begin();
*cit = 1;              //  ok: cit can change its underlying element
++cit;                 // error: can't change the value of cit

const_iterator对象可以用于const vector或非const vector，因为不能改写元素值。const迭代器这种类型几乎没什么用处：一旦它被初始化后，只能用它来改写其指向的元素，但不能使它指向任何其他元素：

const vector nines(10, 9); // cannot change elements in nines
//  error: cit2 could change the element it refers to and nines is const
const vector::iterator cit2 = nines.begin();
//  ok: it can't change an element value, so it can be used with a const vector
vector::const_iterator it = nines.begin();
*it = 10; //  error: *it is const
++it;     // ok: it isn't const so we can change its value