如何实现std :: map,以便它可以要求其key_type具有可比性？

Question

这是我对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类的operator <的定义,如果我尝试将一个Box对象插入到std :: map中,编译器会抱怨(错误).

我有一些Java的经验,我知道在类似的情况下我只需要让Box实现Comarable.Java编译器将在编译时检查此契约,因为Java中的Map要求其键类型符合Comparable.

如果我想在Java中定义自己的地图类型,我只需要写:

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

所以我的问题是,如果我想在C++中实现我自己的地图类型(比如说,MyMap),如何定义MyMap,以便编译器在编译时知道"MyMap要求其key_type有自己的operator_"重载定义？

Answer 1

简而言之,您无需做任何事情:编写代码就好像操作员在那里一样.

与Java泛型不同,C++模板机制可以在没有约束的情况下工作,因为在完全指定所有类参数之前,编译器不需要生成任何代码.相比之下,Java编译器必须完全编译该类,并生成最终的字节代码,而不知道您插入的类型K和V.

换句话说,C++编译器允许您调用任何函数并在模板代码中应用所需的任何运算符.如果您提供的类具有相应的函数和/或运算符,则模板将编译没有问题.如果缺少从模板引用的函数和/或运算符,编译器会给出错误消息.

Answer 2

您不需要在泛型类型中指定任何约束,如Java中的可比较.只需在模板化类中使用operator <,就可以满足要求.

所以在C++中你只需写:

template<typename K, typename V>

class MyMap {
..

if(a < b) {

.. 

} 

实例化模板后会发生什么,例如通过编写MyMap<string, string>编译器,通过用字符串替换K和V来创建新类.如果在没有operator <的情况下输入类型,则会产生编译错误.

Answer 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>想要它.键是'使用比较函数Compare'排序的,请参阅C++ std :: map键排序比较函数？有关如何实现"自己的"Compare对象的更多信息.通常你不需要这样做,因为<-operator已经为基本类型(int,float等)实现了,而对于其他类型,它是作为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)

所以,(因为它觉得到我的脚趾onces)就可以构造一个map<struct my*, int, my_cmp>在my_cmp比较函数决定该类型的两个指针my不相等,allthough它们是相同的价值:

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 /