vc7.1中nth_element的一个实现优化

王朝vc·作者佚名  2006-03-30
窄屏简体版  字體: |||超大  

今天在vc7.1下写了一个小例子,测试一下nth_element和partial_sort,结果partial_sort表现正常,但nth_element的表现却很奇怪。

代码是这样的:

vector<int> v;

for (int i = 0; i < 20; i++)

v.push_back(i + 1);

random_shuffle(v.begin(), v.end());

nth_element(v.begin(), v.begin() + 5, v.end());

copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

return 0;

按照预期,前面5个数字应该是乱序的5个,后面的也是乱序。实际上输出的却是一个全排序的结果。这让我很吃惊,立刻怀疑vc的实现有问题。结果向cber 请教,cber先问我看过14882没有?汗!我只看了MSDN。去看14882。立刻,看到,如果实现采用全排的话,复杂度约束是不可能满足的。 cber又教育我:看了源代码了吗?再次汗!去看源代码!正如侯捷所说,“源码面前,了无秘密”,原来,库的实现中有一个优化:当区间元素个数不大于32 时,直接做一次全排序,只有元素个数足够多时,才采用常规的线性复杂度算法。

从今天的事情,可以看到自己的态度仍然过于轻浮,不能踏踏实实安心学习。其实分析源代码也就是几分钟的功夫,可是潜意识一直不大喜欢Dinkumware的stl实现,所以也就比较抗拒去看它的源代码。做技术,可一定要脚踏实地啊!

鄙视自己一下!立此存照!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航