C++ multiset/list迭代器引用不存在值的异常问题

问题根源 #

你遇到的是迭代器未定义行为，具体分两点：

• 初始迭代器非法：构造函数里，orderedNums是空容器，orderedNums.begin()返回的是尾后迭代器（和end()完全相同），直接解引用这个迭代器属于C++标准明确禁止的未定义行为，输出的1、2、3都是随机的内存垃圾值。
• 迭代器未更新：虽然multiset和list的迭代器不会因为插入元素失效，但你的p1/p2自始至终指向的是最初空容器的尾后迭代器，这个迭代器已经和当前容器的元素集合无关，后续每次解引用依然是未定义行为。

修复方案 #

要让p1/p2持续指向容器内的特定元素（比如中位数相关位置），需要在每次插入元素后，重新计算并定位这两个迭代器的位置，而非保存初始的空容器迭代器。

修改后的示例代码（以中位数场景为例）：

#include <iostream>
#include <set>
#include <iterator> // 用于next/prev函数

using namespace std;

class MedianFinder
{

private:
    multiset<int> orderedNums;
    multiset<int>::iterator p1, p2;

public:
    MedianFinder()
    {
        // 空容器时不初始化迭代器，避免非法解引用
    }

    void addNum(int num)
    {
        orderedNums.insert(num);
        int size = orderedNums.size();

        // 根据容器大小重新定位p1和p2
        auto mid = next(orderedNums.begin(), size / 2);
        if (size % 2 == 1) {
            // 奇数个元素，两个迭代器都指向中间元素
            p1 = p2 = mid;
        } else {
            // 偶数个元素，p1指向中间左，p2指向中间右
            p2 = mid;
            p1 = prev(mid);
        }

        // 现在解引用p1/p2是合法的
        cout << "p1: " << *p1 << " p2: " << *p2 << endl;

        cout << "ordered: ";
        for (auto it = orderedNums.begin(); it != orderedNums.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }
};

int main()
{
    MedianFinder medianFinder;
    medianFinder.addNum(5); 
    medianFinder.addNum(7); 
    medianFinder.addNum(9); 
    return 0;
}

预期输出 #

运行后会得到符合逻辑的结果：

p1: 5 p2: 5
ordered: 5 
p1: 5 p2: 7
ordered: 5 7 
p1: 7 p2: 7
ordered: 5 7 9

内容的提问来源于stack exchange，提问作者Joelin Zou