大家来看看, STL中的sort有bug?

yjgx007 2005-04-08 05:50:03
我用VC++写了一个console程序,代码如下:
发现一旦排序值全部相同,且排序总量大于SORT_MAX,并且我自定义的函数对象:在判断两元值相等(==)时总返回true,那么,将导致排序异常(指针越界,死循环):

异常的是指针越界,为什么会导致越界,详见下文

#include "stdafx.h"
#include <afxwin.h>
#include <algorithm>
using namespace std;

class greater {
public:
greater()
{
}
bool operator ()(int x1, int x2)
{
ASSERT(x1 == 12); // 我在这里作了断言, 目的是判断数组越界,为什么会导致越界,详见下
if (x1 > x2)
return false;

return true;
}
};

int main(int argc, char* argv[])
{
// UINT arr[] = {12, 14, 31, 9, 6, 30, 11, 65, 30
// };
UINT arr[] = {12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
};
int nSize = sizeof(arr)/sizeof(UINT);
greater gt;
sort(arr, arr+nSize, gt);

for (int i = 0; i < nSize; i++)
printf("%d\n", arr[i]);

return 0;
}


//////////////////////////////////////////////////////////////////////////////
// 排序中运行到下面这里, 在for(;_P(*_F, _Piv);++_F)中出现了死循环,原因是我最开始讲的条件一旦全部满足(主要是_P(*_F, _Piv)总返回true), 将导致指针越界, 此外, 为何总是死循环状态, 我在进一步研究...

template<class _RI, class _Ty, class _Pr> inline
_RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv, _Pr _P)
{for (; ; ++_F)
{for (; _P(*_F, _Piv); ++_F)
;
for (; _P(_Piv, *--_L); )
;
if (_L <= _F)
return (_F);
iter_swap(_F, _L); }}
...全文
708 32 打赏 收藏 转发到动态 举报
写回复
用AI写文章
32 条回复
切换为时间正序
请发表友善的回复…
发表回复
xiao0hua1 2010-06-17
  • 打赏
  • 举报
 回复
今天百度一个东西，搜到这个帖子，看到大家讨论的这个问题，实在忍不住要说一句。

sort(arr, arr+nSize, gt);

sort函数也就是快排函数大伙该熟悉下了，第二个参数表示数组的结束下标，正确的写法是：

sort(arr, arr+nSize-1, gt);
bing_huo 2005-04-18
  • 打赏
  • 举报
 回复
楼主 看看这个吧 http://dev.csdn.net/article/17/17509.shtm 说的比较详细 你的比较操作定义有问题。。。不符合stl的规则 这当然不是stl的bug~·！！！！！
calories 2005-04-18
  • 打赏
  • 举报
 回复
To: ilovevc(ilovevc)

if (x1 < x2)
return true;
else
return false;

我试了，在VC6下也不行，是死循环。

但是写 return (x1 < x2)； 就没有问题。
不知道怎么回事
向大家请教
yjgx007 2005-04-15
  • 打赏
  • 举报
 回复
to: wizard13(魔法师13)
批评的及是
wizard13 2005-04-15
  • 打赏
  • 举报
 回复
最后总结一下:strict weak ordering
thanks many peoples for lot of helps, the problem closed.
-----------------

people不可数, a lot of 或者是 lots of, 还有close是vt, is closed.
汗啊...
yjgx007 2005-04-15
  • 打赏
  • 举报
 回复
最后总结一下:strict weak ordering
thanks many peoples for lot of helps, the problem closed.
ilovevc 2005-04-13
  • 打赏
  • 举报
 回复
还不对。这个应该还是自己的问题。

你这个predicate不符合stl的协议。

你使用
return x1 > x2;

或者
return x2 > x1; 都没有问题的。

x1 == x2 的情况下应该返回false，而不是true。



ilovevc 2005-04-13
  • 打赏
  • 举报
 回复
int arr[] = {12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 13};
int nSize = sizeof(arr)/sizeof(int) - 2;
sort( arr, arr + nSize, my_greater);

我发现将测试数据在后面加一个11，13，促使循环退出，然后给sort的元素个数还是和以前一样，可以看到stlport读到了11，已经数组越界了。应该是Bug了。
ilovevc 2005-04-13
  • 打赏
  • 举报
 回复
我当前下的STLPort看来确实有个bug。

while (__comp(*__first, __pivot))
++__first;

这句，__pivot为12，由于你的元素都是12，因此 *first总是12，如果你的comp返回true，那么就会一直进行++first，运气好的话，你数组后面的垃圾可能总有一个返回false的，否则就是一个不停的循环直至内存违规访问。
fangrk 2005-04-13
  • 打赏
  • 举报
 回复
bool operator ()(UINT x1, UINT x2) const//你少了const 了！而且最好使用UINT
{
...
}
yjgx007 2005-04-13
  • 打赏
  • 举报
 回复
up!
FireEmissary 2005-04-13
  • 打赏
  • 举报
 回复
基本上,stl内部测试是否相等是用

if(!comp(a,b)&&!comp(b,a));

a与b相等的话,
if (x1 < x2)
return false;
else
return true;
却是使的!comp(a,b)&&!comp(b,a)为false
ilovevc 2005-04-13
  • 打赏
  • 举报
 回复
strictweakordering的大概理解就是less，即< , 而不是<=。
因此如果＝＝的时候，你应该返回false，而不是true。

true的意思是表示x1确实小于x2，而不是小于等于。
magicblue 2005-04-13
  • 打赏
  • 举报
 回复
楼主的operator明明就有语义错误，既然是greater，operator()(x,y)的意思就应该是：return ture;(if x>y) return false;(if x<y)。而楼主的代码的语义为：<= 。
sort要求comp为StrictWeakordering。StrictWeakordering的一个特性是：comp(x,x) == false (comp是StrictWeakordering的一个functional object)(楼主的operator会返回true)。
yjgx007 2005-04-13
  • 打赏
  • 举报
 回复
也就是说,返回true只能有一个条件符合?多于一个是不行的?
ilovevc 2005-04-13
  • 打赏
  • 举报
 回复
你发了以后我才能发新贴。不能连续发3个。

这个comp函数必须是StrictWeakordering，你的mygreater不符合这个要求。
例如 comp(x,x)必须返回false，而你的语句
if (x1 < x2)
return false;
else
return true;

就当x1等于x2时，你返回true。你改为
if (x1 < x2)
return true;
else
return false;
应该就没有问题。
yjgx007 2005-04-13
  • 打赏
  • 举报
 回复
to: fangrk(加把油，伙计！)
这里的数字都是12,用int也没关系,至于加const常函数是为什么?

to:ilovevc(ilovevc)
是这个协议吗?
User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.
yjgx007 2005-04-11
  • 打赏
  • 举报
 回复
首先,感谢大家给予帮助,但似乎仍无结果.

如果再无结果,我只能认为这是STL的bug了...
gye 2005-04-10
  • 打赏
  • 举报
 回复
我上面说错了。不好意思
calories 2005-04-10
  • 打赏
  • 举报
 回复
to:
gye(嗯嗯)
您说：“所以当比较x1和x2时，当x1==x2时，必须返回false。否则进入死循环”
可是按照下面这么写满足“当x1==x2时，必须返回false”，但是仍然进入死循环了，是怎么回事啊？

if (x1 < x2)
{
return true;
}
else
{
return false;
}

还是不明白这么写和直接写 return (x1 < x2) 有什么区别，我认为这两者是等价的。可是运行时前者不对，后者对。

加载更多回复（12）
C++ STLSTL实战开发精讲视频
《C++ 模板技术与 STL实战开发》主讲：丁宋涛​      泛型编程（Generic Programming）是一种全新的程序设计思想，它和STL是现代C++的精髓。可以说，不会STL很难称得上掌握了现代C++编程。STL是一个高效的C++程序库，它被容纳于C++标准程序库（C++ Standard Library）中，该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
STL中的sort排序
0 前言: STL，为什么你必须掌握 对于程序员来说，数据结构是必修的一门课。从查找到排序，从链表到二叉树，几乎所有的算法和原理都需要理解，理解不了也要死记硬背下来。幸运的是这些理论都已经比较成熟，算法也基本固定下来，不需要你再去花费心思去考虑其算法原理，也不用再去验证其准确性。不过，等你开始应用计算机语言来工作的时候，你会发现，面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法，...
STL中sort函数的用法
详细解说 STL 排序(Sort) 详细解说 STL 排序(Sort) 作者Winter 详细解说 STL 排序(Sort) 0 前言: STL，为什么你必须掌握 1 STL提供的Sort 算法 1.1 所有sort算法介绍 1.2 sort 中的比较函数 1.3 sort 的稳定性 1.4 全排序 1.5 局部排序 1.6 nth_element 指定元
C++ stl 的sort使用中的坑
    stl的sort函数是一个很有用且高效的排序方法。如果自行添加比较函数，可以很大程度上的扩展其功能，使之能灵活的适应各种场景。但是sort在使用过程中存在一些注意事项，如果不加注意，很容易发生bug满地跑，你却不知道bug的源头在哪里的情况。    1.sort需要迭代器是随机访问迭代器。如果使用list容器，可以使用list容器自带的sort成员函数，而不要使用使用这个泛型算法的sor...
详细解说 STL 排序(Sort)
详细解说 STL 排序(Sort) 0 前言: STL，为什么你必须掌握1 STL提供的Sort 算法 1.1 所有sort算法介绍1.2 sort 中的比较函数1.3 sort 的稳定性1.4 全排序1.5 局部排序1.6 nth_element 指定元素排序1.7 partition 和stable_partition 2 Sort 和容器3 选择合适的排序函数4 小结5 参考文
C++ 语言

64,637

社区成员

250,559

社区内容

发帖
与我相关
我的任务
社区描述
C++ 语言相关问题讨论，技术干货分享，前沿动态等
c++ 技术论坛（原bbs）
社区管理员
  • C++ 语言社区
  • encoderlee
  • paschen
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
  1. 请不要发布与C++技术无关的贴子
  2. 请不要发布与技术无关的招聘、广告的帖子
  3. 请尽可能的描述清楚你的问题，如果涉及到代码请尽可能的格式化一下

试试用AI创作助手写篇文章吧

+ 用AI写文章