C++ set容器去重与排序 _ insert函数与自定义比较器【实战】

C++ set容器去重与排序：insert函数与自定义比较器实战解析

set插入重复元素时，如何准确判断insert是否成功？

关键在于直接读取返回值中的布尔标志。C++标准库为set::insert函数设计了一个std::pair类型的返回值。其中的second成员是一个布尔值：如果它为true，恭喜你，新元素被成功插入了；如果它是false，那就意味着这个键值已经存在于集合中，本次插入操作实际上并未执行。

这里有个常见的误区需要警惕：千万别依赖返回的iterator是否等于end()来判断。这个迭代器总是有效的——它要么指向新插入的元素，要么指向集合中已经存在的那个等价元素。所以，用它来“判重”是行不通的。

举个例子，下面这种写法就是典型的无效判断：

if (s.insert(x).first != s.end()) { ... } // 这个条件永远成立，毫无意义

正确的打开方式应该是这样的：

auto [it, inserted] = s.insert(x); // C++17结构化绑定，清晰又方便
if (inserted) {
    // 真正新增了元素，可以在这里处理新增逻辑
} else {
    // x 已存在，it 指向集合中那个原有的元素
}

自定义比较器必须满足「严格弱序」，否则set行为未定义

很多看似诡异的崩溃或逻辑错乱，根源往往不是语法错误，而是自定义的比较器违反了“严格弱序”的基本规则。这套规则主要包含三个条件：非自反性、反对称性和传递性。新手最容易踩的坑，就是不小心用<=或!=来实现比较逻辑。

例如下面这个错误的写法：

struct BadComp {
    bool operator()(const int& a, const int& b) const {
        return a <= b; // ❌ 违反了非自反性：a <= a 为 true，这会导致set认为 a < a 成立，进而引发未定义行为
    }
};

正确的做法是始终坚持只使用<来定义严格的“小于”关系，并确保逻辑清晰无歧义。下面是一些常见场景的正确写法参考：

• 按绝对值排序：return abs(a) < abs(b);（需要注意处理绝对值相等的不同数值）
• 字符串先按长度、再按字典序比较：return s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2);
• 想要降序排列：直接写return a > b;即可，不要绕弯子写!(a < b)，后者在某些边界情况下可能不满足传递性。

想用set去重+排序，但又需要保留原始插入顺序？

答案是：set本身做不到。set容器会严格根据你提供的比较器（或默认的less）对所有元素进行排序，原始的插入顺序会被完全丢弃。如果你的核心需求是“去重但保持元素第一次出现的顺序”，那么set就不是合适的工具。即使你尝试给每个元素加上时间戳字段，在多线程或重复值干扰下，也很难保证稳定和高效。

更务实的替代方案是这样的：

• 使用std::unordered_set来快速判断元素是否已出现，同时用一个std::vector来按序存储唯一的元素序列。代码模式通常是：if (seen.insert(x).second) unique_vec.push_back(x);
• 如果后续还需要对这个唯一序列进行快速查找，可以将其封装成一个小型工具类，内部同时维护一个unordered_set和一个vector。
• 切记不要强行给set套用包含时间戳的自定义比较器。这会让排序逻辑变得复杂，降低find等操作的效率，还可能因为时间戳的重复或更新导致意想不到的行为。

性能敏感场景：单次insert调用 vs 批量构造初始化

当需要插入几十个甚至更多元素时，性能差异就开始显现了。逐个调用insert方法，时间复杂度是O(n log n)。而使用迭代器区间进行构造初始化（例如set s(v.begin(), v.end());），底层实现可能会进行优化，虽然时间复杂度可能仍是O(n log n)，但常数因子更小，更重要的是减少了多次内存分配的开销，提升了内存访问的局部性。

在以下几种实测场景中，差异会比较明显：

• 从vector批量去重排序：直接使用区间构造函数，通常比循环调用insert快10%到30%。
• 数据基本有序时：可以考虑使用std::set::insert的“提示”版本（即带一个迭代器参数作为插入位置提示）。如果提示位置给得准，插入的均摊时间复杂度可以降到接近O(1)；但如果提示不准，性能就会退化到普通的insert。
• 编译器优化：像GCC这样的编译器在-O2优化级别下，对于set{a,b,c}这类初始化列表，可能会进行常量折叠等激进优化。

当然，如果插入操作分散在程序的不同逻辑分支中，就不要强行合并它们。代码的可读性和可维护性始终应该放在第一位。

最后，还有一个容易被忽略的性能细节：自定义比较器的类型是set模板参数的一部分。如果这个比较器类型包含了复杂的内部状态或较大的对象，可能会显著增加模板实例化时的编译时间，以及最终二进制文件的体积。在定义比较器时，保持其轻量和简单，通常是一个好习惯。