Re: Inserting objects into a std::map?
On Mar 27, 10:28 pm, saneman <asdf...@asd.com> wrote:
Ian Collins wrote:
saneman wrote:
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 <.
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. =A723.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 =A725.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.)
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.
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.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34