什么要求必须std :: map键类符合是有效的密钥?

我想将给定类的对象映射到另一个对象。 然而,我想用作键的类不是由我写的,而是一个具有几个值的简单struct 。 std :: map命令它的内容,我想知道它是如何做到的,以及是否有任意的类可以用作关键字,或者是否有需要定义的一组需求(运算符和哪些不需要)。

如果是这样,我可以为实现操作符映射用途的类创build一个包装器。 我只需要知道我需要实现的第一个,没有我在线上find的类的引用指定它们。

所有关键的要求是它是可复制和可分配的。 映射中的sorting由模板的第三个参数(以及构造函数的参数,如果使用的话)定义。 默认std::less<KeyType> ,默认为<运算符,但不要求使用默认值。 只要写一个比较运算符(最好是一个function对象):

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

请注意,它必须定义一个严格的顺序,即如果CmpMyType()( a, b )返回true,那么CmpMyType()( b, a )必须返回false,如果两者都返回false,则认为这些元素是相等的相同的等价类)。

您需要定义运算符<,例如像这样:

 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 ( la < ra ) && ( lb < rb ); } // Better brute force. bool operator<(const A& l, const A& r ) { if ( la < ra ) return true; if ( la > ra ) return false; // Otherwise a are equal if ( lb < rb ) return true; if ( lb > rb ) return false; // Otherwise both are equal return false; } // 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 ( la < ra ) || (( la == ra) && ( lb < rb )); } 

答案实际上是在你的链接的引用下,在“比较”模板参数的描述下。

唯一的要求是Compare (默认为less<Key> ,默认使用operator<来比较键)必须是“严格的弱sorting”。

set相同:class级必须有“小于”的精神。 重载适当的operator<或者提供一个自定义的谓词。 其中!(a<b) && !(b>a)任何两个对象ab将被视为相等。

地图容器实际上将按照该顺序提供的顺序保留所有元素,这就是如何通过键值实现O(log n)查找和插入时间。