std :: карта соответствия оператора []

Question

Я пытаюсь устранить ошибку в своем коде, и мне кажется, что я не могу понять требования к std :: map :: operator [] в стандарте или что-то не работает по крайней мере в STL это идет с моим компилятором (VS2013, все еще в процессе, чтобы попробовать различные наборы инструментов)

std :: map, которую я, вероятно, неправильно использую, определяется как тип Compare в качестве третьего параметра шаблона, который делает некоторые из ключевых объектов, которые я использую, эквивалентными другим. Что касается моего понимания относительно определения эквивалентности, данного в стандарте (23.2.4.2): a и b эквивалентны, если: !(a<b) AND !(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.access] T & operator [] (const key_type & x);

1 Эффекты: если на карте нет ключа, эквивалентного x, вставляется значение value_type (x, T ()) в карту.

2 Требуется: key_type должен быть CopyConstructible, а mapped_type должен быть DefaultConstructible.

3 Возвращает: ссылка на mapped_type, соответствующий x в * this.

4 Сложность: логарифмическая.

Почему я не прав? Я?

Answer 1

Проблема в том, что FooLess не описывает строго слабое упорядочение, но частичное упорядочение.

См. Именованные требования C ++: Сравните для деталей.

В качестве примера:

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 s.