为何向std::set插入20个不同vector后size仅为14？

问题代码 #

typedef vector<int> vec;

struct classcomp {
    bool operator() (const vec& vec1, const vec& vec2) const{
        if (vec1[0] > vec2[0]){
            return true;
        }
    
        return false;
    }            
};

int main() {
    set<vec, classcomp> v; 

    for (int i = 0; i < 20; i++) {
        v.insert({rand() % 20, i});
    }

    cout << "size: " << v.size() << endl;

    for (auto e : v) {
        cout << e[0] << " " << e[1] << endl;
    }
}

核心原因 #

std::set判断元素是否重复的依据是自定义比较器的严格弱序规则：对于两个元素a和b，如果comp(a,b)和comp(b,a)都返回false，set会判定这两个元素是等价的，不会插入后者。

你的比较器只判断了vec1[0] > vec2[0]的情况，当两个vector的第一个元素相等时，不管第二个元素是否唯一，comp(vec1, vec2)和comp(vec2, vec1)都会返回false，此时set会把它们视为等价元素，仅保留第一个插入的实例。

你用rand()%20生成第一个元素，20次插入中必然存在多个vector的第一个元素重复，这些重复项都会被set过滤，最终size为14说明有6组第一个元素重复的情况，每组只保留了一个元素。

修复方法 #

修改比较器，当第一个元素相等时，继续比较第二个元素，确保所有不同的vector都能被区分：

struct classcomp {
    bool operator() (const vec& vec1, const vec& vec2) const{
        if (vec1[0] != vec2[0]){
            return vec1[0] > vec2[0];
        }
        // 第一个元素相等时，比较第二个元素，维持严格弱序
        return vec1[1] > vec2[1];
    }            
};

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