VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 867|回复: 0

[交流] stl::list 實現

[复制链接]
74_avatar_middle
在线会员 发表于 2016-10-11 10:01:51 | 显示全部楼层 |阅读模式
孤近日一項目中 需要使用一個鍊錶 然由於某些原因而不能使用 std::list 故 自己按照 std::list 的接口要求 實現了一個 list
其使用方法 和 std::list 一樣
除了 void insert_n(const_iterator where,const std::size_t n,const T& v) 在std::list 中是 void insert(const_iterator where,const std::size_t n,const T& v)  
(孤使用 insert_n 而非 insert 在於 如果 使用insert 其會和 模板函數 insert(const_iterator where,Iterator begin,Iterator end) 重名 處理起來會增加許多額外代碼
且孤 急切需要此list 故沒按照 c++標準實現)
且孤並沒有 提供 空間適配器

一般情況下 請不要使用 孤實現的list或你自己實現的list 應該 盡量使用 std::list
std::list 經過千錘百煉和 多年的優化 而且在c++發布新特性時 標準庫 通常會用最新的特性 進行 效率安全性的優化
比如c++11後 所有容器都提供了 右值引用的 構造/賦值

然從孤實現的 list 中 多少可以看到一些 標準庫實現的 方式 對於理解標準庫 孤認為還是有點幫助的

https://github.com/zuiwuchang/ki ... /container/list.hpp

  1. //一個同 std::list 的 鍊錶 用在某些不能使用 std::list 的位置
  2. #ifndef KING_LIB_HEADER_CONTAINER_LIST
  3. #define KING_LIB_HEADER_CONTAINER_LIST

  4. #include <memory>
  5. #include <vector>
  6. #include <algorithm>


  7. namespace king
  8. {
  9. namespace container
  10. {
  11.     template<typename T>
  12.     class list
  13.     {
  14.     protected:
  15.         typedef struct _NODE_{
  16.             //節點 存儲 數據
  17.             T Data;

  18.             //上一個 節點 為NULL 表示 第一個節點
  19.             _NODE_* Prev;

  20.             //下一個 節點 為 NULL 表示 最後一個節點
  21.             _NODE_* Next;
  22.         }NODE,*PNODE;


  23.         //鍊錶頭
  24.         PNODE _first;
  25.         //鍊錶尾
  26.         PNODE _last;

  27.         //節點 數量
  28.         std::size_t _size;

  29.     protected:
  30.         PNODE create_node()
  31.         {
  32.             return new(std::nothrow) NODE;
  33.         }
  34.         void destory_node(PNODE p)
  35.         {
  36.             delete p;
  37.         }
  38.     public:
  39.         list():_first(NULL),_last(NULL),_size(0)
  40.         {

  41.         }
  42.         list(const list& copy):_first(NULL),_last(NULL),_size(0)
  43.         {
  44.             insert(begin(),copy.begin(),copy.end());

  45.         }
  46.         list& operator=(const list& copy)
  47.         {
  48.             clear_insert(copy.begin(),copy.end());

  49.             return *this;
  50.         }

  51.         //返回 節點 數量
  52.         inline std::size_t size()const
  53.         {
  54.             return _size;
  55.         }
  56.         //返回 鍊錶 是否為空
  57.         inline bool empty()const
  58.         {
  59.             return !_size;
  60.         }
  61.         //在鍊錶尾 壓入數據
  62.         void push_back(const T& v)    //throw std::bad_alloc
  63.         {
  64.             //申請新 節點
  65.             PNODE p = create_node();
  66.             if(!p)
  67.             {
  68.                 throw std::bad_alloc();
  69.             }

  70.             //copy 數據
  71.             p->Data = v;

  72.             //設置 next
  73.             p->Next = NULL;

  74.             //設置 precv
  75.             if(_last)
  76.             {
  77.                 //連接 節點
  78.                 _last->Next = p;
  79.                 p->Prev = _last;
  80.             }
  81.             else
  82.             {
  83.                 //_last 為空
  84.                 //則 鍊錶一定為空 _first 為空
  85.                 _first = p;
  86.                 p->Prev = NULL;

  87.             }

  88.             //設置鍊錶 尾
  89.             _last = p;

  90.             //增加數量記錄
  91.             ++_size;
  92.         }
  93.         //返回鍊錶 尾節點
  94.         //鍊錶為空 發生未定義行為
  95.         inline T& back()
  96.         {
  97.             return _last->Data;
  98.         }
  99.         //彈出鍊錶 尾節點
  100.         //鍊錶為空 發生未定義行為
  101.         void pop_back()
  102.         {
  103.             PNODE p = _last;
  104.             PNODE prev = _last->Prev;
  105.             if(prev)
  106.             {
  107.                 prev->Next = NULL;
  108.             }
  109.             else
  110.             {
  111.                 //設置新 頭節點
  112.                 _first = NULL;
  113.             }


  114.             //設置新 尾節點
  115.             _last = prev;


  116.             //減少數量記錄
  117.             --_size;

  118.             //釋放資源
  119.             destory_node(p);

  120.         }

  121.         //在鍊錶頭 壓入數據
  122.         void push_front(const T& v)    //throw std::bad_alloc
  123.         {
  124.             //申請新 節點
  125.             PNODE p = create_node();
  126.             if(!p)
  127.             {
  128.                 throw std::bad_alloc();
  129.             }

  130.             //copy 數據
  131.             p->Data = v;

  132.             //設置 prev
  133.             p->Prev = NULL;

  134.             //設置 next
  135.             if(_first)
  136.             {
  137.                 //連接 節點
  138.                 _first->Prev = p;
  139.                 p->Next = _first;
  140.             }
  141.             else
  142.             {
  143.                 //_first 為空
  144.                 //則 鍊錶一定為空 _last 為空
  145.                 _last = p;
  146.                 p->Next = NULL;

  147.             }

  148.             //設置鍊錶 頭
  149.             _first = p;

  150.             //增加數量記錄
  151.             ++_size;
  152.         }
  153.         //返回鍊錶 頭節點
  154.         //鍊錶為空 發生未定義行為
  155.         inline T& front()
  156.         {
  157.             return _first->Data;
  158.         }

  159.         //彈出鍊錶 頭節點
  160.         //鍊錶為空 發生未定義行為
  161.         void pop_front()
  162.         {
  163.             PNODE p = _first;
  164.             PNODE next = _first->Next;
  165.             if(next)
  166.             {
  167.                 next->Prev = NULL;
  168.             }
  169.             else
  170.             {
  171.                 //設置新 尾節點
  172.                 _last = NULL;
  173.             }


  174.             //設置新 頭節點
  175.             _first = next;


  176.             //減少數量記錄
  177.             --_size;

  178.             //釋放資源
  179.             destory_node(p);

  180.         }

  181.         void clear()
  182.         {
  183.             PNODE next;
  184.             while(_first)
  185.             {
  186.                 next =_first->Next;
  187.                 try
  188.                 {
  189.                     destory_node(_first);
  190.                 }
  191.                 catch(...)
  192.                 {

  193.                 }
  194.                 _first = next;
  195.             }
  196.             _size = 0;
  197.             _last = NULL;
  198.         }
  199.     public:
  200.         //迭代器定義
  201.         class iterator
  202.         {
  203.         public:
  204.             PNODE _p;
  205.             const list* _list;

  206.             iterator(PNODE p,const list* l):_p(p),_list(l)
  207.             {

  208.             }
  209.             iterator(const iterator& copy)
  210.             {
  211.                 _p = copy._p;
  212.                 _list = copy._list;
  213.             }
  214.             iterator& operator=(const iterator& copy)
  215.             {
  216.                 _p = copy._p;
  217.                 _list = copy._list;
  218.                 return *this;
  219.             }
  220.             T* operator->()const
  221.             {
  222.                 return &(_p->Data);
  223.             }
  224.             T& operator*()const
  225.             {
  226.                 return _p->Data;
  227.             }

  228.             inline bool operator==(const iterator& compare)const
  229.             {
  230.                 return _p == compare._p;
  231.             }
  232.             inline bool operator!=(const iterator& compare)const
  233.             {
  234.                 return _p != compare._p;
  235.             }

  236.             inline iterator operator++()
  237.             {
  238.                 _p = _p->Next;
  239.                 return *this;
  240.             }
  241.             inline iterator operator++(int)
  242.             {
  243.                 iterator tmp = *this;
  244.                 ++*this;
  245.                 return tmp;
  246.             }
  247.             inline iterator operator--()
  248.             {
  249.                 if(_p)
  250.                 {
  251.                     _p = _p->Prev;
  252.                 }
  253.                 else
  254.                 {
  255.                     _p = _list->_last;
  256.                 }
  257.                 return *this;
  258.             }
  259.             inline iterator operator--(int)
  260.             {
  261.                 iterator tmp = *this;
  262.                 --*this;
  263.                 return tmp;
  264.             }
  265.         };

  266.         //返回 正向 迭代器 頭
  267.         inline iterator begin()
  268.         {
  269.             return iterator(_first,this);
  270.         }

  271.         //返回 正向 迭代器 尾
  272.         inline iterator end()
  273.         {
  274.             return iterator(NULL,this);
  275.         }


  276.         class const_iterator
  277.         {
  278.         public:
  279.             const list* _list;
  280.             PNODE _p;

  281.             const_iterator(PNODE p,const list* l):_p(p),_list(l)
  282.             {

  283.             }
  284.             const_iterator(const iterator& copy)
  285.             {
  286.                 _p = copy._p;
  287.                 _list = copy._list;
  288.             }
  289.             const_iterator& operator=(const iterator& copy)
  290.             {
  291.                 _p = copy._p;
  292.                 _list = copy._list;
  293.                 return *this;
  294.             }
  295.             const_iterator(const const_iterator& copy)
  296.             {
  297.                 _p = copy._p;
  298.                 _list = copy._list;
  299.             }
  300.             const_iterator& operator=(const const_iterator& copy)
  301.             {
  302.                 _p = copy._p;
  303.                 _list = copy._list;
  304.                 return *this;
  305.             }
  306.             const T* operator->()const
  307.             {
  308.                 return &(_p->Data);
  309.             }
  310.             const T& operator*()const
  311.             {
  312.                 return _p->Data;
  313.             }

  314.             inline bool operator==(const const_iterator& compare)const
  315.             {
  316.                 return _p == compare._p;
  317.             }
  318.             inline bool operator!=(const const_iterator& compare)const
  319.             {
  320.                 return _p != compare._p;
  321.             }

  322.             inline const_iterator operator++()
  323.             {
  324.                 _p = _p->Next;
  325.                 return *this;
  326.             }
  327.             inline const_iterator operator++(int)
  328.             {
  329.                 const_iterator tmp = *this;
  330.                 ++*this;
  331.                 return tmp;
  332.             }
  333.             inline const_iterator operator--()
  334.             {
  335.                 if(_p)
  336.                 {
  337.                     _p = _p->Prev;
  338.                 }
  339.                 else
  340.                 {
  341.                     _p = _last;
  342.                 }
  343.                 return *this;
  344.             }
  345.             inline const_iterator operator--(int)
  346.             {
  347.                 const_iterator tmp = *this;
  348.                 --*this;
  349.                 return tmp;
  350.             }
  351.         };
  352.         inline const_iterator begin()const
  353.         {
  354.             return const_iterator(_first,this);
  355.         }
  356.         inline const_iterator end()const
  357.         {
  358.             return const_iterator(NULL,this);
  359.         }


  360.         //逆向迭代器定義
  361.         class reverse_iterator
  362.         {
  363.         public:
  364.             PNODE _p;
  365.             const list* _list;

  366.             reverse_iterator(PNODE p,const list* l):_p(p),_list(l)
  367.             {

  368.             }

  369.             reverse_iterator(const iterator& copy)
  370.             {
  371.                 _p = copy._p;
  372.                 _list = copy._list;

  373.                 if(_p == _list->_first)
  374.                 {
  375.                     _p = NULL;
  376.                 }
  377.                 else if(_p == NULL)
  378.                 {
  379.                     _p = _list->_last;
  380.                 }
  381.             }
  382.             iterator base()const
  383.             {
  384.                 PNODE p = _p;
  385.                 if(p == NULL)
  386.                 {
  387.                     p = _list->_first;
  388.                 }
  389.                 else if(p == _list->_last)
  390.                 {
  391.                     p = NULL;
  392.                 }

  393.                 return iterator(p,_list);
  394.             }

  395.             reverse_iterator(const reverse_iterator& copy)
  396.             {
  397.                 _p = copy._p;
  398.                 _list = copy._list;
  399.             }
  400.             reverse_iterator& operator=(const reverse_iterator& copy)
  401.             {
  402.                 _p = copy._p;
  403.                 _list = copy._list;
  404.                 return *this;
  405.             }
  406.             T* operator->()const
  407.             {
  408.                 return &(_p->Data);
  409.             }
  410.             T& operator*()const
  411.             {
  412.                 return _p->Data;
  413.             }

  414.             inline bool operator==(const reverse_iterator& compare)const
  415.             {
  416.                 return _p == compare._p;
  417.             }
  418.             inline bool operator!=(const reverse_iterator& compare)const
  419.             {
  420.                 return _p != compare._p;
  421.             }

  422.             inline reverse_iterator operator++()
  423.             {
  424.                 _p = _p->Prev;
  425.                 return *this;
  426.             }
  427.             inline reverse_iterator operator++(int)
  428.             {
  429.                 reverse_iterator tmp = *this;
  430.                 ++*this;
  431.                 return tmp;
  432.             }
  433.             inline reverse_iterator operator--()
  434.             {
  435.                 if(_p)
  436.                 {
  437.                     _p = _p->Next;
  438.                 }
  439.                 else
  440.                 {
  441.                     _p = _first;
  442.                 }
  443.                 return *this;
  444.             }
  445.             inline reverse_iterator operator--(int)
  446.             {
  447.                 reverse_iterator tmp = *this;
  448.                 --*this;
  449.                 return tmp;
  450.             }
  451.         };
  452.         //返回 逆向 迭代器 頭
  453.         inline reverse_iterator rbegin()
  454.         {
  455.             return reverse_iterator(_last,this);
  456.         }

  457.         //返回 逆向 迭代器 尾
  458.         inline reverse_iterator rend()
  459.         {
  460.             return reverse_iterator(NULL,this);
  461.         }


  462.         class const_reverse_iterator
  463.         {
  464.         public:
  465.             PNODE _p;
  466.             const list* _list;

  467.             const_reverse_iterator(PNODE p,const list* l):_p(p),_list(l)
  468.             {

  469.             }

  470.             const_reverse_iterator(const const_iterator& copy)
  471.             {
  472.                 _p = copy._p;
  473.                 _list = copy._list;

  474.                 if(_p == _list->_first)
  475.                 {
  476.                     _p = NULL;
  477.                 }
  478.                 else if(_p == NULL)
  479.                 {
  480.                     _p = _list->_last;
  481.                 }
  482.             }
  483.             const_reverse_iterator(const iterator& copy)
  484.             {
  485.                 _p = copy._p;
  486.                 _list = copy._list;

  487.                 if(_p == _list->_first)
  488.                 {
  489.                     _p = NULL;
  490.                 }
  491.                 else if(_p == NULL)
  492.                 {
  493.                     _p = _list->_last;
  494.                 }
  495.             }
  496.             const_iterator base()const
  497.             {
  498.                 PNODE p = _p;
  499.                 if(p == NULL)
  500.                 {
  501.                     p = _list->_first;
  502.                 }
  503.                 else if(p == _list->_last)
  504.                 {
  505.                     p = NULL;
  506.                 }

  507.                 return const_iterator(p,_list);
  508.             }

  509.             const_reverse_iterator(const reverse_iterator& copy)
  510.             {
  511.                 _p = copy._p;
  512.                 _list = copy._list;
  513.             }
  514.             const_reverse_iterator& operator=(const reverse_iterator& copy)
  515.             {
  516.                 _p = copy._p;
  517.                 _list = copy._list;
  518.                 return *this;
  519.             }
  520.             const_reverse_iterator(const const_reverse_iterator& copy)
  521.             {
  522.                 _p = copy._p;
  523.                 _list = copy._list;
  524.             }
  525.             const_reverse_iterator& operator=(const const_reverse_iterator& copy)
  526.             {
  527.                 _p = copy._p;
  528.                 _list = copy._list;
  529.                 return *this;
  530.             }
  531.             const T* operator->()const
  532.             {
  533.                 return &(_p->Data);
  534.             }
  535.             const T& operator*()const
  536.             {
  537.                 return _p->Data;
  538.             }

  539.             inline bool operator==(const const_reverse_iterator& compare)const
  540.             {
  541.                 return _p == compare._p;
  542.             }
  543.             inline bool operator!=(const const_reverse_iterator& compare)const
  544.             {
  545.                 return _p != compare._p;
  546.             }

  547.             inline const_reverse_iterator operator++()
  548.             {
  549.                 _p = _p->Prev;
  550.                 return *this;
  551.             }
  552.             inline const_reverse_iterator operator++(int)
  553.             {
  554.                 const_reverse_iterator tmp = *this;
  555.                 ++*this;
  556.                 return tmp;
  557.             }
  558.             inline const_reverse_iterator operator--()
  559.             {
  560.                 if(_p)
  561.                 {
  562.                     _p = _p->Next;
  563.                 }
  564.                 else
  565.                 {
  566.                     _p = _first;
  567.                 }
  568.                 return *this;
  569.             }
  570.             inline const_reverse_iterator operator--(int)
  571.             {
  572.                 const_reverse_iterator tmp = *this;
  573.                 --*this;
  574.                 return tmp;
  575.             }
  576.         };
  577.         //返回 逆向 迭代器 頭
  578.         inline const_reverse_iterator rbegin()const
  579.         {
  580.             return const_reverse_iterator(_last,this);
  581.         }

  582.         //返回 逆向 迭代器 尾
  583.         inline const_reverse_iterator rend()const
  584.         {
  585.             return const_reverse_iterator(NULL,this);
  586.         }

  587.         //insert
  588.         void insert(const_iterator where,const T& v) // throw std::bad_alloc
  589.         {
  590.             if(where == end())
  591.             {
  592.                 push_back(v);
  593.                 return;
  594.             }

  595.             //申請新 節點
  596.             PNODE p = create_node();
  597.             if(!p)
  598.             {
  599.                 throw std::bad_alloc();
  600.             }

  601.             //插入位置
  602.             PNODE p_i = where._p;

  603.             //copy 數據
  604.             p->Data = v;

  605.             //設置 next
  606.             p->Next = p_i;
  607.             PNODE prev = p_i->Prev;
  608.             p_i->Prev = p;

  609.             //設置 prev
  610.             if(prev)
  611.             {
  612.                 p->Prev = prev;
  613.                 prev->Next = p;
  614.             }
  615.             else
  616.             {
  617.                 //prev 為空
  618.                 //where 為鍊錶頭
  619.                 _first = p;
  620.                 p->Prev = NULL;
  621.             }

  622.             //增加數量記錄
  623.             ++_size;

  624.         }
  625.         void insert_n(const_iterator where,const std::size_t n,const T& v) // throw std::bad_alloc
  626.         {
  627.             if(!n)
  628.             {
  629.                 return;
  630.             }

  631.             //申請新 節點
  632.             std::pair<PNODE,PNODE> range = create_range(n,v);


  633.             //連接節點
  634.             join(where,range,n);

  635.         }
  636.         template<typename Iterator>
  637.         void insert(const_iterator where,Iterator begin,Iterator end) //throw std::bad_alloc
  638.         {
  639.             //申請新 節點
  640.             std::size_t n;
  641.             std::pair<PNODE,PNODE> range = copy_range(begin,end,n);
  642.             if(!n)//[begin end) 為空
  643.             {
  644.                 return;
  645.             }

  646.             //連接節點
  647.             join(where,range,n);

  648.         }

  649.     protected:
  650.         template<typename Iterator>
  651.         void clear_insert(Iterator begin,Iterator end) //throw std::bad_alloc
  652.         {
  653.             //申請新 節點
  654.             std::size_t n;
  655.             std::pair<PNODE,PNODE> range = copy_range(begin,end,n);
  656.             if(!n)//[begin end) 為空
  657.             {
  658.                 return;
  659.             }

  660.             clear();

  661.             //連接節點
  662.             join(this->begin(),range,n);

  663.         }

  664.         template<typename Iterator>
  665.         std::pair<PNODE,PNODE> copy_range(Iterator begin,Iterator end,std::size_t& n) //throw std::bad_alloc
  666.         {
  667.             PNODE prev = NULL;
  668.             PNODE first = NULL;

  669.             n = 0;
  670.             for(;begin!=end;++begin)
  671.             {
  672.                 //申請新 節點
  673.                 PNODE p = create_node();
  674.                 if(!p)
  675.                 {
  676.                     destory_range(first);
  677.                     throw std::bad_alloc();
  678.                 }

  679.                 if(!first)
  680.                 {
  681.                     first = p;
  682.                 }

  683.                 p->Data = *begin;
  684.                 p->Next = NULL;
  685.                 if(prev)
  686.                 {
  687.                     prev->Next = p;
  688.                 }
  689.                 p->Prev = prev;

  690.                 prev = p;

  691.                 ++n;
  692.             }
  693.             return std::make_pair(first,prev);
  694.         }
  695.         void destory_range(PNODE first)
  696.         {
  697.             PNODE next;
  698.             while(first)
  699.             {
  700.                 next = first->Next;

  701.                 destory_node(first);

  702.                 first = next;
  703.             }
  704.         }

  705.         std::pair<PNODE,PNODE> create_range(std::size_t n,const T& v) //throw std::bad_alloc
  706.         {
  707.             PNODE prev = NULL;
  708.             PNODE first = NULL;

  709.             while(n)
  710.             {
  711.                 //申請新 節點
  712.                 PNODE p = create_node();
  713.                 if(!p)
  714.                 {
  715.                     destory_range(first);
  716.                     throw std::bad_alloc();
  717.                 }

  718.                 if(!first)
  719.                 {
  720.                     first = p;
  721.                 }

  722.                 p->Data = v;
  723.                 p->Next = NULL;
  724.                 if(prev)
  725.                 {
  726.                     prev->Next = p;
  727.                 }
  728.                 p->Prev = prev;

  729.                 prev = p;

  730.                 --n;
  731.             }
  732.             return std::make_pair(first,prev);
  733.         }
  734.         std::pair<PNODE,PNODE> create_range(std::size_t n) //throw std::bad_alloc
  735.         {
  736.             PNODE prev = NULL;
  737.             PNODE first = NULL;

  738.             while(n)
  739.             {
  740.                 //申請新 節點
  741.                 PNODE p = create_node();
  742.                 if(!p)
  743.                 {
  744.                     destory_range(first);
  745.                     throw std::bad_alloc();
  746.                 }

  747.                 if(!first)
  748.                 {
  749.                     first = p;
  750.                 }

  751.                 //p->Data = v;
  752.                 p->Next = NULL;
  753.                 if(prev)
  754.                 {
  755.                     prev->Next = p;
  756.                 }
  757.                 p->Prev = prev;

  758.                 prev = p;

  759.                 --n;
  760.             }
  761.             return std::make_pair(first,prev);
  762.         }
  763.         void insert_n(const_iterator where,const std::size_t n) // throw std::bad_alloc
  764.         {
  765.             if(!n)
  766.             {
  767.                 return;
  768.             }

  769.             //申請新 節點
  770.             std::pair<PNODE,PNODE> range = create_range(n);


  771.             //連接節點
  772.             join(where,range,n);

  773.         }
  774.         void join(const_iterator where, std::pair<PNODE,PNODE> range,std::size_t n)
  775.         {
  776.             //push back
  777.             if(where == this->end())
  778.             {
  779.                 if(_last)
  780.                 {
  781.                     _last->Next = range.first;
  782.                     range.first->Prev = _last;

  783.                     _last = range.second;
  784.                     _size += n;
  785.                 }
  786.                 else
  787.                 {
  788.                     //_last 不存在 鍊錶為空
  789.                     _first = range.first;
  790.                     _last = range.second;
  791.                     _size = n;
  792.                 }
  793.                 return;
  794.             }

  795.             //插入位置
  796.             PNODE p_i = where._p;

  797.             //設置 next
  798.             PNODE p = range.second;
  799.             p->Next = p_i;
  800.             PNODE prev = p_i->Prev;
  801.             p_i->Prev = p;

  802.             //設置 prev
  803.             p = range.first;
  804.             if(prev)
  805.             {
  806.                 p->Prev = prev;
  807.                 prev->Next = p;
  808.             }
  809.             else
  810.             {
  811.                 //prev 為空
  812.                 //where 為鍊錶頭
  813.                 _first = p;
  814.                 p->Prev = NULL;
  815.             }

  816.             //增加數量記錄
  817.             _size += n;
  818.         }
  819.     public:
  820.         //swap
  821.         inline void swap(list& right)
  822.         {
  823.             std::swap(_first,right._first);
  824.             std::swap(_last,right._last);
  825.             std::swap(_size,right._size);
  826.         }
  827.         //reverse
  828.         void reverse()
  829.         {
  830.             PNODE pos = _first;
  831.             PNODE next;
  832.             PNODE prev = NULL;
  833.             while(pos)
  834.             {
  835.                 next = pos->Next;

  836.                 pos->Prev = prev;
  837.                 pos->Next = NULL;

  838.                 prev = pos;
  839.                 pos = next;
  840.             }
  841.             std::swap(_first,_last);
  842.         }

  843.         //erase
  844.         iterator erase(const_iterator where)
  845.         {
  846.             PNODE p = where._p;
  847.             PNODE next = p->Next;
  848.             PNODE prev = p->Prev;

  849.             if(next)
  850.             {
  851.                 next->Prev = prev;
  852.             }
  853.             else
  854.             {
  855.                 //設置新的 尾節點
  856.                 _last = prev;
  857.             }


  858.             if(prev)
  859.             {
  860.                 prev->Next = next;
  861.             }
  862.             else
  863.             {
  864.                 //設置新的 頭節點
  865.                 _first = next;
  866.             }


  867.             //減少數量記錄
  868.             --_size;

  869.             return iterator(next,this);
  870.         }
  871.         iterator erase(const_iterator begin,const_iterator end)
  872.         {
  873.             if(begin == end)
  874.             {
  875.                 return iterator(begin._p,this);
  876.             }

  877.             std::size_t n = 0;

  878.             PNODE p_end = end._p;
  879.             PNODE p_begin = begin._p;


  880.             PNODE next = p_end;
  881.             PNODE prev = p_begin->Prev;

  882.             destory_range(p_begin,p_end);

  883.             if(next)
  884.             {
  885.                 next->Prev = prev;
  886.             }
  887.             else
  888.             {
  889.                 //設置新的 尾節點
  890.                 _last = prev;
  891.             }


  892.             if(prev)
  893.             {
  894.                 prev->Next = next;
  895.             }
  896.             else
  897.             {
  898.                 //設置新的 頭節點
  899.                 _first = next;
  900.             }


  901.             //減少數量記錄
  902.             _size -= n;

  903.             return iterator(p_end,this);
  904.         }

  905.     protected:
  906.         void destory_range(PNODE begin,PNODE end)
  907.         {
  908.             PNODE next;
  909.             while(begin != end /*&& begin*/)
  910.             {
  911.                 next = begin->Next;

  912.                 destory_node(begin);

  913.                 begin = next;
  914.             }
  915.         }
  916.     public:
  917.         //remove
  918.         void remove(const T& v)
  919.         {
  920.             iterator iter = begin();
  921.             while(iter != end())
  922.             {
  923.                 if(*iter == v)
  924.                 {
  925.                     iter = erase(iter);
  926.                 }
  927.                 else
  928.                 {
  929.                     ++iter;
  930.                 }
  931.             }
  932.         }

  933.         template<typename Compare>
  934.         void remove_if(Compare compare)
  935.         {
  936.             iterator iter = begin();
  937.             while(iter != end())
  938.             {
  939.                 if(compare(*iter))
  940.                 {
  941.                     iter = erase(iter);
  942.                 }
  943.                 else
  944.                 {
  945.                     ++iter;
  946.                 }
  947.             }
  948.         }


  949.         //sort
  950.         void sort() //throw std::bad_alloc
  951.         {
  952.             //sort
  953.             std::vector<T> v(_size);
  954.             std::size_t i = 0;
  955.             for(iterator iter = begin();iter!=end();++iter)
  956.             {
  957.                 v[i++] = *iter;
  958.             }
  959.             std::sort(v.begin(),v.end());


  960.             //set
  961.             i = 0;
  962.             for(iterator iter = begin();iter!=end();++iter)
  963.             {
  964.                 *iter = v[i++];
  965.             }
  966.         }
  967.         template<typename Compare>
  968.         void sort(Compare compare) //throw std::bad_alloc
  969.         {
  970.             //sort
  971.             std::vector<T> v(_size);
  972.             std::size_t i = 0;
  973.             for(iterator iter = begin();iter!=end();++iter)
  974.             {
  975.                 v[i++] = *iter;
  976.             }
  977.             std::sort(v.begin(),v.end(),compare);


  978.             //set
  979.             i = 0;
  980.             for(iterator iter = begin();iter!=end();++iter)
  981.             {
  982.                 *iter = v[i++];
  983.             }
  984.         }

  985.         //merge and sort
  986.         //right will clear
  987.         void merge(list& right) //throw std::bad_alloc
  988.         {
  989.             //sort
  990.             std::vector<T> v(_size + right.size());
  991.             std::size_t i = 0;
  992.             for(iterator iter = begin();iter!=end();++iter)
  993.             {
  994.                 v[i++] = *iter;
  995.             }
  996.             for(iterator iter = right.begin();iter!=right.end();++iter)
  997.             {
  998.                 v[i++] = *iter;
  999.             }
  1000.             std::sort(v.begin(),v.end());

  1001.             //insert
  1002.             insert_n(end(),right.size());
  1003.             right.clear();

  1004.             //set
  1005.             typename std::vector<T>::const_iterator iter_v = v.begin();
  1006.             for(iterator iter = begin();iter!=end();++iter)
  1007.             {
  1008.                 *iter = *iter_v;
  1009.                 ++iter_v;
  1010.             }

  1011.         }
  1012.         template<typename Compare>
  1013.         void merge(list& right,Compare compare) //throw std::bad_alloc
  1014.         {
  1015.             //sort
  1016.             std::vector<T> v(_size + right.size());
  1017.             std::size_t i = 0;
  1018.             for(iterator iter = begin();iter!=end();++iter)
  1019.             {
  1020.                 v[i++] = *iter;
  1021.             }
  1022.             for(iterator iter = right.begin();iter!=right.end();++iter)
  1023.             {
  1024.                 v[i++] = *iter;
  1025.             }
  1026.             std::sort(v.begin(),v.end(),compare);

  1027.             //insert
  1028.             insert_n(end(),right.size());
  1029.             right.clear();

  1030.             //set
  1031.             typename std::vector<T>::const_iterator iter_v = v.begin();
  1032.             for(iterator iter = begin();iter!=end();++iter)
  1033.             {
  1034.                 *iter = *iter_v;
  1035.                 ++iter_v;
  1036.             }

  1037.         }

  1038.     };


  1039. };
  1040. };

  1041. #endif // KING_LIB_HEADER_CONTAINER_LIST
复制代码

list.zip

5.26 KB, 下载次数: 0, 下载积分: 驿站币 -1

源碼





上一篇:谈谈个人学习《windows核心编程》的感想!
下一篇:开山斧0.3.5(跨平台版本)《源码已开放》
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-4-19 11:28

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表