C/C++编程：浅谈reverse_iterator的base()函数

蔚落 2022-09-11 14:20 211阅读 0赞

# API #

> `std::reverse_iterator<Iter>::base`

*  从其 reverse\_iterator还原基础迭代器。

iterator_type base() const;                            (until C++17)
    constexpr iterator_type base() const;                  		(since C++17)

与其基础迭代器处理所有反向迭代器的标识是： `&*(rit.base() - 1) == &*rit.`

#include <iostream>     // std::cout
    #include <iterator>     // std::reverse_iterator
    #include <vector>       // std::vector
    
    int main () {
        
        std::vector<int> myvector;
        for (int i=0; i<10; i++) myvector.push_back(i);
    
        typedef std::vector<int>::iterator iter_type;
    
        std::reverse_iterator<iter_type> rev_end (myvector.begin());
        std::reverse_iterator<iter_type> rev_begin (myvector.end());
    
        std::cout << "myvector:";
        for (iter_type it = rev_end.base(); it != rev_begin.base(); ++it)   // iter_type 是一个正向迭代器。base()可以将一个反向迭代器变成一个正向迭代器
            std::cout << ' ' << *it;
        std::cout << '\n';
    
        return 0;
    }

![在这里插入图片描述][a12dc2b07214411ca9ca227c815baa4d.png]

> `std::reverse_iterator`

*  reverse\_iterator是一个迭代器适配器，它反转给定迭代器的方向，该迭代器必须至少是LegacyBidirectionalIterator或模型bidirectional\_iterator(从c++ 20开始)。换句话说，当提供双向迭代器时，std::reverse\_iterator将生成一个新的迭代器，该迭代器将从底层双向迭代器定义的序列的末尾移动到开头。
 *  对于由迭代器i构造的反向迭代器r，关系`&*r == &*(i-1)`始终为真(只要r是可解引用的);因此，反向迭代器是由经过末端一的迭代器对序列中的最后一个元素进行解引用而构造的。
 *  这是标准库容器的成员函数rbegin()和rend()返回的迭代器。  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_16_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    #include <iterator>
    #include <vector>
    
    int main()
    {
        
        std::vector<int> v = {
         0, 1, 2, 3, 4, 5 };
    
        using RevIt = std::reverse_iterator<std::vector<int>::iterator>;
    
        const auto it = v.begin() + 3;
        RevIt r_it{
        it};
    
        std::cout << "*it == " << *it << '\n'                     //3
                  << "*r_it == " << *r_it << '\n'                 //2
    ;
    }

![在这里插入图片描述][a17924cd7bf644a6be252f10921be773.png]

# 理论 #

调用reverse\_iterator的base成员函数可以产生"对应的"iterator，但这句话有些辞不达意。举个例子，看一下这段代码，我们首先把从数字1-5放进一个vector中，然后产生一个指向3的reverse\_iterator，并且通过reverse\_iterator的base初始化一个iterator：

vector<int> v;
    v.reserve(5);
    for(int i = 1；i <= 5; ++ i) {
         // 向vector插入1到5
    　　v.push_back(i);
    }
    vector<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3);
    vector<int>::iterator i(ri.base()); // 使i和ri的base一样

执行上述代码后，可以想到产生的结果就像这样：  
　![在这里插入图片描述][412f86aaedb44d0eaf8572e3253ae895.png]  
这张图很好，显示了reverse\_iterator和它对应的base iterator之间特有的偏移量，就像rbegin()和rend()与相关的begin()和end()一样，但并没有说出了所有你需要知道的东西。特别是，它并没有解释怎样在ri上实现你在i上想要完成的操作。有些容器的成员函数只接受iterator类型的参数，所以如果你想要在ri所指的位置插入一个新元素，你不能直接这么做，因为vector的insert函数不接受reverse\_iterator。如果你想要删除ri 所指位置上的元素也会有同样的问题。erase成员函数会拒绝reverse\_iterator，坚持要求iterator。为了完成删除和一些形式的插入操作，你必须先通过base函数将reverse\_iterator转换成iterator，然后用iterator来完成工作。

先让我们假设你要在ri指出的位置上把一个新元素插入v。特别的，我们假设你要插入的值是99。记住ri在上图中遍历的顺序是自右向左，而且插入操作会将新元素插入到ri位置，并且将原先ri位置的元素移到遍历过程的"下一个"位置，我们认为3应该出现在99的左侧。插入操作之后，v看起来像这样：  
![在这里插入图片描述][d4868f2fd7494dff9a0334ee61dd8689.png]  
当然，我们不能用ri来指定插入的地方，因为它不是一个iterator。我们必须用i来代替。如上所述，当ri指向3时，i（就是ri.base()）指向4。如果我们用ri来指定插入位置，那么用i指向插入位置，那个假设就是正确的。结论呢？

要实现在一个reverse\_iterator ri指出的位置上插入新元素，在ri.base()指向的位置插入就行了。对于insert操作而言，ri和ri.base()是等价的，而且ri.base()真的是ri对应的iterator。现在再来考虑删除元素的情况。回顾一下最初的vector（也就是在插入99之前）ri与i的关系：  
　![在这里插入图片描述][0141fc9fa016407a955d1465ef1239c4.png]  
　如果你要删除ri指向的元素，你不能直接使用i了，因为i与ri不是指向同一个元素。因此，你要删除的是i的前一个元素。要实现在一个reverse\_iterator ri指出的位置上删除元素，就应该删除ri.base()的前一个元素。对于删除操作而言，ri和ri.base()并不等价，而且ri.base()不是ri对应的iterator。我们还是有必要看看删除操作的代码，因为它还挺令人惊讶的。

vector<int> v;
     // 向v插入1到5，同上
    vecot<int>::reverse_iterator ri =
    find(v.rbegin(), v.rend(), 3); // 同上，ri指向3
    v.erase(--ri.base()); // 尝试删除ri.base()前面的元素；对于vector，一般来说编译不通过`

这个设计并不存在什么问题。表达式–ri.base()确实能够指出我们需要删除的元素。而且，它们能够处理除了vector和string之外的其他所有容器，它可能也能处理vector和string，但对于大多数vector和string的实现，它无法处理。在这样的实现下，iterator（和const\_iterator）会采用内建的指针来实现，所以ri.base()的结果是一个指针。C和C++都规定了不能直接修改函数返回的指针，所以在string和vector的迭代器是指针的STL平台上，像–ri.base()这样的表达式无法通过编译。要移植从一个由reverse\_iterator指出的位置删除元素时，你应该尽量避免修改base的返回值。没问题。如果你不能减少调用base的返回值，只需要先增加reverse\_iterator的值，然后再调用base。

// 同上
    v.erase((++ri).base()); // 删除ri指向的元素；
    // 这下编译没问题了！

因为这个方法适用于所有的标准容器，这是删除一个由reverse\_iterator指出的元素时首选的技巧。

现在已经很清楚了，reverse\_iterator的base成员函数返回一个"对应的"iterator的说法并不准确。对于插入操作而言，的确如此；但是对于删除操作，并非如此。当需要把reverse\_iterator转换成iterator的时候，有一点非常重要的是你必须知道你准备怎么处理返回的iterator，因为只有这样你才能决定你得到的iterator是否是你需要的。

[a12dc2b07214411ca9ca227c815baa4d.png]: /images/20220828/881a80304d0d445e8068e21166faf390.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/eff8c59880df4e1b9acb250373a5382f.png
[a17924cd7bf644a6be252f10921be773.png]: /images/20220828/7750f80dd5f14109987fd118134f55da.png
[412f86aaedb44d0eaf8572e3253ae895.png]: /images/20220828/de2b8ee696be4f9a954418c6a204ad00.png
[d4868f2fd7494dff9a0334ee61dd8689.png]: /images/20220828/2a6d00dfae764cb3b901bb84f855150f.png
[0141fc9fa016407a955d1465ef1239c4.png]: /images/20220828/572af1397a8148198d6bc4a62237d152.png