example - map c++ ejemplo

¿Cómo se implementa std:: map para que pueda requerir que su key_type sea comparable?

Question

Esta es mi implementación de la clase Box:

class Box {
    friend ostream& operator<<(ostream &os, const Box &b);
    friend bool operator<(const Box &left, const Box &right);
public:
    Box(int i, double d);
    ~Box();
private:
    int i;
    double d;
};

Box::Box(int _i, double _d):i(_i), d(_d) {}

Box::~Box() {}

bool operator<(const Box &left, const Box &right)
{
    return (left.i < right.i);
}

ostream& operator<<(ostream &os, const Box &b)
{
    os << b.d;
    return os;
}

Este es el código de prueba:

int main()
{
    Box b1(3,2), b2(2,1), b3(0, 9);
    map<Box, int> bmap;
    bmap.insert(pair<Box,int>(b1, 10));
    bmap.insert(pair<Box,int>(b2, 10));
    bmap.insert(pair<Box,int>(b3, 10));
    for (map<Box,int>::iterator iter = bmap.begin(); iter != bmap.end(); ++iter)
    {
        cout << iter->first << " ";
    }
    cout << endl;
    return 0;
}

Si elimino la definición de operador <en la clase Box, el compilador se quejará (un error) si intento insertar un objeto Box en std :: map.

Tengo algo de experiencia con Java y sé que en casos similares solo tengo que dejar que Box implemente Comarable. Y el compilador de Java verificará este contrato en el momento de la compilación, ya que Map en Java requiere que su tipo de clave sea conforme a Comparable.

Y si quiero definir mi propio tipo de mapa en Java, solo necesito escribir:

public class MyMap<K extends Comparable<K>, V>

Entonces, mi pregunta es, si quiero implementar mi propio tipo de mapa (por ejemplo, MyMap) en C ++, ¿cómo definir MyMap para que el compilador sepa en tiempo de compilación que "MyMap requiere que su key_type tenga su propia definición de operador sobrecargado <"?

Answer 1

En pocas palabras, no tiene que hacer nada: escriba su código como si el operador estuviera allí.

A diferencia de los genéricos de Java, el mecanismo de la plantilla de C ++ puede funcionar sin restricciones, ya que no se requiere que el compilador produzca ningún código hasta que todos los parámetros de clase estén completamente especificados. En contraste, los compiladores de Java deben compilar completamente la clase y producir el código de byte final sin saber los tipos que se conectan para K y V

En otras palabras, el compilador de C ++ le permite llamar a cualquier función y aplicar cualquier operador que desee en su código de plantilla. La plantilla se compilará sin problemas si las clases que proporciona tienen las funciones y / u operadores correspondientes. Si faltan las funciones y / o los operadores a los que se hace referencia en la plantilla, el compilador le da un mensaje de error.

Answer 2

Mira en.cppreference.com/w/cpp/container/map :

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

La razón por la que su compilador se queja de un operador ''<'' faltante es que el objeto Compare- std::less<Key> quiere. Las teclas están ''ordenadas usando la función de comparación Comparar'', vea C ++ std :: ¿función de comparación de clasificación de teclas de mapa? para obtener más información sobre cómo implementar su ''propio'' objeto de comparación. Por lo general, no necesitará hacer esto porque el < -operador ya está implementado para los tipos fundamentales (ints, flotadores, etc.) y para otros tipos, está implementado como parte de la STL:

https://sourceforge.net/p/stlport/code/ci/master/tree/stlport/stl/_string_operators.h#l347

template <class _CharT, class _Traits, class _Alloc>
inline bool _STLP_CALL
operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
      const basic_string<_CharT,_Traits,_Alloc>& __y) {
return basic_string<_CharT,_Traits,_Alloc> ::_M_compare(__x.begin(), __x.end(),
                                                      __y.begin(), __y.end()) < 0;
}

Nota: el objeto de comparación no solo se usa para ordenar los mapas, sino que también determina si una clave se considera ''existente en el mapa'':

Internally, the elements in a map are always sorted by its
key following a specific strict weak ordering criterion indicated
by its internal comparison object (of type Compare).

Y:

Compare:

A binary predicate that takes two element keys as arguments and returns
a bool. The expression comp(a,b), where comp is an object of this type
and a and b are key values, shall return true if a is considered to go 
before b in the strict weak ordering the function defines.
The map object uses this expression to determine both the order the
elements follow in the container and whether two element keys are equivalent
(by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)).

No two elements in a map container can have equivalent keys.

This can be a function pointer or a function object (see constructor for an 
example). This defaults to `std::less<Key>`, which returns the same as applying the 
less-than operator (a<b).

Aliased as member type map::key_compare.

(consulte http://www.cplusplus.com/reference/map/map/ ) Otra buena fuente de información es la documentación de SGI de su implementación de STL: https://www.sgi.com/tech/stl/Map.html

Nuevamente, ya que en estos documentos hay muchas palabras y necesitarías leerlas muy cuidadosamente:

they are equivalent if !comp(a,b) && !comp(b,a)

Por lo tanto, (como se notó en mis dedos de los pies), puedes construir un map<struct my*, int, my_cmp> donde la my_cmp comparación my_cmp decide que 2 punteros de tipo my NO son iguales, aunque tienen el mismo valor:

struct my* a = &my_a;
struct my* b = a;

La salida de my_cmp () decide si una clave dada (y el valor asociado) se almacenan en el mapa o no. Muy sutil.

Quizás sea interesante de leer: https://latedev.wordpress.com/2013/08/12/less-than-obvious/ y http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/

Answer 3

No es necesario que especifique ninguna restricción en su tipo genérico, como comparable en Java. Con solo usar el operador <en su clase de plantilla, hace que este sea un requisito.

Así que en C ++ simplemente escribirías:

template<typename K, typename V>

class MyMap {
..

if(a < b) {

.. 

} 

¿Qué sucede tan pronto como crea una instancia de una plantilla, por ejemplo, al escribir MyMap<string, string> el compilador crea una nueva clase sustituyendo K y V por cadena? Si pones un tipo sin operador <, esto creará un error de compilación.

Answer 4

Piense en una plantilla como una expresión que se puede usar para generar código, no como código en sí mismo (así es como las plantillas obtuvieron sus nombres, antes de las plantillas en C ++, algunas personas abusarían del preprocesador para lograr el mismo objetivo). Es decir, cuando escribes.

template<class T> void foo(const T& bar) {
    baz(bar);
}

Es casi lo mismo que si hubieras escrito

#define foo(bar) baz(bar)

El contenido de la definición (plantilla o preprocesador) es bastante irrelevante siempre y cuando no se use . Solo cuando la plantilla está instanciada / la directiva del preprocesador se expande, el compilador verificará si el resultado de la instanciación / expansión es válido.

Como tal, cuando una plantilla usa una determinada función u operador miembro en uno de sus argumentos, es tarea del usuario proporcionar un tipo que se pueda usar de tal manera, de lo contrario el compilador hará la sustitución, mire la código resultante, sacude la cabeza y lanza un mensaje de error.