Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> Android開發 >> 關於android開發 >> std::nth_element crash問題

std::nth_element crash問題

編輯:關於android開發

std::nth_element crash問題


(1) 源碼:

  1. auto less_compare = [] (const MirroringGroup& mg1, const MirroringGroup& mg2) -> bool {
  2. return (mg1.usage() < mg2.usage());
  3. };
  4. std::nth_element(mgs->begin(), mgs->begin() + (copy_count - 1), mgs->end(), less_compare);

(2) 問題:

經常發生crash,stack如下:

  1. #0 0x00000000004b3807 in MirroringGroup::CopyFrom (this=0x15edf20, from=...) at miuifs/miuistorage-dev/idl/proto/InternalData.pb.cc:6487
  2. #1 0x000000000052bc71 in MirroringGroup::operator= (this=0x15edf20, from=...) at miuifs/miuistorage-dev/idl/proto/InternalData.pb.h:1797
  3. #2 0x000000000052f7cb in std::swap (__a=..., __b=...) at /usr/local/include/c++/4.8.2/bits/move.h:177
  4. #3 0x000000000052e0b0 in std::iter_swap<__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > > > (__a=..., __b=...)
  5. at /usr/local/include/c++/4.8.2/bits/stl_algobase.h:147
  6. #4 0x0000000000604b11 in std::__unguarded_partition<__gnu_cxx::__normal_iterator >, MirroringGroup, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, const MirroringGroup &, miuifs::BlockManager::__lambda101) (__first=..., __last=..., __pivot=..., __comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2270
  7. #5 0x0000000000603c1b in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator >, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, miuifs::BlockManager::__lambda101) (
  8. __first=..., __last=..., __comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2296
  9. #6 0x0000000000603408 in std::__introselect<__gnu_cxx::__normal_iterator >, long int, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, long, miuifs::BlockManager::__lambda101) (__first=..., __nth=..., __last=..., __depth_limit=2,
  10. __comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2394
  11. #7 0x0000000000602c95 in std::nth_element<__gnu_cxx::__normal_iterator >, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, miuifs::BlockManager::__lambda101) (__first=..., __nth=..., __last=..., __comp=...)
  12. at /usr/local/include/c++/4.8.2/bits/stl_algo.h:5417
  13. #8 0x000000000060039c in miuifs::BlockManager::ChooseWritableMirroringGroups (this=0x118abe0 , mgs=0x7fffeb9f4140,
  14. copy_count=2) at miuifs/miuistorage-dev/BlockManager.cc:391
  15. #9 0x00000000005ff9cf in miuifs::BlockManager::NewBlock (this=0x118abe0 ) at miuifs/miuistorage-dev/BlockManager.cc:331
  16. #10 0x00000000005fed63 in miuifs::BlockManager::AcquireBlock (this=0x118abe0 , attribute=...)
  17. at miuifs/miuistorage-dev/BlockManager.cc:243

(3) 查找問題:

問題一直出現在std::nth_element中,開始沒有想到是STL的問題,一直沒有很好的解決辦法,後來通過閱讀STL源碼找到原因在/usr/local/include/c++/4.8.2/bits/stl_algo.h中:

  1. template
  2. inline _RandomAccessIterator
  3. __unguarded_partition_pivot(_RandomAccessIterator __first,
  4. _RandomAccessIterator __last, _Compare __comp)
  5. {
  6. _RandomAccessIterator __mid = __first + (__last - __first) / 2;
  7. std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
  8. __comp);
  9. return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
  10. }

__move_median_to_first函數的作用是將 __first +1 , __mid, (__last - 2) 中中間大小的值和 __first交換。但是卻忽略了__mid,(__last - 2) 指向相同迭代器的情況,如果輸入時情況如下:


經過__move_median_to_first之後的結果如下:


此時__first指向了最大的值。然後看std::__unguarded_partition的實現,在2263行__comp(*__first, __pivot))永遠返回true,導致++__first一直執行而訪問了非法內存。


  1. template
  2. _RandomAccessIterator
  3. __unguarded_partition(_RandomAccessIterator __first,
  4. _RandomAccessIterator __last,
  5. const _Tp& __pivot, _Compare __comp)
  6. {
  7. while (true)
  8. {
  9. while (__comp(*__first, __pivot))
  10. ++__first;
  11. --__last;
  12. while (__comp(__pivot, *__last))
  13. --__last;
  14. if (!(__first < __last))
  15. return __first;
  16. std::iter_swap(__first, __last);
  17. ++__first;
  18. }
  19. }

(4) 解決方法:

通過google找到下面這個鏈接,發現確實是一個STL的bug,只能通過升級C++解決了。

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=732042





  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved