STL的反向迭代器

      灵动阳光: http://www.sssit.org/blog/articles/233.html

    反向迭代器reverse_iterator是一种反向遍历容器的迭代器，也就是从最后一个元素到第一个元素遍历容器。反向迭代器的自增(或自减)的含义反过来了：对于反向迭代器，++运算符将访问前一个元素，–运算符将访问下一个元素。

    在某些场景下，reverse_iterator能很好地适应应用需求。但容器的有些成员方法只支持iterator,如果你想在反向迭代器所指的位置插入一个新元素，或者是删除反向迭代器所指的元素是不行的，因为insert方法、erase方法都不支持reverse_iterator。要完了这些操作，必须将reverse_iterator转换成iterator，再用iterator完成这些操作。

    下面说明了反向迭代器与迭代器的关系，并列举了一些常用的操作。

反向迭代器与迭代器的转换

    reverse_iterator与iterator都继承自_Iterator_base，它们是可以相互转换的。

• 调用reverse_iterator的base()方法可以获取"对应的"iterator。
  
• 可以用iterator构造一个"对应的"reverse_iterator。
  

   下面的两个例子展示了它们之间的转换：

list<int> test_list;
for (size_t i = 1; i < 8; i++)
{
    test_list.push_back( i*2 );
}
list<int>::reverse_iterator rit = find(test_list.rbegin(), test_list.rend(), 8);
list<int>::iterator it(rit.base());
cout << *rit << endl;
cout << *it << endl;

   上面的代码是先查找到一个指向8的reverse_iterator，并reverse_iterator的base()方法得到一个iterator。但是从输出上看，iterator指向的元素的值并不是8，而是10。

list<int> test_list;
for (size_t i = 1; i < 8; i++)
{
    test_list.push_back( i*2 );
}
list<int>::iterator it = find(test_list.begin(), test_list.end(), 8);
list<int>::reverse_iterator rit(it);
cout << *it << endl;
cout << *rit << endl;

   上面的代码是先查找一个指向8的iterator，然后用该iterator构造一个reverse_iterator。但是从输出上看，reverse_iterator指向的元素并不是8，而是6。

   从上面这两个例子，我们看到reverse_iterator与iterator的这个"对应的"关系并不是一一对应的。那么反向迭代器与普通迭代器的关系到底是怎么样的呢？

反向迭代器与迭代器的关系

    下图清晰地显示了反向迭代器与迭代器之间的关系。

    从上图可以看出，对于同一个容器：

• end()与rbegin()、begin()与rend()、rit与rit.base()并不是指向同一个位置。
• 反向迭代器rit总是指向rit.base()的前一个位置。
  
• 反向迭代器标记的区间[rbegin()，rit)与迭代器标记的区间[rit.base()，end())是相同的。
  

    为什么会这样呢？从技术上讲，把普通迭代器与反向迭代器间的关系设计成这样是为了适应容器是左闭右开的区间这个特性。《C++标准模板库》里是这么说的："逆向迭代器的设计者运用了一个小技巧：他们实际上倒置了’半开原则’"。

反向迭代器的操作

   了解了反向迭代器与迭代器的关系，再来对容器进行操作就很简单了。下面是常用操作的例子，例子中用的test_list的内容如上图所示：

1. 遍历容器

for(list<int>::reverse_iterator rit = test_list.rbegin(); rit != test_list.rend(); ++rit)
{
    cout<< *rit << " ";
}

2. 插入元素

    假设要在rit指向的位置插入一个新元素150,那么150应该在8和10之间。对于rit而言，150应该插入到rit的前一个位置。对于it (it = rit.base()),150应该插入it的前一个位置。

所以，要实现在一个reverse_iterator rit指出的位置上插入新元素，在rit.base()指向的位置插入就行了。

    操作代码如下：

list<int>::reverse_iterator rit = find(test_list.rbegin(), test_list.rend(), 8);
test_list.insert(rit.base(), 150);

3. 删除元素

    假设要删除rit指向的元素，就不直能删除rit.base()指向的元素了，rit指向的是8，而rit.base()指向的是10。实际上我们要删除的是rit.base()的前一个元素。

所以，要实现在一个reverse_iterator rit指出的位置上删除元素，那么删除rit.base()的前一个元素就行了。

操作代码如下：

for(list<int>::reverse_iterator rit = test_list.rbegin(); rit != test_list.rend();)
{
    if (8 == *rit)
    {
        list<int>::iterator it = --rit.base() ;  // 用(++rit).base()也可;
        list<int>::iterator it_after_del = test_list.erase(it);
        rit = list<int>::reverse_iterator(it_after_del);
    }
    else
    {
        ++rit;
    }
}

    调用erase()删除元素后，返回值是指向被删除的元素的下一个元素的iterator，所以还需要把返回的iterator变成reverse_iterator赋值给rit。

当然，上面的代码写成这样也是一个意思：

for(list<int>::reverse_iterator rit = test_list.rbegin(); rit != test_list.rend();)
{
    if (8 == *rit)
    {
        rit = list<int>::reverse_iterator(test_list.erase(--rit.base()));
    }
    else
    {
        ++rit;
    }
}