首页 > 代码库 > 如何在STL的map中使用结构体作为键值

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

 

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

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的定义:

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。举例来说,现在有一个结构体:

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。

  修改后的结构体代码如下:

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的第三个模板参数。不过这样做显然不如上边这种办法简单,这里也不具体叙述了。

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