Question

如何在STL的map中使用结构体作为键值

Answer 1

　　这里首先给出容器map的原型：

1
2
3
4
5
6
7
8

template <
class Key,
class T,
class Compare = less<Key>,
class Alloc = alloc>
class map{
...
}

　　可以看到模板参数一共有四个，第一个就是Key，即键；第二个就是值；第四个就是空间配置器，默认使用alloc(随STL版本不同而不同)。那么第三个是啥？
　　我们知道，map的底层数据结构，其实是树，更确切的说，是一个RB-tree（红黑树）。RB-tree树在进行插入时，会按照一定的规则把新元素插入特定位置。相应的，进行删除操作时，也会按一定规则修改树的结构。此外，树形结构也是高效率查询的基本保证。但是，插入、删除、查询时都要依赖与节点之间的比较，对于map来说，我们必须提供对Key进行比较的函数或操作符。这也就是第三个模板参数的意义。
　　默认情况下，第三个模板参数使用less<Key>类型，其中less<T>是一个仿函数。下面给出less的定义：

1
2
3
4
5
6
7
8
9

template<class _Ty>
struct less
: public binary_function<_Ty, _Ty, bool>
{ // functor for operator<
bool operator()(const _Ty& _Left, const _Ty& _Right) const
{ // apply operator< to operands
return (_Left < _Right);
}
};

　　如果创建一个less类的对象less_obj，然后使用less_obj(A,B)这样的写法，就相当于调用了less的operator()方法。而最终执行时，会自动获取A与B的类型，并使用此类型的operator<来实现less类的operator()方法。到现在为止，就理清了map中的第三个模板参数的所有问题。
　　接下来的问题就是，如何在map中使用一个结构体作为Key。举例来说，现在有一个结构体：

1
2
3
4
5
6

typedef struct _info_head{
u_int src_ip;
u_int dest_ip;
u_int src_port;
u_int dest_port;
}info_head;

　　如果直接使用info_head这个结构体来填入map中的第一个模板参数的位置，并且不指定第三个模板参数的话，那么就会使用less<info_head>作为map中对键值进行比较的操作符。而通过上述分析，在less<info_head>中最终使用的，是info_head类型的operator<操作符。那么显然的，只给出上边的简单的对结构体的定义，是不够的。因此，要想使用结构体来作为map中的Key，那就必须为此结构体重载并实现operator<操作符。如果没能做到这一点，就会在编译时报错，因为编译器找不到对应的operator<。其中，VS2010下的编译错误代码是：error C2784。
　　修改后的结构体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct _info_head{
u_int src_ip;
u_int dest_ip;
u_int src_port;
u_int dest_port;

bool operator<(const struct _info_head & other) const {
//Must be overloaded as public if this struct is being used as the KEY in map.
if (this->src_ip < other.src_ip) return true;
if (this->dest_ip < other.dest_ip) return true;
if (this->src_port < other.src_port) return true;
if (this->dest_port < other.dest_port) return true;
return false;
}
}info_head;

　　不过这并不是唯一的办法。另外一种方式，就是自己写一个仿函数，实现对info_head类型的比较。然后在info_head作为map中第一个模板参数的时候，填入这个仿函数作为map的第三个模板参数。不过这样做显然不如上边这种办法简单，这里也不具体叙述了。