Как реализуется std:: map, поэтому может потребоваться сопоставление ее ключа_type?

Это моя реализация класса 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;
}

Этот тестовый код:

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

Если я удалю определение оператора < в классе Box компилятор будет жаловаться (ошибка), если я попытаюсь вставить объект Box в std:: map.

У меня есть некоторый опыт работы с Java, и я знаю, что в подобных случаях я просто должен позволить Box реализовать Comarable. И компилятор Java проверяет этот контракт во время компиляции, потому что Map в Java требует, чтобы его тип ключа соответствовал Comparable.

И если я хочу определить свой собственный тип карты в Java, мне просто нужно написать:

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

Итак, мой вопрос: если я хочу реализовать свой собственный тип карты (например, MyMap) на С++, как определить MyMap, чтобы компилятор знал во время компиляции, что "MyMap требует, чтобы его key_type имел свое собственное перегруженное определение оператора <?"

Ответы

Ответ 1

Короче говоря, вам не нужно ничего делать: напишите свой код, как если бы оператор был там.

В отличие от генераторов Java, механизм шаблонов С++ может работать без ограничений, поскольку компилятор не должен создавать какой-либо код до тех пор, пока все параметры класса не будут полностью указаны. Напротив, компиляторы Java должны полностью компилировать класс и создавать окончательный байтовый код, не зная типов, которые вы подключаете для K и V.

Другими словами, компилятор С++ позволяет вам вызывать любые функции и применять любые операторы, которые вы хотите в своем шаблоне. Шаблон будет компилироваться без проблем, если классы, которые вы поставляете, имеют соответствующие функции и/или операторы. Если функции и/или операторы, на которые ссылается шаблон, отсутствуют, компилятор выдает сообщение об ошибке.

Ответ 2

Вам не нужно указывать какие-либо ограничения в вашем общем типе, например, сопоставимые в Java. Просто используя оператор < в вашем шаблоном классе, делает это требование.

Итак, на С++ вы просто напишете:

template<typename K, typename V>

class MyMap {
..

if(a < b) {

.. 

}

Что происходит, как только вы создаете шаблон, например, написав MyMap<string, string>, компилятор создает новый класс, заменяя K и V на строку. Если вы поместите тип без оператора <, это создаст ошибку компиляции.

Ответ 3

Посмотрите 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;

Причина, по которой ваш компилятор жалуется на отсутствующий оператор "<", заключается в том, что этот объект Compare-object std::less<Key> хочет этого. Клавиши "сортируются с помощью функции сравнения сравнения", см. С++ std:: map key sort compare function? для получения дополнительной информации о том, как реализовать свое собственное сравнение -объект. Обычно вам не нужно это делать, потому что < -оператор уже внедрен для базовых типов (ints, floats и т.д.), А для других типов он реализуется как часть 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;
}

Примечание. Compare-object используется не только для сортировки карт, но также определяет, считается ли ключ "существующим на карте":

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

и

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.

(см. http://www.cplusplus.com/reference/map/map/). Другим хорошим источником информации является SGI-документация по их реализации STL: https://www.sgi.com/tech/stl/Map.html

Опять же, поскольку в этих документах много слов, и вам нужно будет их очень внимательно прочитать:

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

Итак, (поскольку он чувствовал себя на пальцах ног), вы можете построить map<struct my*, int, my_cmp>, где функция сравнения my_cmp решает, что 2 указателя типа my НЕ равны, хотя они имеют одинаковое значение:

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

Вывод my_cmp() решает, если данный ключ (и связанное с ним значение) сохраняется на карте или нет. Очень тонкий.

Может быть интересно прочитать: https://latedev.wordpress.com/2013/08/12/less-than-obvious/ и http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/

Ответ 4

Подумайте о шаблоне как выражении, которое можно использовать для генерации кода, а не как сам код (на самом деле, как шаблоны получили свои имена, до шаблонов С++ некоторые люди злоупотребляли препроцессором для достижения той же цели). То есть, когда вы пишете

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

это почти так же, как если бы вы написали

#define foo(bar) baz(bar)

Содержимое определения (шаблон или препроцессор) в значительной степени не имеет значения, если оно не используется. Только при расширении шаблона/директива препроцессора расширяется, компилятор проверяет, действителен ли результат инициализации/расширения.

Таким образом, когда шаблон использует определенную функцию-член или оператор для одного из своих аргументов, задача пользователя заключается в предоставлении типа, который может использоваться таким образом, иначе компилятор выполнит замену, посмотрите на полученный код, покачайте головой и выпустите сообщение об ошибке.