std::reverse_iterator::base

时间:2021-10-08 11:45:36

google chromium base MRU_Cache 支持反向erase

iterator Erase(iterator pos) {
  deletor_(pos->second);
  index_.erase(pos->first);
  return ordering_.erase(pos);
}

// MRUCache entries are often processed in reverse order, so we add this
// convenience function (not typically defined by STL containers).
reverse_iterator Erase(reverse_iterator pos) {
  // We have to actually give it the incremented iterator to delete, since
  // the forward iterator that base() returns is actually one past the item
  // being iterated over.
  return reverse_iterator(Erase((++pos).base()));
}

有些容器的成员函数只接受iterator类型的参数,不接受reverse_iterator,为完成些形式的操作,必须先通过base函数将reverse_iterator转换成iterator。

Iterator base() const;             (until C++17)

constexpr Iterator base() const;   (since C++17)

Returns the underlying base iterator. That is std::reverse_iterator(it).base() == it.

The base iterator refers to the element that is next (from the std::reverse_iterator::iterator_typeperspective) to the element the reverse_iterator is currently pointing to. That is &*(rit.base() - 1) == &*rit.

Example
#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>;
    RevIt r_end(v.begin());
    RevIt r_begin(v.end());  for (auto it = r_end.base(); it != r_begin.base(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
}

Output:   0 1 2 3 4 5


Example

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);  // 使ri指向3
vector<int>::iterator i(ri.base()); // 使i和ri的base一样

std::reverse_iterator::base

  • ri遍历的顺序是rbegin() -> rend()。
  • reverse_iterator与base iterator之间偏移量,如rbegin()()、end及rend()、begin()一样。

在ri位置上插入新元素99,原ri位置的元素移到遍历过程的“下一个”位置。

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

对于insert操作而言,ri和ri.base()是等价的,而且ri.base()真的是ri对应的iterator。

std::reverse_iterator::base

删除ri指向的元素,不能直接使用i了,因为i与ri不是指向同一个元素。因此要删除的是i的前一个元素。

实现在一个reverse_iterator ri指出的位置上删除元素,就应该删除ri.base()的前一个元素。

对于删除操作而言,ri和ri.base()并不等价,而且ri.base()不是ri对应的iterator。

std::reverse_iterator::base
Example

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

在这样的实现下,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是否是你需要的。