shit_adam

insertion_sort for single_list/forward_list

May 21st, 2013
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1.     template<typename _Tp, class _Alloc>
  2.     template<typename _Comp>
  3.     void
  4.     forward_list<_Tp, _Alloc>::
  5.     sort(_Comp __comp) {
  6.         _Node * __list = static_cast<_Node *>(this->_M_impl._M_head._M_next);
  7.         _Node * __sorted_list = nullptr;
  8.  
  9.         while(__list != nullptr) {
  10.             // save the head
  11.             _Node * __head = __list;
  12.             // cut off the head from the list
  13.             __list = static_cast<_Node *>(__list->_M_next);
  14.  
  15.             // __fsp is the double star node for fast splice
  16.             _Node ** __fsp = &__sorted_list;
  17.  
  18. #ifndef NDEBUG
  19. std::cout << "--------------------------------------------------" << std::endl;
  20. std::cout << "__head @" << __head << " : " <<  *__head->_M_valptr() << std::endl;
  21. std::cout << "__list: ";
  22. for(_Node_base * p = __list; p != nullptr; p = p->_M_next)
  23.     std::cout << *(static_cast<_Node *>(p)->_M_valptr()) << ' ';
  24. std::cout << std::endl;
  25. std::cout << "sorted_list: ";
  26. for(_Node_base * p = __sorted_list; p != nullptr; p = p->_M_next)
  27.     std::cout << *(static_cast<_Node *>(p)->_M_valptr()) << ' ';
  28. std::cout << std::endl;
  29. #endif//NDEBUG
  30.  
  31.             while(true) {
  32. #ifndef NDEBUG
  33. std::cout << "*__fsp --> " << (*__fsp) << std::endl;
  34. #endif//NDEBUG
  35.                 if(*__fsp == nullptr ||
  36.                         __comp(
  37.                             *__head->_M_valptr(),
  38.                             *((*__fsp)->_M_valptr())
  39.                         ) == true)
  40.                 {
  41.                     __head->_M_next = *__fsp;
  42.                     *__fsp = __head;
  43. #ifndef NDEBUG
  44. std::cout << "__head->_M_next --> " << (__head->_M_next) << std::endl;
  45. std::cout << "*__fsp --> " << (*__fsp) << std::endl;
  46. #endif//NDEBUG
  47.                     break;
  48.                 } else {
  49.                     __fsp = (_Node **)(&((*__fsp)->_M_next));
  50.                 }//if-else
  51.             }//while
  52.         }//while
  53.  
  54.         this->_M_impl._M_head._M_next = __sorted_list;
  55.     }//sort(_Comp __comp)
Add Comment
Please, Sign In to add comment