注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

std中sort为什么要求严格弱序  

2017-05-21 18:44:55|  分类: C/C++基础 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、std::sort对于"严格弱序"(strict weak ordering)的限制
在std文档中,对于sort使用的比较操作是要求严格弱序的,这个限制会推导出一个看起来有些违背直观的行为,那就是假设两个对象的值是常规意义上的相等,此时比较算符同样需要返回false。下面举一个简单直观的例子,也就是这样的效果:
struct tsecer
{
int x;
int y;
};
bool sortcomp(const tsecer &lhs, const tsecer &rhs)
{
        return lhs.x < rhs.x || lhs.x == rhs.x && lhs.y < rhs.y;
}
这里对于完全相等的值其实是返回false,这个直观上看有些不合常理,但是结合下std库的实现就很容易理解这个限制。
二、gcc使用的stl::sort实现
毫无意外,几乎所有的库函数对于排序的实现都是快速排序,包括glibc和mysql的排序实现。gcc-4.1.0\libstdc++-v3\include\bits\stl_algo.h:
sort===>>>__introsort_loop===>>>__unguarded_partition
  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
 _RandomAccessIterator __last,
 _Tp __pivot, _Compare __comp)
    {
      while (true)
{
 while (__comp(*__first, __pivot))
   ++__first;
 --__last;
 while (__comp(__pivot, *__last))
   --__last;
 if (!(__first < __last))
   return __first;
 std::iter_swap(__first, __last);
 ++__first;
}
    }
这里可以看到一个典型的快速排序方法,其中的__pivot即使从队列中选出的中轴点,或者更通俗的说就是一个参照点,它用来将当前列表中的元素分割为两部分,比它小的和不比它小的。我们假设当两个对象的值在常规意义上相等时比较操作符__comp返回true,当迭代列表中所有元素都相同的时候,内层的while循环并执行++first操作,直到迭代器返回非法内容导致comp函数出现异常。
三、测试代码
由于从源代码中可以看到,其中对于元素数量小于等于_S_threshold(值为16)的时候使用的是简单的插入排序,所以没有前面所说的快排的分割问题,从而在向量中元素数量小于等于16时代码运行正确,但是在其它情况下发生异常,而这种看起来类似偶现的问题是最为坑爹的。
tsecer@harry: cat stdsortcomp.cpp 
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
bool comp(const int &lhs, const int &rhs)
{
return lhs <= rhs;
}

int main(int argc, char * argv[])
{
vector<int> v;
int ilen = atoi(argv[1]);
for (int i = 0; i < ilen; i++)
{
v.push_back(0);
}
sort(v.begin(), v.end(),comp);
for (vector<int>::iterator i = v.begin(); i != v.end(); i++)
{
printf("%d, ", *i);
}
printf("\n");
return 0;
}
tsecer@harry: g++ stdsortcomp.cpp 
tsecer@harry: ./a.out 16
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
tsecer@harry: ./a.out 17
Segmentation fault (core dumped)
tsecer@harry: 
四、延伸的一些问题
std的很多操作都是没有严格限制必须是类或者函数,特别是对于sort的最后一个参数,它即可以是重载了函数算符的functor,也可以是最为普通的实实在在的function,同样的迭代器也可以是普通的原始数组指针,比较也可以是原始的内置小于算符。

下面使用的迭代器就是原始的数组指针,而比较算符也就是整数的天然内置比较算符。
tsecer@harry: cat native.cpp 
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;
#define ARRLEN(arr) (int)(sizeof(arr)/sizeof(arr[0]))
int main()
{
int arr[] = {5, 4, 3, 2, 1};
sort(arr, arr + ARRLEN(arr));
for (int i = 0; i < ARRLEN(arr); i++)
{
printf("%d, ", arr[i]);
}
printf("\n");
return 0;
}
tsecer@harry: g++ native.cpp -o native
tsecer@harry: ./native 
1, 2, 3, 4, 5, 
tsecer@harry: 

  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017