Does std::map require the comparator's operator() to be const?

Question

The following code fails to compile with XCode 4.5's clang++ when using libc++ on OS X 10.8:

#include <map>
#include <string>

class Foo {
public:
  explicit Foo(int val_) : val(val_) {}
  int val;
};

struct FooComparator {
  bool operator()(const Foo& left, const Foo& right) {
    return left.val < right.val;
  }
};

int main(int argc, char* argv[]) {

  std::map<Foo, std::string, FooComparator> m;

  Foo f(4);
  m[f] = std::string("four");

  return 0;
}

The error:

broken.cpp:11:8: note: candidate function not viable: 'this' argument has type 'const FooComparator', but method is not marked const bool operator()(const Foo& left, const Foo& right) {

If I turn off libc++ and build with libstdc++ then all is well. Obviously, I can work around this by making FooComparator::operator() const, but I'd like to understand whether this is a problem with libc++ being too strict, or whether the standard (both C++03 and C++11) does in fact require that the comparator's operator() be const (in which case the fact that it works with libstdc++ is a happy accident).

Answer 1

Well, yes: The comparator is a subobject of the map itself, one way or another (maybe a member; usually a base class of some inner implementation class). If you have a constant reference to the map, the comparator still needs to be usable for lookup, so the operator needs to be const.