c++ - 在迭代排序的 stl 容器时插入元素

Question

当我的代码在迭代时将元素插入 std::set 时，我发现了意外的结果。我需要对此有所启发。

这是测试代码：

    template<class Ti, class T>
    void iteration_insertion(Ti start, Ti end, T& S){
        for (auto ite=start;ite!=end;++ite){
            auto before=*ite;
            if(*ite % 2)
                S.insert(*ite*2);
            else
                S.insert(*ite/2);
            if(before!=*ite)
                cout<<before<<","<<*ite<<endl;
        }
    }
    void test() {
        set<int> S1({4,7,10,13}),S2(S1);
        cout<<"ascending\n";
        iteration_insertion(S1.begin(),S1.end(),S1);
        cout<<"descending\n";
        iteration_insertion(S2.rbegin(),S2.rend(),S2);
    }

结果：

ascending
descending
13,26

我们可以看到迭代器指向的元素在插入后有时会发生变化。但我不知道什么时候会发生。在测试代​​码中它只发生了一次，降序为 13。为什么在升序迭代中没有这种不匹配？为什么在降序迭代中 7 没有不匹配？如何防止它发生？我很好，新的附加值可以在以后迭代，这是意料之中的。我只是不希望通过插入更改迭代器。

测试代码可以是一种通用的启发式实践：从每个当前状态生成新状态以供进一步检查。

标签： c++stliterator

Answer 1

为了考虑容器的所有元素，反向迭代器将元素的迭代器存储在取消引用时获得的元素之后。例如，结果rbegin()内部存储了一个过去的迭代器。当您取消引用时，将生成存储的迭代器的副本，并且该副本在取消引用之前递减。

本质上，使用的标准代码的简化版本：

template<typename Iter>
struct reverse_iterator {
    Iter base;

    auto& operator++() { --base; return *this; }
    auto& operator*() {
        auto copy = base;
        --copy;
        return *copy;
    }
};

auto std::set::rbegin() {
    return reverse_iterator{this->end()};
}

将此应用于您的情况，您从rbegin(). 取消引用它会为您提供最后一个元素 13。当您插入 26 时，它会在 13 之后插入，但在内部存储在ite. 当您ite再次取消引用时，会生成一个内部单过去迭代器的副本，并将其递减到 13 和 26 之间的位置，然后取消引用以提供 26。

这是解释的图片版本，以防有帮助：