std::map的奇怪行为

Question

I have a

std::map<a,std::vector<b>> m;

a是一个结构体

struct a
{
  std::string c,d;
bool operator<(const a &o)
{ return !(c==o.c && d==o.d);}
}

我将以如下方式填充地图：

for(/*blah blah*/)
{
  m[A].push_back(B)
}

并在填写后打印一些东西。

std::cout << "Size:" << m.size() << std::endl;
int i=0;
for(std::map<a,std::vector<b>>::iterator it = m.begin(); it != m.end();i++,it++)
{
   std::cout << "[" <<i <<"] " << it->second.size() << std::endl;
}

我正在收到的输出是：

Size: 12
[0] 1
[1] 3

有人能解释一下为什么 map::size() 显示为 12 ，而实际只迭代了 2 个元素吗？

- tejas

---

抱歉，您的问题是关于循环只在地图大小为12时迭代两次，还是关于向量大小从1到3的问题？ - EdChum

更新了更多信息。 - tejas

d==0.d - 这里的 d 是零，不是字母 o。你真的在展示你的实际代码吗？ - lethal-guitar

不，这不是实际的代码，a::operator< 在这里起到了什么作用？ - tejas

一个 map 是一个有序的容器。它构建了一棵二叉树。因此，它需要知道一个特定元素是在另一个元素之前还是之后。默认情况下，operator< 用于此目的。你的实现完全破坏了 map 的契约（期望）。在你的实现中，a < b == b < a。一个可用的 operator< 应该足以对键进行排序。 - Adam

我觉得这个问题非常有趣。虽然遗憾的是，这里没有SSCCE，但我使用以上一些代码制作了一个可编译版本（VS2012，我必须适应一些东西）。根据键入的密钥，该程序甚至在某些情况下会崩溃。Matt在下面提供了解决方案。@Matt：好答案！ - TobiMcNamobi

Answer 1

将比较函数更改为

bool operator<(const a &o) const
{
    if ( c == o.c )
         return d < o.d;

    return c < o.c; 
}

请注意，将其设为非成员函数通常更有用。

您的比较函数必须遵循以下规则：

如果我们定义equiv(a, b)为!comp（a，b）&&！comp（b，a），则要求comp和equiv都是传递关系： - comp（a，b）&& comp（b，c）意味着comp（a，c） - equiv（a，b）&& equiv（b，c）意味着equiv（a，c）

该映射在生成其数据结构并遍历其时使用比较函数，因此如果您的函数出现错误，则任何事情都可能发生。

- M.M

---

那不是一个排序函数。排序就是排序，比较就是比较。a < b并没有对任何东西进行排序，它只是告诉我们a是否小于b。 - luk32

如果要比较的元素数量变得更多，那么比较会变得更加复杂吗？ - tejas

@tejashs 是的，没错。这也是 std::tie 如此酷炫的原因之一。 - juanchopanza

@tejashs：是的，只需使用Matt的解决方案即可。 - MSalters

Answer 2

出于好奇，我在VS2010中尝试了这段代码。它无法编译。

bool operator<(const a &o) { return !(c==o.c && d==o.d); }

错误如下。

错误 C2678：二进制'<'：没有找到接受左操作数类型为 'const StdMapTest::Exec::a' 的运算符（或者没有可接受的转换）

bool operator<(const a &o) const { return !(c==o.c && d==o.d); }

上述代码可以编译通过，但会抛出一个断言:

表达式: 无效的运算符<

最后我尝试了这个方法。

    bool operator<(const a &o) const { return (c == o.c) ? d < o.d : c < o.c; }

编译并且似乎可以正确运行。

我认为可以说，一个足够好的编译器会使这个问题变得不必要。我相信VS2010不是唯一可以执行此类诊断的编译器。

- david.pfx

---

你的第一个错误表明你的代码是通过const引用使用map的（而OP的代码没有这样做）。 - M.M