0

考虑玩具程序（post.cpp）：

#include <iostream>
#include <vector>

using namespace std;
int main() {
        vector<int > a;
        int i;
        for(i=0;i<10;i++)
                a.push_back(i);
        auto it=a.rbegin();
        while(it!=a.rend()) {
                if ((*it % 2)==0) {
                                cout << "about to erase "<<*it<<endl;
                                a.erase((it++).base());
                }
                else {
                        ++it;
                }
        }
        for(auto it2=a.begin(); it2 != a.end(); it2++) {
                cout << *it2 << endl;
        }
        return 0;
}

我要做的是测试均匀性，然后删除当前数字，因为(it++)应该返回当前迭代器，然后推进迭代器。这是我得到的输出：

$ ./post 
about to erase 8
about to erase 6
about to erase 4
about to erase 2
about to erase 0
0
2
4
6
8

但是，如果我将行更改a.erase((it++).base());为a.erase((++it).base());，我会得到正确的行为。为什么是这样？

有用的说明：我使用的是base()因为 reverse_iterators 不能用于erase(). 有一个应用程序，我想在向量上反向擦除东西。

4

2 回答 2

3

base()反向迭代器的 偏移 1。所以rbegin().base() == end()和rend().base() == begin()。

这只不过是这个反向循环的概括：

for (size_t i = 0; i != N; ++i)
{
    mutate(array[N - i - 1]);
}   //                 ^^^

循环以相反的顺序遍历数组，并注意我们如何- 1在“迭代器”上需要 a。

更新：现在让我们研究一下什么是反向迭代器：它只是一个双向迭代器的包装器。假设调用了反向迭代器it；然后它有一个普通的迭代器成员it.base()。例如，v.rbegin().base() == v.end()。当您说++it时，这只是--it.base()（从概念上）调用。真正的魔法是取消引用操作：这必须在底层迭代器之前给我们一个元素：

*it == *(it.base() - 1)

这与告诉我们数组后面的第i 个元素偏移 1的算法完全相同：这也向我们展示了为什么我们需要一个双向迭代器来形成反向迭代器。array[N - i - 1]

现在很清楚我们如何通过反向迭代器从不会使迭代器无效的容器中擦除，例如任何基于节点的容器：

if (meets_condition(*it))   // this examines *(it.base() - 1)!
{
     auto b = it.base();
     container.erase(it.base() - 1);
     it = std::reverse_iterator(b);
}

请记住，这要求擦除不会使除被擦除者之外的任何迭代器无效，就像在任何基于节点的容器中一样。像这样从向量中擦除会更加困难。对于向量，擦除会使所有经过擦除的迭代器（正向）无效，因此我们必须使用erase函数的返回值：

if (meets_condition(*ut))   // again, examine *(it.base() - 1)
{
    it = std::reverse_iterator(container.erase(it.base() - 1));
}

在图片中（我们正在删除元素“5”）：

+---+---+---+---+---+---+---+
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |     =:   v
+---+---+---+---+---+---+---+
              ^   ^
              |   |
|             |   +--- it.base()
|             |
|             +--- *it == *(it.base() - 1)
|
V

+---+---+---+---+---+---+
| 2 | 3 | 4 | 6 | 7 | 8 |
+---+---+---+---+---+---+
          ^   ^
          |   |
          |   +--- result of v.erase(it.base() - 1)
          |
          +--- *(std::reverse_iterator(v.erase(it.base() - 1)))
于 2012-09-25T16:55:50.547 回答
1

不是您的问题的答案，而是您的问题的解决方案：使用比您当前正在做的更有效的擦除删除习惯用法：

bool even( int value ) { return !(value%2); }
std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 }; // Assuming C++11 or build it otherwise
v.erase( std::remove_if( v.begin(), v.end(), even ),
         v.end() );

效率上的区别在于，remove_if它只会将容器中剩余的值复制一次到最终位置，而您的算法可能会多次复制某些元素。特别是 9 将被复制 4 次，7 将被复制 3 次，依此类推。

于 2012-09-25T17:05:07.883 回答