面试题：C++ set 容器插入冲突优化及自定义场景

Question

设计一个自定义类 MyClass 用于存储复杂数据结构，并且将 MyClass 对象插入到 set<MyClass> 中。假设存在一种特殊情况，即两个 MyClass 对象在某些属性上相等，但在其他属性上不同，而在 set 插入时你希望将这些对象视为相同元素处理冲突。请实现 MyClass 类的相关比较函数，并编写代码展示如何插入并处理这种特殊的插入冲突场景，同时分析这种设计对性能的影响及可能的优化方向。

Answer 1

1. 实现 MyClass 类及相关比较函数

#include <iostream>
#include <set>
#include <string>

class MyClass {
private:
    int id;
    std::string name;
    int otherProperty;

public:
    MyClass(int id, const std::string& name, int otherProperty)
        : id(id), name(name), otherProperty(otherProperty) {}

    // 重载比较运算符，只比较 id 和 name，忽略 otherProperty
    bool operator<(const MyClass& other) const {
        if (id != other.id) {
            return id < other.id;
        }
        return name < other.name;
    }

    friend std::ostream& operator<<(std::ostream& os, const MyClass& obj) {
        os << "MyClass(id=" << obj.id << ", name=" << obj.obj.name << ", otherProperty=" << obj.otherProperty << ")";
        return os;
    }
};

2. 插入并处理插入冲突场景的代码

int main() {
    std::set<MyClass> mySet;

    MyClass obj1(1, "Alice", 100);
    MyClass obj2(1, "Alice", 200); // 除 otherProperty 外与 obj1 相同

    mySet.insert(obj1);
    auto result = mySet.insert(obj2);

    if (result.second) {
        std::cout << "Inserted successfully." << std::endl;
    } else {
        std::cout << "Object already exists in the set." << std::endl;
    }

    // 遍历集合
    for (const auto& obj : mySet) {
        std::cout << obj << std::endl;
    }

    return 0;
}

3. 性能影响及优化方向分析

• 性能影响：
  • 查找性能：通过重载 operator< 简化比较逻辑，std::set 的查找复杂度仍保持为 $O(\log n)$，其中 $n$ 是集合中元素的数量。因为 std::set 基于红黑树实现，这种比较方式保证了树的平衡性。
  • 插入性能：每次插入时，std::set 需要根据比较函数确定插入位置，由于只比较部分属性，减少了比较的工作量，在一定程度上可能提高插入性能。但如果元素数量庞大，树的平衡调整操作仍可能带来性能开销。
• 优化方向：
  • 哈希表替代：如果性能要求更高，可以考虑使用 std::unordered_set。需要为 MyClass 实现哈希函数，哈希表的平均查找和插入复杂度为 $O(1)$，能显著提高性能，但可能会消耗更多内存。
  • 减少比较开销：确保比较函数尽可能高效。如果 id 和 name 比较操作本身开销较大，可以考虑对这些属性进行预处理，例如提前计算哈希值等方式减少每次比较的时间。