Inserting objects into a std::map?

[saneman]

I am reading section 23 in the C++ standard and cannot seem to find
where it says that the key_type must be defined for '<' when inserting
into std::map.

It is described in The C++ Programming Language 3th ed so I assume I
just can't find it.


Another thing. When I make:

std::map<Bob, int> m;

And my Bob class does not define '<' operator why does the compiler not
complain in the above declaration of 'm'?

Its first when I insert that the compiler complains about the missing
operator in Bob:

Bob b1(22);
std:air<Bob, int> p_bob2int;
p_bob2int.first = b1; // key.
p_bob2int.second = 23; // mapped type.
m.insert(p_bob2int); // DOES NOT WORK UNLESS Bob IMPLEMENTS <

 

[Paul Brettschneider]

I am reading section 23 in the C++ standard and cannot seem to find
where it says that the key_type must be defined for '<' when inserting
into std::map.

It is described in The C++ Programming Language 3th ed so I assume I
just can't find it.


Another thing. When I make:

std::map<Bob, int> m;

And my Bob class does not define '<' operator why does the compiler not
complain in the above declaration of 'm'?

Its first when I insert that the compiler complains about the missing
operator in Bob:

It's the way templates work: functions/methods are only instantiated when
you use them. Since Key:perator<() is not needed for constructing an
empty map, the compiler doesn't complain.

This will probably change with the C++0x contracts-feature.

 

[red floyd]

I am reading section 23 in the C++ standard and cannot seem to find
where it says that the key_type must be defined for '<' when inserting
into std::map.

It is described in The C++ Programming Language 3th ed so I assume I
just can't find it.


Another thing. When I make:

std::map<Bob, int> m;

And my Bob class does not define '<' operator why does the compiler not
complain in the above declaration of 'm'?

It's called SFNIAE (Substitution Failure Is Not An Error). Until the
problematic code is instantiated (by the insert call below), there isn't
a problem.

Note that you don't have to define '<', you *could* specialize
std::less<>, or you could create a separate functor/function for
comparison, and use that as the third template argument to std::map.

 

[Ian Collins]

I am reading section 23 in the C++ standard and cannot seem to find
where it says that the key_type must be defined for '<' when inserting
into std::map.

That's because it doesn't have to.

std::map has four template arguments, the third is the comparison, which
defaults to std::less. By definition, std::less requires operator <, so
that's where the requirement for a map key originates. You are free to
provide your own comparison object which does not require an operator <.

Another thing. When I make:

std::map<Bob, int> m;

And my Bob class does not define '<' operator why does the compiler not
complain in the above declaration of 'm'?

Because the declaration does not insert anything. The missing operator
is only discovered when the insert method is instantiated.

 

[saneman]

That's because it doesn't have to.

std::map has four template arguments, the third is the comparison, which
defaults to std::less. By definition, std::less requires operator <, so
that's where the requirement for a map key originates. You are free to
provide your own comparison object which does not require an operator <.

Assuming that std::map is based on some kind of balanced tree structure
it wouldn't make much sense if no ordering based on key_type was
supplied (<, >, < 5 etc).

I realize that the dependency comes from the comparator but since the
comparator is based on the key_type some kind of ordering operator still
needs to be valid for the key_type.

So it would in my opinion make sense if the standard says that the
key_type needs to be valid for the comparator used. Or is this to
obvious to mention?

Because the declaration does not insert anything. The missing operator
is only discovered when the insert method is instantiated.

Will something like this be caught before instantiation with concepts in
the new standard?

 

[Ian Collins]

Assuming that std::map is based on some kind of balanced tree structure
it wouldn't make much sense if no ordering based on key_type was
supplied (<, >, < 5 etc).

I realize that the dependency comes from the comparator but since the
comparator is based on the key_type some kind of ordering operator still
needs to be valid for the key_type.

Did you read what I said? You are free to provide your own comparison
object which does not require an operator <. That's the way maps work.
Say you had a map of pointers and wanted to sort based on the objects
pointed to. In that case you would provide a comparison object.

So it would in my opinion make sense if the standard says that the
key_type needs to be valid for the comparator used. Or is this to
obvious to mention?

NO, because it does not!

 

[saneman]

Did you read what I said? You are free to provide your own comparison
object which does not require an operator <. That's the way maps work.
Say you had a map of pointers and wanted to sort based on the objects
pointed to. In that case you would provide a comparison object.

NO, because it does not!

I don't understand. Does std::map not require that the comparison object
implement a boolean operator () ? In the below example I have made a
comparison object independent of the key_type:


// Dummy comparator.

class myCmp {
public:

myCmp() {}
bool operator()() const {
return 0;
}
};


// Testing with myCmp
std::map<int, std::string, myCmp> m;
std:air<int, std::string> p;
p.first = 22; // key.
p.second = "33"; // key.
m.insert(p);

And it gives the error:

error: no match for call to ‘(myCmp) (const int&, const int&)’
bob.cpp:42: note: candidates are: bool myCmp:perator()() const


I read the first error line as it tries to call a function operator on
the two key_types, which I intensionally have omitted in the operator in
'myCmp'



Here is what the standard says:
"This comparison object may be a pointer to function or an object of a
type with an appropriate function call operator."

If I instead do:

template <typename T>
class myCmp {
public:

myCmp() {}

bool operator()(const T& x, const T& y) const {
return 0;
}
};

and declare the map with:

std::map<int, std::string, myCmp<int> > m;

it works.

 

[Ian Collins]

I don't understand. Does std::map not require that the comparison object
implement a boolean operator () ? In the below example I have made a
comparison object independent of the key_type:

I think I misinterpreted your post. Yes the comparison object is
required to implement a boolean operator().

If I instead do:

template <typename T>
class myCmp {
public:

myCmp() {}

bool operator()(const T& x, const T& y) const {
return 0;
}
};

and declare the map with:

std::map<int, std::string, myCmp<int> > m;

it works.

As it should - you need two objects to compare!

 

[saneman]

I think I misinterpreted your post. Yes the comparison object is
required to implement a boolean operator().

And further it needs two arguments which must be of type key_type right?

 

[Ian Collins]

And further it needs two arguments which must be of type key_type right?

How else could it compare them?

 

[James Kanze]

It's very indirect. The requirements for an associative
container specify the requirements of a Compare type, which
defines the ordering, and the requirements are that it can be
called with two key_type, will return a bool, and that if that
bool is interpreted as meaning that the first object is strictly
ordered before the second, then the type establishes the
necessary ordering relationship. There is no requirement for
the < operator (and many of my keys for sets don't support it).

In the specifications for std::map, the Compare type is the
third template parameter, and defaults to std::less<key_type>.
And std::less requires a < operator, unless explicitly
specialized otherwise.

The only time you need a < operator is thus if you use the
default third parameter and haven't explicitly specialized
std::less for the type.

It's the way templates work: functions/methods are only
instantiated when you use them. Since Key:perator<() is not
needed for constructing an empty map, the compiler doesn't
complain.

Or it does (g++, for example). The current standard says it's
undefined behavior, so anything the implementation does is
legal.

This will probably change with the C++0x contracts-feature.

I think the word you're looking for is concepts. And yes, the
goal is to require errors in cases which are now undefined
behavior.

 

[James Kanze]

It's called SFNIAE (Substitution Failure Is Not An Error).

No it's not. It's called undefined behavior. SFNIAE is
something else entirely (and only concerns function templates,
since it takes place in template argument deduction).

Until the problematic code is instantiated (by the insert call
below), there isn't a problem.

Just because the compiler doesn't complain doesn't mean that
there's no problem, or that the code is correct. Undefined
behavior is undefined behavior, and unless your implementation
explicitly defines it, it is an error.

 

[James Kanze]

Assuming that std::map is based on some kind of balanced tree
structure it wouldn't make much sense if no ordering based on
key_type was supplied (<, >, < 5 etc).

I realize that the dependency comes from the comparator
but since the comparator is based on the key_type some
kind of ordering operator still needs to be valid for the
key_type. So it would in my opinion make sense if the
standard says that the key_type needs to be valid for the
comparator used. Or is this to obvious to mention?

It is mentioned. §23.1.2/2 (in C++98) says that "Each
associative container is parameterized on Key and an ordering
relation Compare that induces a strict weak ordering (25.3) on
elements of Key." And §25.3/4 describes the requirements on
this ordering fairly extensively:

The term strict refers to the requirement of an
irreflexive relation (!comp(x, x) for all x), and the
term weak to requirements that are not as strong as
those for a total ordering, but stronger than those for
a partial ordering. If we define equiv(a, b) as
!comp(a, b) && !comp(b, a ), then the requirements are
that comp and equive both be transitive relations:

-- comp(a, b) && comp(b, c) implies comp(a, c)

-- equiv(a, b) && equiv(b, c) implies equiv(a, c)

(Followed immediately by a note concerning the induced
relation.)

There is, of course, no requirement that any particular
operator be overloaded. You provide the comparator, and you
can call it what you want. The requirement is that it
establishes the required ordering relationship. (Most of my
maps use std::string as a key, but I don't think any of my
sets have ever used operator< as the ordering relationship.
And it's not uncommon to have several different sets of the
same type, ordered by different critieria.)

Will something like this be caught before instantiation
with concepts in the new standard?

How can you determine that an instantiation parameter is
illegal before instantiation?

Even today, some compilers (e.g. g++) complain if you
instantiate a map with a type that that doesn't support <,
and you haven't provided either an explicit comparator or a
specialization of std::less. I believe that this will be
required in the next version of the standard; i.e. instead
of undefined behavior, a compiler error will be required.
But note that all that can be checked is that the syntax
requirements are met. Most of the problems I've seen with
associative containers are due to the ordering operator not
meeting the requirements for a strict weak ordering.

(The classic error is something like:

struct Toto
{
int a ;
int b ;
bool operator<( Toto const& other ) const
{
return a < other.a && b < other.b ;
}
} ;

And I'm pretty sure that concept checking will not detect
this error---it will remain undefined behavior.)

 

[Paul Brettschneider]

I think the word you're looking for is concepts. And yes, the
goal is to require errors in cases which are now undefined
behavior.

Yes, yes, concepts. At least I got the first three letters right.

 

[Paul Brettschneider]

It is mentioned. §23.1.2/2 (in C++98) says that "Each
associative container is parameterized on Key and an ordering
relation Compare that induces a strict weak ordering (25.3) on
elements of Key." And §25.3/4 describes the requirements on
this ordering fairly extensively:

The term strict refers to the requirement of an
irreflexive relation (!comp(x, x) for all x), and the
term weak to requirements that are not as strong as
those for a total ordering, but stronger than those for
a partial ordering. If we define equiv(a, b) as
!comp(a, b) && !comp(b, a ), then the requirements are
that comp and equive both be transitive relations:

-- comp(a, b) && comp(b, c) implies comp(a, c)

-- equiv(a, b) && equiv(b, c) implies equiv(a, c)

(Followed immediately by a note concerning the induced
relation.)

There is, of course, no requirement that any particular
operator be overloaded. You provide the comparator, and you
can call it what you want. The requirement is that it
establishes the required ordering relationship. (Most of my
maps use std::string as a key, but I don't think any of my
sets have ever used operator< as the ordering relationship.
And it's not uncommon to have several different sets of the
same type, ordered by different critieria.)



How can you determine that an instantiation parameter is
illegal before instantiation?

Even today, some compilers (e.g. g++) complain if you
instantiate a map with a type that that doesn't support <,
and you haven't provided either an explicit comparator or a
specialization of std::less. I believe that this will be
required in the next version of the standard; i.e. instead
of undefined behavior, a compiler error will be required.
But note that all that can be checked is that the syntax
requirements are met. Most of the problems I've seen with
associative containers are due to the ordering operator not
meeting the requirements for a strict weak ordering.

(The classic error is something like:

struct Toto
{
int a ;
int b ;
bool operator<( Toto const& other ) const
{
return a < other.a && b < other.b ;
}
} ;

And I'm pretty sure that concept checking will not detect
this error---it will remain undefined behavior.)

If it could - wouldn't that be solving the halting problem?

 

[James Kanze]

James Kanze wrote:

[...]

If it could - wouldn't that be solving the halting problem?

I rather suspect so. What I am sure of is that but I wouldn't
know how to implement it (and I'm not totally without knowledge
in the domain).

 

[Paul Brettschneider]

saneman wrote: [...]

Another thing. When I make:
std::map<Bob, int> m;
And my Bob class does not define '<' operator why does the
compiler not complain in the above declaration of 'm'?
Its first when I insert that the compiler complains about
the missing operator in Bob:

It's the way templates work: functions/methods are only
instantiated when you use them. Since Key:perator<() is not
needed for constructing an empty map, the compiler doesn't
complain.

Or it does (g++, for example). The current standard says it's
undefined behavior, so anything the implementation does is
legal.

I cannot reproduce this on g++:

#include <map>

class A {
int x;
public:
A(int x_) : x(x_) { };
};

int main()
{
std::map<A, int> x; // Compiles fine

A a(123);
// x[a] = 456; // <-- This fails
}

compiles on my g++4.2 and g++4.1 versions as long as the last line stays
commented out. I'd find it curious if the std::map construction would
instantiate a method depending on the Compare argument.

 

[James Kanze]

saneman wrote: [...]
Another thing. When I make:
std::map<Bob, int> m;
And my Bob class does not define '<' operator why does
the compiler not complain in the above declaration of
'm'?
Its first when I insert that the compiler complains about
the missing operator in Bob:
It's the way templates work: functions/methods are only
instantiated when you use them. Since Key:perator<() is not
needed for constructing an empty map, the compiler doesn't
complain.

Or it does (g++, for example). The current standard says it's
undefined behavior, so anything the implementation does is
legal.

I cannot reproduce this on g++:

Are you using the normal options for standard conformant code?
I get:

Gabi (10): cat nocmp.cc
#include <map>

class A {
} ;

int
main()
{
std::map< A, int > m ;
}
Gabi (11): g++ --version
g++ (GCC) 4.2.1 (SUSE Linux)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.

Gabi (12): g++ -std=c++98 -ffor-scope -fno-gnu-keywords -foperator-
names -pipe -Wall -W -Wno-sign-compare -Wno-deprecated -Wno-non-
virtual-dtor -Wpointer-arith -Wno-unused -Wno-switch -Wno-missing-
field-initializers -ggdb3 -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG -
D_GLIBCXX_DEBUG_PEDANTIC nocmp.cc
/usr/include/c++/4.2.1/bits/stl_function.h: In member function
'bool std::less<_Tp>:perator()(const _Tp&, const _Tp&) const [with
_Tp = A]':
/usr/include/c++/4.2.1/bits/boost_concept_check.h:359:
instantiated from 'void __gnu_cxx::_BinaryFunctionConcept<_Func,
_Return, _First, _Second>::__constraints() [with _Func = std::less<A>,
_Return = bool, _First = A, _Second = A]'
/usr/include/c++/4.2.1/bits/stl_map.h:106: instantiated from
'std::__norm::map<A, int, std::less<A>, std::allocator<std:air<const
A, int> > >'
/usr/include/c++/4.2.1/debug/map.h:51: instantiated from
'std::__debug::map<A, int, std::less<A>,
std::allocator<std:air<const A, int> > >'
nocmp.cc:9: instantiated from here
/usr/include/c++/4.2.1/bits/stl_function.h:227: error: no match
for 'operator<' in '__x < __y'


This is under Linux, here, but I got the same thing under
Solaris on a Sparc at work.

Obviously, you've got to demand error checking, or you won't get
it. Like every other compiler I've used, the default options
are never what you want.

 

[Paul Brettschneider]

On Mar 27, 10:04 pm, Paul Brettschneider
saneman wrote:
[...]
Another thing. When I make:
std::map<Bob, int> m;
And my Bob class does not define '<' operator why does
the compiler not complain in the above declaration of
'm'?
Its first when I insert that the compiler complains about
the missing operator in Bob:
It's the way templates work: functions/methods are only
instantiated when you use them. Since Key:perator<() is not
needed for constructing an empty map, the compiler doesn't
complain.

Or it does (g++, for example). The current standard says it's
undefined behavior, so anything the implementation does is
legal.

I cannot reproduce this on g++:

Are you using the normal options for standard conformant code?
I get:

Gabi (10): cat nocmp.cc
#include <map>

class A {
} ;

int
main()
{
std::map< A, int > m ;
}
Gabi (11): g++ --version
g++ (GCC) 4.2.1 (SUSE Linux)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.

Gabi (12): g++ -std=c++98 -ffor-scope -fno-gnu-keywords -foperator-
names -pipe -Wall -W -Wno-sign-compare -Wno-deprecated -Wno-non-
virtual-dtor -Wpointer-arith -Wno-unused -Wno-switch -Wno-missing-
field-initializers -ggdb3 -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG -
D_GLIBCXX_DEBUG_PEDANTIC nocmp.cc

-D_GLIBCXX_CONCEPT_CHECKS did it, thanks!