自定义比较器的std::map未插入全部元素问题排查

问题根源 #

std::map的自定义比较器必须满足严格弱序规则：对于任意两个键lhs和rhs，如果comp(lhs, rhs)和comp(rhs, lhs)同时为false，map会判定这两个键等价，后续插入等价键的元素会被直接忽略。

你的比较器在两种场景下触发了等价判定：

• 当两个索引对应的data值都是INPUT时：data[lhs] < data[rhs]结果为false（INPUT值固定为2），同时comp(rhs, lhs)也为false，map会认为这两个索引是同一个键，只保留第一个插入的元素（比如索引0插入后，3、5都会被忽略）。
• 当两个索引对应的data值相同且非INPUT时：比如索引2（OUTPUT）和4（OUTPUT），同样会因为data[lhs] < data[rhs]为false，被判定为等价，插入4时会被忽略。

这就是最终map仅保留3个元素的原因。

修正方案 #

修改比较器，在同类型场景下比较索引本身，确保每个索引都是唯一键，同时满足排序需求：

#include <vector>
#include <map>
#include <cstdio>

enum Type {
  OUTPUT = 1,
  INPUT = 2,
  INOUT = 3
};

std::vector<int> data = {INPUT, INOUT, OUTPUT, INPUT, OUTPUT, INPUT};

struct Comparator {
  bool operator()(int lhs, int rhs) {
    // INPUT 优先排在最前面
    bool lhs_is_input = (data[lhs] == INPUT);
    bool rhs_is_input = (data[rhs] == INPUT);
    
    if (lhs_is_input != rhs_is_input) {
      return lhs_is_input;
    }

    // 同是 INPUT，按索引升序排列
    if (lhs_is_input) {
      return lhs < rhs;
    }

    // 非 INPUT，先按 Type 值升序，值相同则按索引升序
    if (data[lhs] != data[rhs]) {
      return data[lhs] < data[rhs];
    }
    return lhs < rhs;
  }
};

int main()
{
  std::map<int, char, Comparator> m;

  for (unsigned i = 0; i < data.size(); ++i) {
    m.insert( {i, 'a' + i} );
  }

  // 遍历验证结果
  for (const auto& pair : m) {
    printf("%d -> '%c'\n", pair.first, pair.second);
  }
}

输出结果 #

运行后map的元素顺序完全符合预期：

0 -> 'a'
3 -> 'd'
5 -> 'f'
2 -> 'c'
4 -> 'e'
1 -> 'b'

排序逻辑说明：

1. 所有INPUT对应的索引（0、3、5）排在最前面，且按索引从小到大排列
2. 非INPUT元素先按Type值升序（OUTPUT=1 < INOUT=3），同Type的按索引升序排列

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