Why do C ++ STL containers use the "less than" operator and not the "equal equal" operator == as a comparator?
While implementing the comparator operator inside a custom class for, std::map
I came across this question and couldn't see what was being asked.
Apart from the above question, it is also interesting to know briefly how operator<
will work for std::map
.
Origin of the question:
struct Address {
long m_IPv4Address;
bool isTCP;
bool operator< (const Address&) const; // trouble
};
source to share
std::map<K,D>
should be able to sort. The default is 1 std::less<K>
, which for non-pointers is <
1 .
Using the rule that you require your users at least, it synthesizes "equivalence" from <
when it needs it ( !(a<b) && !(b<a)
means a
and are b
equivalent, ie not less than another).
This makes it easier to write classes to use as key components for map
, which seems like a good idea.
There are containers std
that use ==
, for example std::unordered_map
, which uses std::hash
and ==
. Again, they are designed to require the least from their users - you don't need complete ordering for containers unordered_
, just equivalence and good hash
.
As it happens, it is very easy to write <
if you have access to <tuple>
.
struct Address {
long m_IPv4Address;
bool isTCP;
bool operator< (const Address& o) const {
return
std::tie( m_IPv4Address, isTCP )
< std::tie( o.m_IPv4Address, o.isTCP );
}
};
which uses the std::tie
one defined in <tuple>
to create the right one <
for you. std::tie
takes a bunch of data and generates tuple
links that already have a good one <
.
1 For pointers, it uses some comparison that is consistent with <
where the behavior is specified <
, and behaves well when <
not. This really matters for the segmented memory model and other obscure architectures.
source to share
Since it std::map
is an associative sorted container , it needs ordering settings.
The operator ==
would not allow ordering multiple keys
You may be looking for std::unordered_map
which job has a hash table. You can provide your own hash and equality functions:
explicit unordered_map( size_type bucket_count,
const Hash& hash = Hash(),
const KeyEqual& equal = KeyEqual(),
const Allocator& alloc = Allocator() );
source to share
With help <
you can order items. If a < b
, then a
should be placed before b
the collection.
You can also determine if two elements are equivalent: if !(a < b) && !(b < a)
(if neither object is less than the other), they are equivalent.
These two possibilities require everything std::map
. So it just expects the operator to supply its element type <
.
With ==
you can define equality, but you cannot order items. Therefore, it does not meet the requirements std::map
.
source to share