W jaki sposób jest wdrażana funkcja std :: map, aby wymagać, aby jej typ klucza był porównywalny?

Question

To moja implementacja klasy 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; 
} 

Ten kod testowy:

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

Jeśli usunąć definicję operatora < od klasy Box, kompilator będzie narzekać (błąd) jeśli próbuję wstawić obiekt Box do std :: map.

Mam pewne doświadczenie z Javą i wiem, że w podobnych przypadkach muszę pozwolić, aby Box implement Comarable. Kompilator Java sprawdzi tę umowę podczas kompilacji, ponieważ Map w Javie wymaga, aby jej typ klucza był zgodny z porównywalne.

I jeśli chcemy zdefiniować własny typ mapy w Javie, po prostu trzeba napisać:

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

Więc moje pytanie brzmi, czy chcę, aby zaimplementować własny typ mapy (powiedzmy, MyMap) w C++, jak zdefiniować MyMap, aby kompilator wiedział podczas kompilacji, że "MojaMapa wymaga, aby jej typ klucza miał swoją własną przeciążoną definicję operatora <"?

Answer 1

Krótko mówiąc, nie musisz robić nic: jak napisać kod, jeśli operator ma.

W przeciwieństwie do generycznych Java, mechanizm szablonu C++ może działać bez ograniczeń, ponieważ kompilator nie musi tworzyć żadnego kodu, dopóki wszystkie parametry klasy nie zostaną w pełni określone. Natomiast kompilatory Java muszą w pełni skompilować klasę i wygenerować końcowy kod bajtowy, nie znając typów podłączanych do K i V.

Innymi słowy, kompilator C++ umożliwia wywoływanie dowolnych funkcji i stosowanie dowolnych operatorów w kodzie szablonu. Szablon zostanie skompilowany bez problemu, jeśli klasy, które podajesz, mają odpowiednie funkcje i/lub operatory. Jeśli brakuje funkcji i/lub operatorów przywołanych z szablonu, kompilator wyświetli komunikat o błędzie.

Answer 2

Nie trzeba określać żadnych ograniczeń w typie ogólnym, podobnie jak w Javie. Wystarczy użyć operatora < w klasie szablonowej, aby było to wymagane.

Więc w C++ byś po prostu napisać:

template<typename K, typename V> 

class MyMap { 
.. 

if(a < b) { 

.. 

} 

Co dzieje się tak szybko, jak instancję szablonu, na przykład pisząc MyMap<string, string> kompilator tworzy nową klasę zastępując K i V sznurkiem. Jeśli wpiszesz typ bez operatora <, spowoduje to błąd kompilacji.

Answer 3

Spójrz na http://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; 

Powód kompilator skargi o brakującym '<' -operator jest to, że Porównaj-object std::less<Key> chcą to wszystko. Klucze są "sortowane przy użyciu funkcji porównania", zobacz C++ std::map key sort comparison function?, aby uzyskać więcej informacji o tym, jak zaimplementować własny "Porównaj" obiekt.Zazwyczaj nie trzeba tego robić, ponieważ < -operator jest implmented podstawowych typów już (ints, pływaki itp) i innych typów jest to implemted jako część 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; 
} 

Uwaga: Porównaj -przedmiot jest nie tylko używane do sortowania mapy, ale również określa, czy klucz jest uważany za „istnial w mapie”:

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). 

oraz:

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. 

(zob http://www.cplusplus.com/reference/map/map/) Innym dobrym źródłem informacji jest dokumentacja SGI ich STL realizacji: https://www.sgi.com/tech/stl/Map.html

Ponownie, ponieważ w tych docs wiele słów i trzeba by je czytać bardzo uważnie:

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

tak, (ponieważ czułem, że na palcach onces) można skonstruować map<struct my*, int, my_cmp> gdzie porównać funkcja my_cmp zdecyduje, że 2 wskaźniki typu my nie są równe, allthough mają taką samą wartość:

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

Dane wyjściowe funkcji my_cmp() określają, czy dany klucz (i powiązana z nim wartość) są przechowywane na mapie, czy nie. Bardzo subtelny.

Może interesujący czytać: https://latedev.wordpress.com/2013/08/12/less-than-obvious/ i http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/

Answer 4

Pomyśl o szablonie jako wyrażeniu, które może zostać użyte do wygenerowania kodu, a nie jako sam kod (tak naprawdę to szablony mają swoje nazwy, przed szablonami C++ niektóre osoby nadużywałyby preprocesora do osiągnięcia tego samego celu). Oznacza to, że kiedy piszesz

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

to niemal tak samo jakbyś napisał

#define foo(bar) baz(bar) 

treścią definicji (szablonu lub preprocesora) jest prawie bez znaczenia o ile nie jest to użyte. Tylko wtedy, gdy szablon zostanie wprowadzony/rozszerzona zostanie dyrektywa preprocesora, kompilator sprawdzi, czy wynik wyniku instanciation/expansion jest poprawny.

Jako taki, gdy szablon wykorzystuje określoną funkcję członka lub operatora na jednym z jego argumentów, zadaniem użytkownika jest podanie typu, który może być używany w taki sposób, w przeciwnym razie kompilator dokona podstawienia , spójrz na wynikowy kod, potrząśnij głową i wyślij komunikat o błędzie.