S.l.e!ep.￠%

像打了激速一样，以四倍的速度运转，开心的工作
简单、开放、平等的公司文化；尊重个性、自由与个人价值；
posts - 1098, comments - 335, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

排序比较函数：<符号你重载对么了么？

Posted on 2011-10-15 08:00 S.l.e!ep.￠% 阅读(783) 评论(0)  编辑 收藏 引用 所属分类: C++
前段时间整理台历的逻辑数据时考虑到需要去兼容已发布的照片书数据，很多地方做了兼容处理，比如下面这个例子：

      在很多时候，我们常常会使用map储存一些需要经常查询数据结构，而map的key在一开始设计的时候往往不多加思索，很容易就认为它就是个纯ID，比如一个数字，或者一个字符串。当随着产品变得复杂，或者不同数据结构的添加，这个假设往往不堪一击—-比如在网游中的游戏ID竟然被认为是唯一的Key，而实际上如果涉及到服务器合并，这个ID也就不那么唯一了。很显然需要解决这个问题就是扩充原来的Key：要么还是将附加信息直接和原先的Key合并，要么将它俩合并到一个数据结构中—-而后者会引来一个小问题：

       如果我把这个Key储存在某个有序容器中，我就需要重新告诉他各个key是按照什么顺序排序的。

      在做照片书的时候，服务器告诉你：哦，我们的模板ID就是唯一标识了，你拿这个ID就可以得到我这边关于这个作品的所有数据。而到了做台历的时候，服务器换了种说法：不好意思，为了充分利用资源，我们很多台历用得是同一个模板，你还要告诉我这个台历的产品ID。于是shit就这么发生了。

       可怜的Key就从string templateID，变成了struct TemplateKey{string m_sTemplateID;string m_sProductID};嗯，这不是什么问题，比较烦的就是如果你用map来储存，那你就得自己重写排序比较函数，于是你有了如下的代码：

view source
print?
1booloperator<(constTemplateSearchKey &searchKey) const
2{
3        returnm_sProductID < searchKey.m_sProductID &&
4               m_sTemplateID < searchKey.m_sTemplateID;
5}

可惜的是这样的代码大错特错，试试下面的代码

view source
print?
01#include <iostream>
02#include <map>
03#include <string>
04  
05usingnamespacestd;
06  
07structTemplateSearchKey
08{
09    string m_sProductID;
10    string m_sTemplateID;
11    TemplateSearchKey(conststring& sTemplateID,conststring& sProductID)
12    {
13        m_sTemplateID    = sTemplateID;
14        m_sProductID    = sProductID;
15    }
16  
17    booloperator<(constTemplateSearchKey &searchKey) const
18    {
19        returnm_sProductID < searchKey.m_sProductID &&
20               m_sTemplateID < searchKey.m_sTemplateID;
21    }
22};
23  
24intmain()
25{
26    map<TemplateSearchKey,string> testMap;
27    TemplateSearchKey key("","2");
28    TemplateSearchKey key1("","1");
29    TemplateSearchKey key2("","3");
30    testMap[key] = "a";
31    testMap[key1] = "b";
32    testMap[key2] = "c";
33    cout<<testMap[key]<<endl;
34    system("pause");
35    return0;
36  
37}

做调整：

view source
print?
1booloperator<(constTemplateSearchKey &searchKey) const
2{
3  
4       returnm_sProductID < searchKey.m_sProductID ||
5              m_sTemplateID < searchKey.m_sTemplateID;
6  
7}

 

而这个连编译都是不通过的……出一个ASSERT告诉你你的<符号是无效的。

view source
print?
01template<class_Pr, class_Ty1, class_Ty2> inline
02bool__CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const_Ty1& _Left, const_Ty2& _Right,
03  
04    constwchar_t*_Where, unsigned int_Line)
05  
06{    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
07  
08if(!_Pred(_Left, _Right))
09  
10    return(false);
11  
12elseif(_Pred(_Right, _Left))
13  
14    _DEBUG_ERROR2("invalid operator<", _Where, _Line); //ASSERT出来的点
15  
16return(true);
17  
18}

于是赶紧琢磨了下，改了：

view source
print?
01booloperator<(constTemplateSearchKey &searchKey) const
02{
03  
04    if(m_sProductID == searchKey.m_sProductID)
05    {
06        returnm_sTemplateID < searchKey.m_sTemplateID;
07    }
08    else
09    {
10        returnm_sProductID < searchKey.m_sProductID;
11    }
12};

OK，编译通过，运行没问题。可问题也来了，如果有3个成员呢？4个5个呢？一个比较好的方法就是直接把每个成员hash成一个数值，然后各个数值链起来，通过比较最后这个值来确定大小。于是就想了，为啥不学JAVA直接把排序功能切成两部分—-两个函数hasCode和equals，一个用来确定东西怎么排序，而另外一个用来确定是不是同一个东西。而STL这种做法虽然简练却晦涩，需要用户自己去考虑我写完的排序函数是不是符合传说中的排序三定律(有时候即使符合也不能完全反应用户原意)。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理