映射键类必须满足哪些要求才能成为有效键？

我想把一个给定类的对象映射到另一个类的对象。但是，我想用作键的类不是我编写的，它是一个简单的 struct，只有几个值。Map 对它的内容进行排序，我想知道它是如何做到的，是否有任意的类可以用作键，或者是否有一组需求(操作符和其他东西)需要定义。

如果是这样，我可以为实现操作符映射使用的类创建一个包装器。我只需要知道我首先需要实现什么，而且没有一个类的引用指定它们。

46968 次浏览
小开

Same as for set: The class must have a strict ordering in the spirit of "less than". Either overload an appropriate operator<, or provide a custom predicate. Any two objects a and b for which !(a<b) && !(b>a) will be considered equal.

The map container will actually keep all the elements in the order provided by that ordering, which is how you can achieve O(log n) lookup and insertion time by key value.

小开

The answer is actually in the reference you link, under the description of the "Compare" template argument.

The only requirement is that Compare (which defaults to less<Key>, which defaults to using operator< to compare keys) must be a "strict weak ordering".

小开

You need to define the operator<, for example like this :

struct A
{
int a;
std::string b;
};


// Simple but wrong as it does not provide the strict weak ordering.
// As A(5,"a") and A(5,"b") would be considered equal using this function.
bool operator<(const A& l, const A& r )
{
return ( l.a < r.a ) && ( l.b < r.b );
}


// Better brute force.
bool operator<(const A& l, const A& r )
{
if ( l.a < r.a )  return true;
if ( l.a > r.a )  return false;


// a are equal, compare b
return ( l.b < r.b );
}


// This can often be seen written as
bool operator<(const A& l, const A& r )
{
// This is fine for a small number of members.
// But I prefer the brute force approach when you start to get lots of members.
return ( l.a < r.a ) ||
(( l.a == r.a) && ( l.b < r.b ));
}
小开
最佳答案

All that is required of the key is that it be copiable and assignable. The ordering within the map is defined by the third argument to the template (and the argument to the constructor, if used). This defaults to std::less<KeyType>, which defaults to the < operator, but there's no requirement to use the defaults. Just write a comparison operator (preferably as a functional object):

struct CmpMyType
{
bool operator()( MyType const& lhs, MyType const& rhs ) const
{
//  ...
}
};

Note that it must define a strict ordering, i.e. if CmpMyType()( a, b ) returns true, then CmpMyType()( b, a ) must return false, and if both return false, the elements are considered equal (members of the same equivalence class).


提交答案