valuelist的应用实践之二: 实现多键值的map
1.1 需求
在应用中需要实现一个多键值的MAP表, 希望达到下面的使用目的:
//键值是三个int类型,根据情况,数量和类型都应该可以变化,保存的值是string
map<int,int,int,string> MultiKeyMap;
MultiKeyMap mymap;
//插入多个值
mymap.add(1,1,2,”112”);
mymap.add(1,1,3,”113”);
mymap.add(1,2,1,”121”);
mymap.add(1,2,2,”122”);
mymap.add(1,3,1,”131”);
//查找一个值:
string value = mymap.find(1,1,2);
//可以根据部分键值查找出多个匹配值
map<int,string> resultMap;
mymap.find(1,2,resultMap);
最后得到的resultMap应该包括<1,”121”>和<2,”122”>两个值.
这里关键问题是键值的数量是变化的,后面根据部分键值进行查找只是一个比较算法而已,有了valuelist的使用经验,第一个感觉就是应该用valuelist来实现它.
1.2 实现技术
1.2.1 首先实现以ValueList为键值的MAP
搬出已有的valuelist的定义:
class null_type{};
template<class T1,class T2> class ValueList
{
public:
typedef T1 first_value_type;
typedef T2 second_value_type;
T1 m_val1;
T2 m_val2;
ValueList(const T1& val1,const T2& val2):m_val1(val1),m_val2(val2){}
};
因为我们需要明确的ValueList的类型来构造一个map,需要定义宏,方便用户进行类型定义,如下:
#define TYPE_VLIST_1(t) ValueList< t,null_type>
#define TYPE_VLIST_2(t1,t2) ValueList<t1,TYPE_VLIST_1(t2) >
#define TYPE_VLIST_3(t1,t2,t3) ValueList<t1,TYPE_VLIST_2(t2,t3) >
…
同样定义生成ValueList的便利函数,在这里,RefHolder的使用就不考虑了.
template<class T1,class T2>
inline ValueList<T1,T2> makeValueList(const T1& val1, const T2& val2)
{
return ValueList<T1,T2>(val1,val2);
}
同样定义宏方便生成ValueList:
#define VLIST_1(x) makeValueList(x,null_type())
#define VLIST_2(x1,x2) makeValueList(x1,VLIST_1(x2))
#define VLIST_3(x1,x2,x3) makeValueList(x1,VLIST_2(x2,x3))
…
因为ValuelList作为键值,就需要我们定义一个ValueList之间的比较算法,作为map内部排序使用,我们实现下面的比较函数:
template<class T1,class T2>
bool operator<(const VauleList<T1,T2>& key1,const VauleList<T1,T2>& key2)
{
//首先比较第一个元素,如果他们不相等,那么最终的比较结果就和这两个元素的大小比较结果相同
if(key1.m_val1 != key2.m_val1) return key1.m_val1 < key2.m_val1;
//如果当前元素相等,递归比较下一个元素
return key1.m_val2 < key2.m_val2;
}
因为ValueList以null_type进行比较，则上面的模板函数最终会进行null_type的比较,因此我们需要如下的比较函数:
bool operator<(null_type,null_type)
{
//两个null_type应该是相等的,所以无条件返回false
return false;
}
有了上面的定义之后,我们就可以实现任意数量键值的map了, 见下面的例子:
typedef std::map<TYPE_VLIST_3(int,int,int),string> > MultiKeyMap;
MultiKeyMap mymap;
mymap[VLIST_3(1,1,1)] = “111”;
mymap[VLIST_3(1,1,2)] = “112”;
mymap[VLIST_3(1,2,1)] = “121”;
mymap[VLIST_3(1,2,2)] = “122”;
mymap[VLIST_3(1,3,1)] = “131;
//上面直接使用VLIST_3来定义键值,仅仅在这个例子中适用,因为这个宏,是根据传入参数的值生成ValueList的,整型常量的类型是int,VLIST_3的返回类型就是ValueList<int,ValueList<int,ValueList<int,null_type>>>, 刚好我们定义的key的类型相同.更一般的方法见下一节的说明.
std::cout << mymap[VLIST_3(1,2,2)] << std::endl;
1.2.2 考虑部分键值的查找支持
map已经有lower_bound,upper_bound, equal_range等方法支持范围查询,能够直接利用就很好了. 这里有个问题,这些方法的查找都是通过map的第三个模板参数定义的大小比较算法来完成的,而且输入参数就是std::map::key_type也就是第一个模板参数,根据这两点需要我们做到:
1. 根据输入的部分键值,生成完整的std::map::key_type类型的值. 要求我们定义的ValueList需要支持缺省构造函数来代替用户未输入的键值,我们在比较的时候怎么区分一个某个键值是外部输入的还是缺省构造的?利用每个类型的缺省函数是无法做到这一点,唯一的办法是每个key值需要有一个标识来指示其值是外部传入的还是缺省构造的, 这比较简单,对每个key值做一层包装即可.
2. 我们需要修改前面键值比较函数的定义,支持输入不同数量的键值的比较. 我们需要明确外界没有输入的键值和内部其他键值比较时,谁大谁小? 根据用户的需求,应该是没有大小之分,也就是说如果用户没有输入任何键值,则它和任意内部键值都相等.
考虑上面两点后的实现:
template<class T1,class T2> class ValueList
{
public:
…//同原来的定义
//增加一个缺省构造函数
ValueList(){};
};
对每个key值的包装类:
template<class T>
struct KeyHolder
{
typedef T value_type;
const bool m_avail; //用于指示m_val是否是外部传入的值,定义为const,只能在创建的时候设置,其他任何时候不得修改
T m_val;
Holder():m_avail (false){}
explicit KeyHolder (const T& v):m_val(v),m_avail(true){}
template<class V> bool operator<(const KeyHolder<V>& rhs) const
{
return m_avail && rhs.m_avail && m_val < rhs.m_val;
}
template<class V> bool operator!=(const KeyHolder<V>& rhs) const
{
return (*this) < rhs || rhs < (*this);
}
};
定义一个便利函数:
template<class T>
Holder<T> ByKey(const T& t)
{
return Holder<T>(t);
}
当然多个key组成的ValueList的类型已经悄然发生变化,我们用下面的宏来定义:
#define TYPE_KVLIST_1(t) ValueList< KeyHolder<t>,null_type>
#define TYPE_KVLIST_2(t1,t2) ValueList< KeyHolder<t1>,TYPE_VLIST_1(t2) >
#define TYPE_KVLIST_3(t1,t2,t3) ValueList< KeyHolder<t2>,TYPE_VLIST_2(t2,t3) >
…
最后根据上面的实现,定义一个生成符合条件的ValueList的宏:
#define KVLIST_1(n) VLIST_1(ByKey(n))
#define KVLIST_2(n1,n2) VLIST_2(ByKey(n1), ByKey(n2))
#define KVLIST_3(n1,n2,n3) VLIST_3(ByKey(n1), ByKey(n2),ByKey(n3))
…
然后修改比较算法:
template<class T1,class T2>
bool operator<(const ValueList<KeyHolder<T1>,T2>& key1,const ValueList<KeyHolder<T1>,T2>& key2)
{
//KeyHolder<T>的具体的比较动作已经满足我们的要求了
if(key1.m_val1 != key2.m_val1) return key1.m_val1 < key2.m_val1;
return key1.m_val2 < key2.m_val2;
}
前面的例子需要重新定义:
typedef MultiKeyMap<TYPE_KVLIST_3(int,int,int),std::string> MyMap;
MultiKeyMap mymap;
mymap[KVLIST_3(1,1,1)] = “111”;
…
在前一节已经说明,前面KVLIST_3的用法是正确的纯属巧合,我们需要更一般的生成指定类型键值的方法, 而且还必须支持部分只输入部分键值,一个比较笨的方法是分别定义下面的函数:
template<class VLIST,class T1>
VLIST key(const T1& v1)
{
return makeValueList (ByHolder<VLIST::first_value_type>(v1), VLIST::second_value_type());
}
template<class VLIST,class T1,class T2>
VLIST key (const T1& v1,const T2& v2)
{
return makeValueList(ByHolder<VLIST::first_value_type>(v1), key <VLIST::second_value_type>(v2));
}
template<class VLIST,class T1,class T2,class T3>
VLIST key (const T1& v1,const T2& v2,const T3& v3)
{
return makeValueList(ByHolder<VLIST::first_value_type>(v1), key <VLIST::second_value_type>(v2,v3));
}
…
有了上面的定义,正确的用法如下:
typedef MultiKeyMap<TYPE_KVLIST_3(int,int,int),std::string> MyMap;
MyMap mymap;
mymap[key< MyMap::key_type>(1,1,1)] = “111”;
mymap[key< MyMap::key_type> (1,1,2)] = “112”;
mymap[key< MyMap::key_type> (1,2,1)] = “121”;
mymap[key< MyMap::key_type> (1,2,2)] = “122”;
mymap[key< MyMap::key_type> (1,2,3)] = “123”;
mymap[key< MyMap::key_type> (1,3,1)] = “131”;
//下面实现部分查找功能:
MyMap::iterator bit = mymap.lower_bound(key<MyMap::key_type>(1,2));
MyMap::iterator eit = mymap.upper_bound(key<MyMap::key_type>(1,2));
//输出查找到的值:
for(MyMap::iterator it = mymap.begin(); it != mymap.end(); ++it)
std::cout << it->second << endl;
上面的结果输出应该是:
121
122
123
到现在为止,我们已经完整实现了一个支持多key值的map. 当然我们借助了重复的KVLIST_xxx, TYPE_KVLIST_xxx, template<…> key(…)这类需要重复定义的函数, 我们可以一次性定义可以支持10个或者更多参数个数的宏和模板函数,相信已经足够了,如果真的不够,请你自己动手吧.
1.2.3 进一步优化
上面的实现中,key值的生成过程比较麻烦,不方便使用. 因为生成key值的过程中一定要知道目前map中的键值类型,有两种办法来解决这个问题,一是我们通过继承或适配的方式定义自己的map类,添加一个生成key值的函数,因为在map类内部是知道map的键值类型的;另一种方式,就是我们定义任意两个ValueList类型之间的转换,这种方法就最好使了.下面详细说明:
1. 实现任意ValueList之间的转换
首先我们必须实现的是一个ValueList之间的隐式转换,隐式转换有两种形式,一种是通过目标类型的构造函数实现,一种是定义被转换类型的用户定义类型的转换操作符,这就需要知道目标类型, 而我们要解决的就是不知道目标类型的情况实现自动转换,因此只能利用前者,构造函数来完成:
template<class T1,class T2>
class ValueList
{
public:
//每个key值都是KeyHolder类型,简单利用KeyHolder的构造函数来完成类型转换即可.然后递归调用其他key的构造,null_type的拷贝构造缺省支持可以不管
template<class V1,class V2>
ValueList(const ValueList<V1,V2>& rhs): m_val1(rhs.m_val1),m_val2(rhs.m_val2){}
//考虑如果传递进来的ValueList长度不足,递归调用的最后就是会出现利用一个null_type来构造一个ValueList的情况,因为我们必须定义下面的构造函数. 如果传入的ValueList长度更长，将会用一个ValueList来构造null_type的情况，编译会报错。我们认为这种情况是合理的，很可能是写错了代码导致。
ValueList(null_type){}
};
实现KeyHolder的构造函数:
template<class T>
struct KeyHolder
{
…
//两个类型必须可以自动转换,否则编译期间报告错误
template<class V>
KeyHolder(const KeyHolder<V>& rhs): m_avail(rhs.m_avail),m_val(rhs.m_val){}
};
最后我们可以完全抛弃KVLIST_xxx宏了,任何时候只需要使用VLIST_xxx宏即可,一切必须的类型转换都在内部悄悄进行.
1.2.4 目前完整的代码和使用举例
class null_type{};
template<class T1,class T2> class ValueList
{
public:
typedef T1 first_value_type;
typedef T2 second_value_type;
T1 m_val1;
T2 m_val2;
ValueList(const T1& val1,const T2& val2):m_val1(val1),m_val2(val2){}
template<class V1,class V2>
ValueList(const ValueList<V1,V2>& rhs): m_val1(rhs.m_val1),m_val2(rhs.m_val2){}
explicit ValueList(null_type){}
ValueList(){};
};
template<class T>
struct KeyHolder
{
typedef T value_type;
const bool m_avail;
T m_val;
KeyHolder(): m_avail(false){}
explicit KeyHolder(const T& v):m_val(v),m_avail(true){}
template<class V>
KeyHolder(const KeyHolder<V>& rhs): m_avail(rhs.m_avail),m_val(rhs.m_val){}
};
template<class T>
KeyHolder<T> ByKey(const T& t)
{
return KeyHolder<T>(t);
}
template<class T1,class T2>
inline ValueList<T1,T2> makeValueList(const T1& val1, const T2& val2)
{
return ValueList<T1,T2>(val1,val2);
}
#define TYPE_KVLIST_1(t) ValueList<KeyHolder<t>,null_type>
#define TYPE_KVLIST_2(t1,t2) ValueList<KeyHolder<t1>,TYPE_KVLIST_1(t2) >
#define TYPE_KVLIST_3(t1,t2,t3) ValueList<KeyHolder<t1>,TYPE_KVLIST_2(t2,t3) >
#define VLIST_1(v1) makeValueList(v1,null_type())
#define VLIST_2(v1,v2) makeValueList((v1),VLIST_1(v2))
#define VLIST_3(v1,v2,v3) makeValueList((v1),VLIST_2(v2,v3))
#define VLIST_4(v1,v2,v3,v4) makeValueList((v1),VLIST_3(v2,v3,v4))
#define VLIST_5(v1,v2,v3,v4,v5) makeValueList((v1),VLIST_4(v2,v3,v4,v5))
#define VLIST_6(v1,v2,v3,v4,v5,v6) makeValueList((v1),VLIST_5(v2,v3,v4,v5,v6))
#define VLIST_7(v1,v2,v3,v4,v5,v6,v7) makeValueList((v1),VLIST_6(v2,v3,v4,v5,v6,v7))
#define VLIST_8(v1,v2,v3,v4,v5,v6,v7,v8) makeValueList((v1),VLIST_7(v2,v3,v4,v5,v6,v7,v8))
#define VLIST_9(v1,v2,v3,v4,v5,v6,v7,v8,v9) makeValueList((v1),VLIST_8(v2,v3,v4,v5,v6,v7,v8,v9))
#define VLIST_10(v1,v2,v3,v4,v5,v6,v7,v8,v9,v10) makeValueList((v1),VLIST_9(v2,v3,v4,v5,v6,v7,v8,v9,v10))
template<class T1,class T2>
bool operator<(const ValueList<KeyHolder<T1>,T2>& key1,const ValueList<KeyHolder<T1>,T2>& key2)
{
//KeyHolder<T>的具体的比较动作已经满足我们的要求了
if(key1.m_val1 != key2.m_val1) return key1.m_val1 < key2.m_val1;
return key1.m_val2 < key2.m_val2;
}
bool operator<(null_type,null_type)
{
return false;
}
//下面的例子说明,key的类型发生了变化:
typedef std::map<TYPE_KVLIST_3(char,long,double),string> MyMap;
MyMap mm;
mm[VLIST_3(1,1,5)]= "115";
mm[VLIST_3(1,3,5)] = "135";
mm[VLIST_3(1,4,5)]="145";
mm[VLIST_3(1,2,5)]="125";
mm[VLIST_3(1,2,4)]="124";
mm[VLIST_3(1,2,3)]= "123";
MyMap::iterator bit = mm.lower_bound(VLIST_2(1,2));
MyMap::iterator eit = mm.upper_bound(VLIST_2(1,2));
for(; bit != eit; ++bit){
cout << bit->second << endl;
}
上面的结果输出应该是:
123
124
125
