Type requirements for std::map

Question

Today I created a map, where the value type has no default constructor. I was surprised that I could not use operator[] to insert the elements to this map, but I had to use the insert method.

So, what exactly are requirements for the key and value types for std::map?

Here is short example :

#include <map>

struct A
{
    A(int){}
};

int main()
{
    std::map< int, A > m;
    A a1(2);
    A a2(3);
    A a3(4);
    m[5] = a1;
    m[3] = a2;
    m[2] = a3;
}

I am compiling like this :

[vladimir@sandbox tmp]$ g++ b5.cpp -Wall -Wextra -ansi -pedantic
/usr/lib/gcc/i386-redhat-linux/4.3.0/../../../../include/c++/4.3.0/bits/stl_map.h: In member function ‘_Tp& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const _Key&) [with _Key = int, _Tp = A, _Compare = std::less<int>, _Alloc = std::allocator<std::pair<const int, A> >]’:
b5.cpp:14:   instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.3.0/../../../../include/c++/4.3.0/bits/stl_map.h:419: error: no matching function for call to ‘A::A()’
b5.cpp:5: note: candidates are: A::A(int)
b5.cpp:4: note:                 A::A(const A&)

Answer 1

operator[] does indeed require default-constructibility because the semantics of this method mandate that if the key doesn’t yet exist, an appropriate entry is created. Thus:

map<TKey, TValue> mymap;
TKey foo = …;
TValue& x = mymap[foo];

will create and store a new object TValue() if foo doesn’t exist in the map, and return a reference to it.

Answer 2

This site make a great STL reference: http://www.sgi.com/tech/stl/

Basically, it says that map takes has mandatory 2 type arguments, Key and Data. Data needs to be Assignable, as Daniel said. Key, however, is stated to need to be a type that can be used with the type Compare, i.e. Compare designates a function object whose parameters are of type Key. In this case, the default Compare function object is std::less<T>, which is a Strict Weak Ordering that compares objects of type T using the operator<. Hence, if you do not change the Compare type, i.e. use the default, std::less<T> will be used with type Key, and thus operator< will be used with type Key, and thus Key needs to be comparable with operator<.

Hope that helps! I know it's a bit gratuitous and I don't mean to be condescending, but I just want to make sure it's absolutely clear how to go about reasoning about this.