這兩天定位了一個(gè)由std::sort引發(fā)的core,。
寫了下面的程序來復(fù)現(xiàn)此問題,。
- #include <stdio.h>
- #include <vector>
- #include <algorithm>
- #include <new>
- struct foo_t
- {
- int size;
- };
- class cmp_t
- {
- public:
- bool operator()(foo_t *a, foo_t *b)
- {
- return a->size >= b->size;
- }
- };
- int main(int argc, char *argv[])
- {
- std::vector<foo_t *> vec;
- for (int i = 0; i < 17; i++)
- {
- foo_t *x = new(std::nothrow) foo_t();
- if (NULL == x)
- {
- goto fail;
- }
- else
- {
- x->size = 1;
- }
- vec.push_back(x);
- }
- std::sort(vec.begin(), vec.end(), cmp_t());
- fail:
- for(std::vector<foo_t *>::iterator iter = vec.begin(); vec.end() != iter; ++iter)
- {
- delete *iter;
- *iter = NULL;
- }
- return 0;
- }
然后編譯
- g++ main.cpp -Werror -Wall -g
然后執(zhí)行，此時(shí)系統(tǒng)出core，錯(cuò)誤類型為段錯(cuò)誤 如果無core文件產(chǎn)生,，可以使用
后重新執(zhí)行一次,，此時(shí)就會(huì)有core文件生成 然后
- gdb a.out core
- (gdb) bt
- #0 0x0804889e in cmp_t::operator() (this=0xbfed92d0, a=0x0, b=0x9a9d0c8) at main.cpp:16
#1 0x080497ff in std::__unguarded_partition<__gnu_cxx::__normal_iterator<foo_t**, std::vector<foo_t*, std::allocator<foo_t*> > >, foo_t*, cmp_t> (__first=..., __last=..., __pivot=@0x9a9d1a0, __comp=...) at /usr/include/c++/4.6/bits/stl_algo.h:2233
#2 0x0804926a in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<foo_t**, std::vector<foo_t*, std::allocator<foo_t*> > >, cmp_t> (__first=..., __last=..., __comp=...) at /usr/include/c++/4.6/bits/stl_algo.h:2265
#3 0x08048e84 in std::__introsort_loop<__gnu_cxx::__normal_iterator<foo_t**, std::vector<foo_t*, std::allocator<foo_t*> > >, int, cmp_t> (
__first=..., __last=..., __depth_limit=7, __comp=...) at /usr/include/c++/4.6/bits/stl_algo.h:2306
#4 0x08048a22 in std::sort<__gnu_cxx::__normal_iterator<foo_t**, std::vector<foo_t*, std::allocator<foo_t*> > >, cmp_t> (__first=...,
__last=..., __comp=...) at /usr/include/c++/4.6/bits/stl_algo.h:5368
#5 0x080487ce in main (argc=1, argv=0xbfed9464) at main.cpp:38
可以看到,，系統(tǒng)core在了排序函數(shù)里面,。 然后通過分析stl代碼發(fā)現(xiàn)以下一段代碼
- /// This is a helper function...
- template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
- _RandomAccessIterator
- __unguarded_partition(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- const _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;
- }
- }
此函數(shù)完成快速排序中分區(qū)功能，即將比哨兵小的數(shù)據(jù)放在其前,，大的放在其后,。 函數(shù)中使用的是 while (__comp (*__first , __pivot ))
++__first;
如果當(dāng)比較元素相同返回真時(shí)，此時(shí)比較元素將會(huì)繼續(xù)向下遍歷，在極端情況下,，例如程序中所有元素都是一樣的情況下,，在這種情況下，就會(huì)出現(xiàn)訪問越界,，結(jié)果就是導(dǎo)致程序出現(xiàn)segment fault
所以在寫c++ stl中的比較函數(shù)是,，bool返回真的時(shí)候，一定是“真的”大,，或者小,，等于的時(shí)候只能返回false。
這個(gè)錯(cuò)誤算是一次教訓(xùn),，索性的是沒有引起大范圍的錯(cuò)誤。
|
