如何选择容器存储Element结构体：按_key排序、_type区分重复键

需求与结构体定义 #

需要存储如下结构体：

struct Element
{
    int       _key;
    enum_type _type;
    double    _value;
};

插入规则：

• 按_key升序排序，_key小的元素优先排列；
• _key相同时，以_type区分元素：_key和_type都相同的元素，后插入的覆盖先插入的；_key相同但_type不同的元素，顺序无关且不会互相覆盖。

示例：

• 插入Element x(6, enum_type::A, 57.76)和Element y(7, enum_type::B, 104.29)，x会排在y之前；
• 插入Element x(6, enum_type::A, 57.76)和Element y(6, enum_type::B, 104.29)，二者共存且顺序无关；
• 若插入Element z(6, enum_type::A, 80.1)，则z会覆盖x的_value。

推荐容器与实现方案 #

核心：自定义比较器 #

要满足需求，必须定义一个严格弱序比较器，让容器以_key为主要排序依据，同时将_key+_type作为元素的唯一标识：

enum class enum_type { A, B, C };

struct ElementCompare {
    bool operator()(const Element& lhs, const Element& rhs) const {
        // 优先按_key升序排序
        if (lhs._key != rhs._key) {
            return lhs._key < rhs._key;
        }
        // _key相同时，按_type区分（确保不同_type的元素被视为独立节点）
        return lhs._type < rhs._type;
    }
};

容器选择 #

1. std::set<Element, ElementCompare>

• 天然支持有序存储，插入、查找的时间复杂度为O(log n)；
• 当插入_key+_type完全匹配的元素时，默认不会自动覆盖，可通过insert的返回值手动处理覆盖逻辑：

  auto [it, inserted] = my_set.insert(new_element);
  if (!inserted) {
      // C++20及以上可通过extract高效修改
      auto node = my_set.extract(it);
      node._value = new_element._value;
      my_set.insert(std::move(node));
      // 旧版本可先删除再插入
      // my_set.erase(it);
      // my_set.insert(new_element);
  }
  

• 同_key不同_type的元素会被保留，符合需求。

2. Boost flat_set<Element, ElementCompare>

• 基于有序数组实现，内存连续，缓存命中率更高，适合对内存性能敏感的场景；
• 插入、删除的时间复杂度为O(n)（需要移动数组元素），但查找效率接近std::set（二分查找）；
• 同样支持自定义比较器，满足排序和元素区分的规则。

不推荐std::map的原因 #

std::map需要键值分离，若用std::map<std::pair<int, enum_type>, double>实现，需要额外维护键与_value的映射，不如直接用set存储整个Element结构体直观。

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