CODEWITHSUNDEEP
c++c++11
Giuseppe Puoti
Giuseppe Puoti

Reputation: 140

std::map conformance of the operator[]

I'm trying to solve a bug in my code and it seems that either I can't really understand the requirements for std::map::operator[] in the standard or there is something broken at least in the STL that comes with my compiler (VS2013, still in the process to try different toolsets).

The std::map I'm probably misusing is defined providing a Compare type as its third template parameter that makes some of the key objects I use equivalent with some other. As for my understanding respecting the definition of equivalence given in the standard (23.2.4.2): a and b are equivalent if: !(a<b) AND !(b<a).

The problem I'm facing is that, depending on the insertion order, sometime it inserts also keys with an equivalent already there.

Here is the minimal example that I ended up:

#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;
}

As for my reading of the standard the assertions should hold.

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.

Why Am I wrong? Am I?

Upvotes: 1

Views: 112

Answers (1)

Deduplicator
Deduplicator

Reputation: 45664

The problem is that FooLess does not describe a strict weak ordering, but a partial ordering.

See C++ named requirements: Compare for the details.

As an example:

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

Your comparator works as long as all of the keys in the map or searched for have unique .cs.

Upvotes: 4

Related Questions