C++容器中使用reference_wrapper时修改排序属性的影响

代码片段 #

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x=3;
    int y=1;
    int z=2;
    cout<<(&x)<<' '<<(&y)<<' '<<(&z)<<endl;
    set<reference_wrapper<int>> a;
    a.insert(ref(x));
    a.insert(ref(y));
    a.insert(ref(z));
    for(const auto& i: a) cout<<i<<' '<<endl;
    y=10;
    for(const auto& i: a) cout<<i<<' ';
    return 0;
}

问题 #

当修改容器用于排序的属性时，底层容器会发生什么变化？

分析与结论 #

std::set是基于红黑树实现的有序关联容器，它仅在元素插入阶段根据当时的元素值完成排序并维护有序结构，不会主动监测元素值的后续变化。针对上述代码的情况：

• 由于容器持有的是reference_wrapper<int>，修改原变量y的值后，容器中引用指向的值会被正确更新，第二次遍历时能输出修改后的10；
• 但set的内部有序结构不会自动调整，原本值为1的y是容器中的最小元素，修改为10后理应成为最大元素，但容器的排序顺序仍保持插入时的状态，导致遍历顺序与当前值的排序规则不符，出现顺序错误；
• 这种情况会破坏set的核心不变量（容器始终有序），后续对容器的操作（如查找、插入新元素）可能触发未定义行为。

因此在set这类依赖元素有序性的容器中使用reference_wrapper时必须格外谨慎，绝对不能修改会影响排序逻辑的元素值。

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