Quais requisitos as classs da chave std :: map devem atender para serem chaves válidas?

Eu quero mapear objects de uma determinada class para objects de outro. A class que eu quero usar como chave, no entanto, não foi escrita por mim e é uma struct simples com alguns valores. O std :: map ordena seu conteúdo, e eu queria saber como ele faz isso, e se qualquer class arbitrária pode ser usada como chave ou se há um conjunto de requisitos (operadores e quais não) que precisam ser definidos.

Nesse caso, eu poderia criar um wrapper para a class que implementa os usos do mapa de operadores. Eu só preciso saber o que preciso implementar primeiro, e nenhuma das referências para a class que encontrei on – line especificá-las.

Tudo o que é exigido da chave é que seja copiável e atribuível. A ordenação dentro do mapa é definida pelo terceiro argumento para o modelo (e o argumento para o construtor, se usado). Esse padrão é std::less , cujo padrão é o operador < , mas não há necessidade de usar os padrões. Basta escrever um operador de comparação (preferencialmente como um object funcional):

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

Observe que ele deve definir uma ordenação estrita, ou seja, se CmpMyType()( a, b ) retornar true, CmpMyType()( b, a ) deve retornar false e, se ambos retornarem false, os elementos serão considerados iguais (membros do grupo mesma class de equivalência).

Você precisa definir o operador < , por exemplo, assim:

 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 )); } 

A resposta está realmente na referência que você vincula, sob a descrição do argumento do modelo “Comparar”.

O único requisito é que o Compare (que usa como padrão less , cujo padrão é usar o operator< para comparar chaves) deve ser um "pedido fraco estrito".

O mesmo que para o set : A class deve ter uma ordem estrita no espírito de “menor que”. Sobrecarregue um operator< apropriado operator< ou forneça um predicado personalizado. Quaisquer dois objects a e b para os quais !(aa) serão considerados iguais.

O contêiner do mapa manterá todos os elementos na ordem fornecida por essa ordenação, que é como você pode obter o tempo de pesquisa e inserção de O (log n) pelo valor da chave.