迭代器失效问题

在看leetcode题解的时候，不明白为什么可以一边持有容器的迭代器，一边对容器进行修改。如下代码的left和right变量。

class MedianFinder {
    multiset<int> nums;
    multiset<int>::iterator left, right;

public:
    MedianFinder() : left(nums.end()), right(nums.end()) {}

    void addNum(int num) {
        const size_t n = nums.size();

        nums.insert(num);
        if (!n) {
            left = right = nums.begin();
        } else if (n & 1) {
            if (num < *left) {
                left--;
            } else {
                right++;
            }
        } else {
            if (num > *left && num < *right) {
                left++;
                right--;
            } else if (num >= *right) {
                left++;
            } else {
                right--;
                left = right;
            }
        }
    }

    double findMedian() {
        return (*left + *right) / 2.0;
    }
};

事实上这和multiset的底层实现相关。mutliset底层实现是红黑树，节点之间用指针连接，插入新的元素不会导致原先节点的位置发生改变。所以代码的操作是安全的。而vector这样的数据结构就不一定了，因为它在插入的过程中需要进行扩容，改变元素的位置。

深入探究

map/set/multimap/multiset的底层实现是红黑树，list是链表。所以对于这些容器来说，插入insert新的元素不会导致原先的迭代器失效，而删除erase一个元素会导致删除元素的迭代器失效。

vector/string 在插入insert元素的时候，如果进行了扩容会导致所有迭代器失效；没有扩容由于需要将后面的元素整体向后移动，也会导致插入元素后面的所有迭代器失效。删除erase元素的时候，由于需要将后面的元素整体向前移动，也会导致删除元素后面的所有迭代器失效。

更详细的内容参考Stackoverflow，参考链接2。原理大同小异。

类比于Rust，是不会让你同时持有对一个容器的多个可变引用的。保证了安全的同时，极大的减轻了编程者的心智负担，代价则是灵活性的丧失。孰优孰劣没有答案。