如何在O(log n)时间内删除C++ set中指定ID的自定义结构体元素？

可以做到，但需要让set的排序规则基于ID字段，具体有两种常见实现方式：

方式一：重载结构体的operator<，仅按ID比较 #

set是有序容器，默认通过operator<完成排序和元素匹配。我们只需让car的比较逻辑仅依赖唯一的ID，就能通过构造临时对象快速定位目标元素：

struct car {
    int ID;
    // 其他四个成员变量
    bool operator<(const car& other) const {
        return ID < other.ID; // 仅以ID作为排序依据
    }
};

set<car> s;
// 删除ID为x的元素
s.erase(car{x});

此时erase内部会通过红黑树以O(log n)时间找到匹配元素，再完成删除，整体复杂度为O(log n)。

方式二：给set指定自定义比较器 #

如果不想修改结构体的默认operator<，可以为set单独指定基于ID的比较器：

struct car {
    int ID;
    // 其他四个成员变量
};

struct CompareByID {
    bool operator()(const car& a, const car& b) const {
        return a.ID < b.ID;
    }
};

set<car, CompareByID> s;
// 删除ID为x的元素
s.erase(car{x});

这种方式同样能让set按ID有序存储，erase操作的时间复杂度保持O(log n)。

关键注意事项 #

• 必须保证set的排序逻辑基于ID，否则无法通过临时对象快速定位元素（若用std::find_if遍历查找，时间复杂度会退化为O(n)）。
• 由于题目明确ID唯一，构造仅包含目标ID的临时car对象即可精准匹配对应元素，无需初始化其他成员变量。

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