使用自定义类的C++ std::set返回错误lower_bound值问题

问题描述 #

定义了Tile类，使用自定义比较器tCmp_id的std::set<Tile, tCmp_id>容器存储Tile对象，插入id为1、2、4、5的元素后，调用lower_bound(mkTile(3))和upper_bound(mkTile(3))时，预期分别返回id为2和4的元素，但实际两次输出均为4。

代码如下：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

class Tile {
    public:
        int id;
};
struct tCmp_id {
    bool operator()(Tile a, Tile b) const {
        return a.id < b.id;
    }
};

set<Tile, tCmp_id> TQ;

Tile mkTile(int id){
    Tile t;
    t.id = id;
    return t;
}

int main(){
    TQ.insert(mkTile(1));
    TQ.insert(mkTile(2));
    TQ.insert(mkTile(4));
    TQ.insert(mkTile(5));

    cout << (*TQ.lower_bound(mkTile(3))).id << endl;
    cout << (*TQ.upper_bound(mkTile(3))).id << endl;
}

原因分析 #

• API概念理解偏差

  • std::set::lower_bound(k)返回第一个不小于k的元素（基于比较器逻辑）。这里比较器tCmp_id以a.id < b.id作为排序依据，"不小于k"即元素id ≥ 3，集合中第一个满足该条件的是id=4的元素。
  • std::set::upper_bound(k)返回第一个大于k的元素，即元素id > 3，集合中第一个满足该条件的同样是id=4的元素。
  • 你预期lower_bound返回id=2是错误的，id=2是小于3的元素，而lower_bound的设计逻辑不会返回小于目标值的元素。若要获取小于等于3的最后一个元素，需要通过--TQ.upper_bound(mkTile(3))实现。

• 比较器效率问题（非功能错误）
  比较器的operator()使用了值传递参数（Tile a, Tile b），每次比较都会拷贝Tile对象，虽不影响功能，但建议改为const引用传递（const Tile& a, const Tile& b）以提升运行效率。

修复示例（获取小于等于3的元素） #

如果需要得到id=2的元素（即集合中小于等于3的最后一个元素），可修改main函数代码：

int main(){
    TQ.insert(mkTile(1));
    TQ.insert(mkTile(2));
    TQ.insert(mkTile(4));
    TQ.insert(mkTile(5));

    // 获取第一个大于3的元素，向前移动一位得到小于等于3的最后一个元素
    auto upper_iter = TQ.upper_bound(mkTile(3));
    if (upper_iter != TQ.begin()) {
        auto target_iter = prev(upper_iter);
        cout << (*target_iter).id << endl; // 输出2
    }
    cout << (*TQ.upper_bound(mkTile(3))).id << endl; // 输出4
}

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