c++ - std::map operator[] 的一致性

Question

我正在尝试解决我的代码中的一个错误，似乎我无法真正理解标准中对 std::map::operator[] 的要求，或者至少在 STL 中存在一些问题我的编译器附带的(VS2013，仍在尝试不同的工具集)。

我可能误用的 std::map 被定义为提供比较类型作为其第三个模板参数，这使得我使用的一些关键对象与其他一些对象等效。至于我对标准 (23.2.4.2) 中给出的等价定义的理解:a 和 b 是等价的，如果:!(a<b)和 !(b<a) .

我面临的问题是，根据插入顺序，有时它还会插入具有等效项的键。

这是我最终得到的最小示例:

#include <map>
#include <cassert>

struct Foo {
  int x;
  char c;
};

struct FooLess {
  bool equal_c( const Foo& f1, const Foo& f2) const {
    return f1.c == f2.c;
  }

  bool operator() (const Foo& f1, const Foo& f2) const {
    return !equal_c(f1, f2) && f1.x < f2.x;
  }
};

using namespace std;

int main(int , char* [])
{
  FooLess lt;
  assert( !lt( Foo {1, 'a'}, Foo{3, 'a'}) );
  assert( !lt( Foo {3, 'a'}, Foo{1, 'a'}) );

  map<Foo, string, FooLess> m;
    
  m[Foo{ 2, 'b'}] = "Foo(b)"; 
  m[Foo{ 3, 'a'}] = "Foo(A)"; 
  m[Foo{ 4, 'c'}] = "Foo(c)";
  
  // does not hold! 
  assert ((m[Foo{1, 'a'}] == "Foo(A)") );

  m[Foo{ 1, 'a'}] = "Foo(a)"; 
  
  // does not hold!
  assert(m.size() == 3); 
    return 0;
}

至于我对标准的解读，断言应该成立。

23.4.4.3 map element access [map.access]T& operator[](const key_type& x);

1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

2 Requires: key_type shall be CopyConstructible and mapped_type shall be DefaultConstructible.

3 Returns: A reference to the mapped_type corresponding to x in *this.

4 Complexity: logarithmic.

为什么我错了？我是吗？

Answer 1

问题是 FooLess 没有描述严格的弱排序，而是偏序。

参见 C++ named requirements: Compare了解详情。

举个例子:

Foo a {1, 'a'};
Foo b {2, 'b'};
Foo c {1, 'c'};
FooLess comp;
assert(comp(a, b) && comp(b, c)); // Should imply comp(a, c)
assert(!comp(a, c));              // But doesn't due to only partial ordering

只要映射中或搜索到的所有键都具有唯一的 .c，您的比较器就可以工作。