如果 std::vector::insert 由反向迭代器提供，它会做什么？

Question

我正在填充矢量以按以下方式保持其顺序

vector<int>::iterator it = upper_bound(arr.begin(), arr.end(), value);
arr.insert(it, value);

现在我想保持相反的顺序。如果我这样做怎么办

vector<int>::iterator it = upper_bound(arr.rbegin(), arr.rend(), value).base();
arr.insert(it, value);

将

arr.insert(it, value);

工作正常，即在 arr?

中找到条目后放入新值

什么是复杂性？在迭代开始时插入元素需要多长时间，即在向量的末尾？接近 O(1) 对吧？

我试过了

vector<int> src = {10, 1, 3, 7, 2, 100};
    vector<int> dst;

    for (auto it=src.begin(); it!=src.end(); ++it) {
        //auto it2 = upper_bound(dst.begin(), dst.end(), *it);
        vector<int>::iterator it2 = upper_bound(dst.rbegin(), dst.rend(), *it).base();
        dst.insert(it2, *it);
    }

它奏效了，但为什么呢？如果 it2 是普通迭代器，那么，例如在 {10, 1, 3 中搜索 7 时，it2 将指向 10 而 insert 将插入 7 在 10.

之前

之后怎么显示的？

如下代码

int main() {

    vector<int> src = {10, 1, 3, 7, 2, 100};
    vector<int> dst;

    auto begin = src.begin();

    for (auto it=src.begin(); it!=src.end(); ++it) {
        cout << *it << endl;

        //auto it2 = upper_bound(dst.begin(), dst.end(), *it);
        vector<int>::iterator it2 = upper_bound(dst.rbegin(), dst.rend(), *it).base();
        if (it2 == begin) {
            cout << "begin" << endl;
        }
        dst.insert(it2, *it);
    }

    cout << dst << endl;

}

打印

10
1
3
7
2
100
100, 10, 7, 3, 2, 1

即它从不打印“开始”。但是为什么？

Answer 1

If it2 is normal iterator, then, for example when searching for 7 in {10, 3, 1} it2 will point to 10 and insert will insert 7 BEFORE 10.

除了反向迭代器取消引用旁边的值它是 base （在基本类型的 pov 之后，在反向的 pov 之前） .您可以通过取消引用 it2 来观察这一点（只要它在 dst.end() 之前），在这种情况下它指向 3。

这是更多的中间输出，showing the difference

int main() { std::vector<int> src = {10, 1, 3, 7, 2, 100}; std::vector<int> dst; for (int i : src) { std::cout << i << " "; auto it = upper_bound(dst.rbegin(), dst.rend(), i); auto it2 = it.base(); if (it != dst.rend()) { std::cout << *it << " "; } else { std::cout << "first "; } if (it2 != dst.end()) { std::cout << *it2; } else { std::cout << "last"; } std::cout << std::endl; dst.insert(it2, i); } std::cout << dst << std::endl; }

如果 std::vector::insert 由反向迭代器提供，它会做什么？

What does std::vector::insert does, if it is fed by reverse iterator?

c++

iterator

stl

vector