devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

(第二步) STL: stl_list容器的实现_reference back() { return _tail()->item; }

作者：很楠不爱3 | 2024-02-22 02:17:13

赞

踩

reference back() { return _tail()->item; }

stl_list容器

工具：visual studio 2019

STL标准模板库中实现的是双向环形链表，这里就实现了普通双向链表

在stl_list.impl.h部分做了详细的注释

实现功能

基本功能实现：
list.back()         返回最后一个元素 
list.begin()         返回指向第一个元素的迭代器 
list.clear()         删除所有元素 
list.empty()         如果list是空的则返回true 
list.end()             返回末尾的迭代器 
list.erase()         删除一个元素 
list.front()         返回第一个元素 
list.insert()         插入一个元素到list中
list.pop_back()     删除最后一个元素 
list.pop_front()     删除第一个元素 
list.push_back()     在list的末尾添加一个元素 
list.push_front()     在list的头部添加一个元素
list.resize()         改变list的大小
list.size()         返回list中的元素个数
list.swap()         交换两个list 

丰富功能函数的实现：
list.splice()         直接合并两个list 
list.merge()         默认按小到大，合并两个list 
list.rbegin()         返回指向第一个元素的逆向迭代器 
list.rend()         指向list末尾的逆向迭代器
list.remove()         从list删除元素 
list.remove_if()    按指定条件删除元素 
list.unique()         删除list中重复的元素
list.reverse()         把list的元素倒转 
list.sort()         给list排序 

stl_list.h

  1.  #ifndef _LIST_H_
  2.  #define _LIST_H_
  3.  ​
  4.  #include "../Includes/Allocator.h"
  5.  #include "../Includes/Iterator.h"
  6.  #include "../Includes/ReverseIterator.h"
  7.  #include "../Includes/UninitializedFunctions.h"
  8.  #include "../Includes/Utility.h"
  9.  ​
  10.  #include <type_traits>
  11.  ​
  12.  namespace mySTL {
  13.      template<class T>
  14.      class list;
  15.      namespace detail {
  16.          // 设置链表的每个节点
  17.          template<class T>
  18.          struct node {
  19.              T data;
  20.              node* prev;
  21.              node* next;
  22.  ​
  23.              node(const T& d, node* p, node* n) :
  24.                  data(d), prev(p), next(n){}
  25.  ​
  26.              // 节点相等的情况
  27.              bool operator ==(const node& n) {
  28.                  return data == n.data && prev == n.prev && next == n.next;
  29.              }
  30.          };
  31.  ​
  32.          // 迭代器类型
  33.          template<class T>
  34.          struct listIterator :public iterator<bidirectional_iterator_tag, T> {
  35.                  template<class T>
  36.                  friend class list;          //友元访问，互相为好基友，相互访问
  37.              public:
  38.                  typedef node<T>* nodePtr;
  39.                  nodePtr p;
  40.  ​
  41.              public:
  42.                  explicit listIterator(nodePtr ptr = nullptr):p(ptr){}
  43.  ​
  44.                  listIterator& operator++();                      //++i
  45.                  listIterator operator++(int);                    //i++
  46.                  listIterator& operator--();                     //
  47.                  listIterator operator--(int);                    //
  48.  ​
  49.                  T& operator *() { return p->data; }
  50.                  T* operator ->() { return &(operator*()); }
  51.                  
  52.  ​
  53.                  // 友元函数必须类内定义、类外声明（不确定，但是类内声明实现不了int以外的类型）
  54.                  template<class T>
  55.                  friend bool operator==(const listIterator<T>& lhs, const listIterator<T>& rhs); 
  56.  ​
  57.                  template<class T>
  58.                  friend bool operator!=(const listIterator<T>& lhs, const listIterator<T>& rhs);
  59.  ​
  60.              };
  61.          }
  62.  ​
  63.      template<class T>
  64.      class list {
  65.          template<class T>
  66.          friend struct listIterator;             //友元，互相为好基友
  67.      private:
  68.          typedef allocator<detail::node<T>>      nodeAllocator;
  69.          typedef detail::node<T>*                nodePtr;
  70.  ​
  71.      public:
  72.          typedef T                               value_type;
  73.          typedef detail::listIterator<T>         iterator;
  74.          typedef detail::listIterator<const T>   const_iterator;
  75.          typedef reverse_iterator_t<iterator>    reverse_iterator;
  76.          typedef T&                              reference;
  77.          typedef size_t                          size_type;
  78.      private:
  79.          iterator head;
  80.          iterator tail;
  81.  ​
  82.          nodePtr newNode(const T& val = T());
  83.          void deleteNode(nodePtr p);
  84.  ​
  85.      public:
  86.          // 构造和析构函数
  87.          list();
  88.          explicit list(size_type n, const value_type& val = value_type());
  89.          template <class InputIterator>
  90.          list(InputIterator first, InputIterator last);
  91.          // 注意，这里使用的是浅拷贝
  92.          list(const list& l);
  93.          list& operator=(const list& l);
  94.  ​
  95.          ~list();
  96.      
  97.          // 查看元素
  98.      public:
  99.          bool empty()const { return head == tail; }
  100.          size_type size()const;
  101.          reference front() { return (head.p->data); }
  102.          reference back() { return (tail.p->prev->data); }
  103.  ​
  104.          iterator begin() { return head; }
  105.          iterator end() { return tail; }
  106.  ​
  107.          // 逆序迭代器，拓展功能
  108.          reverse_iterator rbegin();
  109.          reverse_iterator rend();
  110.  ​
  111.          // 元素操作的基本操作
  112.      public:
  113.          void push_front(const value_type& val);
  114.          void pop_front();
  115.          void push_back(const value_type& val);
  116.          void pop_back();
  117.  ​
  118.          iterator insert(iterator position, const value_type& val);
  119.          void insert(iterator position, size_type n, const value_type& val);
  120.          template <class InputIterator>
  121.          void insert(iterator position, InputIterator first, InputIterator last);
  122.          iterator erase(iterator position);
  123.          iterator erase(iterator first, iterator last);
  124.          void clear(); ​        
  125.          void swap(list& x);
  126.  
  127.          // 拓展丰富功能
  128.          void splice(iterator position, list& x);        
  129.          void splice(iterator position, list& x, iterator first, iterator last);
  130.          void splice(iterator position, list& x, iterator i);
  131.          void merge(list& x);
  132.          template <class Compare>
  133.          void merge(list& x, Compare comp);
  134.  ​
  135.          void remove(const value_type& val);
  136.          template <class Predicate>
  137.          void remove_if(Predicate pred);
  138.          void unique();
  139.          template <class BinaryPredicate>
  140.          void unique(BinaryPredicate binary_pred);
  141.          void sort();
  142.          template <class Compare>
  143.          void sort(Compare comp);
  144.          void reverse();
  145.  ​
  146.          // 辅助函数
  147.      private:
  148.          void ctorAux(size_type n, const value_type& val, std::true_type);
  149.          template <class InputIterator>
  150.          void ctorAux(InputIterator first, InputIterator last, std::false_type);     
  151.          void insert_aux(iterator position, size_type n, const T& val, std::true_type);
  152.          template<class InputIterator>
  153.          void insert_aux(iterator position, InputIterator first, InputIterator last, std::false_type);
  154.  ​
  155.      public:
  156.          template<class T>
  157.          friend void swap(list<T>& x, list<T>& y);
  158.          template <class T>
  159.          friend bool operator== (const list<T>& lhs, const list<T>& rhs);
  160.          template <class T>
  161.          friend bool operator!= (const list<T>& lhs, const list<T>& rhs);
  162.      };
  163.  }
  164.  ​
  165.  #include "../Detail/stl_list.impl.h"
  166.  ​
  167.  #endif

stl_list.impl.h

  1.  #include "..\p2_STL_Source\stl_list.h"
  2.  ​
  3.  #ifndef _LIST_IMPL_H_
  4.  #define _LIST_IMPL_H_
  5.  ​
  6.  namespace mySTL {
  7.      namespace detail {
  8.          // 实现重载++,--功能
  9.          template<class T>
  10.          inline listIterator<T>& listIterator<T>::operator++()
  11.          {
  12.              p = p->next;
  13.              return *this;
  14.          }
  15.  ​
  16.          template<class T>
  17.          inline listIterator<T> listIterator<T>::operator++(int)
  18.          {
  19.              auto res = *this;
  20.              p = p->next;
  21.              return res;
  22.          }
  23.  ​
  24.          template<class T>
  25.          inline listIterator<T>& listIterator<T>::operator--()
  26.          {
  27.              p = p->prev;
  28.              return *this;
  29.          }
  30.  ​
  31.          template<class T>
  32.          inline listIterator<T> listIterator<T>::operator--(int)
  33.          {
  34.              auto res = *this;
  35.              p = p->prev;
  36.              return res;
  37.          }
  38.  ​
  39.          template<class T>
  40.          bool operator ==(const listIterator<T>& lhs, const listIterator<T>& rhs) {
  41.              return lhs.p == rhs.p;
  42.          }
  43.  ​
  44.          template<class T>
  45.          bool operator !=(const listIterator<T>& lhs, const listIterator<T>& rhs) {
  46.              return !(lhs == rhs);
  47.          }
  48.  ​
  49.      }
  50.  ​
  51.      // 构造、拷贝、析构函数
  52.      // 新建节点
  53.      template<class T>
  54.      inline typename list<T>::nodePtr list<T>::newNode(const T& val)
  55.      {
  56.          // 申请空间
  57.          nodePtr res = nodeAllocator::allocate();
  58.          // 初始化节点
  59.          nodeAllocator::construct(res, detail::node<T>(val, nullptr, nullptr));
  60.  ​
  61.          return res;
  62.      }
  63.  ​
  64.      // 无参构造，新建一个节点，head == tail
  65.      template<class T>
  66.      list<T>::list()
  67.      {
  68.          head.p = newNode(); // 虚假节点dummy
  69.          tail.p = head.p;
  70.      }
  71.  ​
  72.  ​
  73.      // 删除节点
  74.      template<class T>
  75.      inline void list<T>::deleteNode(nodePtr p)
  76.      {
  77.          p->prev = p->next = nullptr;
  78.          nodeAllocator::destroy(p);      // 调用p的析构
  79.          nodeAllocator::deallocate(p);   // free空间释放
  80.      }
  81.  ​
  82.      // 析构
  83.      template<class T>
  84.      inline list<T>::~list()
  85.      {
  86.          while (head != tail)
  87.          {
  88.              auto temp = head++;
  89.              nodeAllocator::destroy(temp.p);     // 调用p的析构
  90.              nodeAllocator::deallocate(temp.p);  // free空间释放
  91.          }
  92.          nodeAllocator::destroy(tail.p);     // 调用p的析构
  93.          nodeAllocator::deallocate(tail.p);  // free空间释放
  94.      }
  95.  ​
  96.      /************************查看元素**************************/
  97.  ​
  98.      template<class T>
  99.      typename list<T>::size_type list<T>::size()const
  100.      {
  101.          size_type len = 0;
  102.          for (auto h = head; h != tail; ++h)
  103.          {
  104.              ++len;
  105.          }
  106.  ​
  107.          return len;
  108.      }
  109.  ​
  110.      /************************元素基本操作**************************/
  111.      /****************实现push、pop、insert、erase、clear功能************************/
  112.      template<class T>
  113.      inline void list<T>::push_front(const value_type& val)
  114.      {
  115.          auto node = newNode(val);
  116.          head.p->prev = node;
  117.          node->next = head.p;
  118.          head.p = node;
  119.      }
  120.  ​
  121.      template<class T>
  122.      void list<T>::pop_front() 
  123.      {
  124.          auto oldNode = head.p;
  125.          head.p = oldNode->next;
  126.          head.p->prev = nullptr;
  127.          deleteNode(oldNode);
  128.      }
  129.  ​
  130.      template<class T>
  131.      inline void list<T>::push_back(const value_type& val)
  132.      {
  133.          auto node = newNode(val);
  134.          tail.p->data = val;
  135.          tail.p->next = node;
  136.          node->prev = tail.p;
  137.          tail.p = node;
  138.      }
  139.  ​
  140.      template<class T>
  141.      void list<T>::pop_back() 
  142.      {
  143.          auto oldNode = tail.p;
  144.          tail.p = oldNode->prev;
  145.          tail.p->next = nullptr;
  146.          deleteNode(oldNode);
  147.      }
  148.  ​
  149.      template<class T>
  150.      inline typename list<T>::iterator list<T>::insert(iterator position, const value_type& val)
  151.      {
  152.          if (position == begin())
  153.          {
  154.              push_front(val);
  155.              return begin();
  156.          }
  157.          else if (position == end())
  158.          {
  159.              push_back(val);
  160.              auto ret = position;
  161.              return ret;
  162.          }
  163.  ​
  164.          auto node = newNode(val);
  165.          auto prev = position.p->prev;
  166.          node->next = position.p;        
  167.          node->prev = prev;
  168.          prev->next = node;
  169.          position.p->prev = node;
  170.  ​
  171.          return iterator(node);
  172.      }
  173.  ​
  174.      template<class T>
  175.      inline typename list<T>::iterator list<T>::erase(iterator position)
  176.      {
  177.          if (position == head)
  178.          {
  179.              pop_front();
  180.              return head;
  181.          }
  182.          else
  183.          {
  184.              auto prev = position.p->prev;
  185.              prev->next = position.p->next;
  186.              position.p->next->prev = prev;
  187.              deleteNode(position.p);
  188.              return iterator(prev->next);
  189.          }
  190.      }
  191.  ​
  192.      template<class T>
  193.      inline typename list<T>::iterator list<T>::erase(iterator first, iterator last)
  194.      {
  195.          typename list<T>::iterator ret;
  196.          while (first != last)
  197.          {
  198.              auto temp = first++;
  199.              ret = erase(temp);
  200.          }
  201.  ​
  202.          return ret;
  203.      }
  204.  ​
  205.      template<class T>
  206.      void list<T>::clear()
  207.      {
  208.          erase(begin(), end());
  209.      }
  210.  ​
  211.      /***********************基本功能实现完毕，深入拓展************************/
  212.      
  213.      // 有参构造，和两个辅助函数ctorAux
  214.      template<class T>
  215.      inline list<T>::list(size_type n, const value_type& val)
  216.      {
  217.          ctorAux(n, val, std::is_integral<value_type>());
  218.      }
  219.  ​
  220.      template<class T>
  221.      template<class InputIterator>
  222.      inline list<T>::list(InputIterator first, InputIterator last)
  223.      {
  224.          ctorAux(first, last, std::is_integral<InputIterator>());
  225.      }
  226.  ​
  227.      template<class T>
  228.      inline void list<T>::ctorAux(size_type n, const value_type& val, std::true_type)
  229.      {
  230.          head.p = newNode(); // 虚假节点dummy
  231.          tail.p = head.p;
  232.  ​
  233.          while (n--)
  234.              push_back(val);
  235.      }
  236.  ​
  237.      // 实现插入一段list
  238.      template<class T>
  239.      template<class InputIterator>
  240.      inline void list<T>::ctorAux(InputIterator first, InputIterator last, std::false_type)
  241.      {
  242.          head.p = newNode(); // 虚假节点dummy
  243.          tail.p = head.p;
  244.  ​
  245.          for (; first != last; ++first)
  246.          {
  247.              push_back(*first);
  248.          }
  249.      }
  250.  ​
  251.      // 拷贝构造函数 浅拷贝
  252.      template<class T>
  253.      list<T>::list(const list& l)
  254.      {
  255.          head.p = newNode();
  256.          tail.p = head.p;
  257.  ​
  258.          for (auto node = l.head.p; node != l.tail.p; ++node)
  259.          {
  260.              push_back(node->data);
  261.          }
  262.      }
  263.  ​
  264.      template<class T>
  265.      typename list<T>& list<T>::operator=(const list& l) 
  266.      {
  267.          if (this != &l)
  268.          {
  269.              list(l).swap(*this);    // 先使用L2(L1)构造函数，然后再进行swap进行copy
  270.          }
  271.          return *this;
  272.      }
  273.  ​
  274.      template<class T>
  275.      void list<T>::swap(list& x)
  276.      {
  277.          mySTL::swap(head.p, x.head.p);  // 值交换
  278.          mySTL::swap(tail.p, x.tail.p);
  279.      }
  280.  ​
  281.      
  282.  ​
  283.      template<class T>
  284.      void swap(list<T>& x, list<T>& y)
  285.      {
  286.          x.swap(y);
  287.      }
  288.  ​
  289.      // insert多项插入，两个辅助函数insert_aux
  290.      template<class T>
  291.      inline void list<T>::insert(iterator position, size_type n, const value_type& val)
  292.      {
  293.          insert_aux(position, n, val, typename std::is_integral<value_type>::type());
  294.      }
  295.  ​
  296.      template<class T>
  297.      template<class InputIterator>
  298.      inline void list<T>::insert(iterator position, InputIterator first, InputIterator last)
  299.      {
  300.          insert_aux(position, first, last, typename std::is_integral<InputIterator>::type());
  301.      }
  302.  ​
  303.      
  304.  ​
  305.      template<class T>
  306.      inline void list<T>::insert_aux(iterator position, size_type n, const T& val, std::true_type)
  307.      {
  308.          for (auto i = n; i != 0; --i)
  309.          {
  310.              position = insert(position, val);
  311.          }
  312.      }
  313.  ​
  314.      template<class T>
  315.      template<class InputIterator>
  316.      inline void list<T>::insert_aux(iterator position, InputIterator first, InputIterator last, std::false_type)
  317.      {
  318.          for (--last; first != last; --last)     // last为end，没有元素值，需要变为back
  319.          {
  320.              position = insert(position, *last); // 逆序插入，insert返回为插入的元素地址
  321.          }
  322.          insert(position, *last);
  323.      }
  324.  ​
  325.      /***********************丰富构造函数、插入函数，接下来进行功能拓展************************/
  326.      // 合并两个list 
  327.      template<class T>
  328.      inline void list<T>::splice(iterator position, list& x)
  329.      {
  330.          this->insert(position, x.begin(), x.end());
  331.          x.head.p = x.tail.p;
  332.      }
  333.  ​
  334.      template<class T>
  335.      inline void list<T>::splice(iterator position, list& x, iterator first, iterator last)
  336.      {
  337.          if (first.p == last.p) return;
  338.  ​
  339.          auto tailNode = last.p->prev;
  340.          // list x的处理，合并后删除对应元素
  341.          if (x.head.p == first.p)
  342.          {
  343.              x.head.p = last.p;
  344.              x.head.p->prev = nullptr;
  345.          }
  346.          else
  347.          {
  348.              first.p->prev->next = last.p;
  349.              last.p->prev = first.p->prev;
  350.          }
  351.  ​
  352.          // 开始合并
  353.          if (position.p == head.p)
  354.          {
  355.              first.p->prev = nullptr;
  356.              tailNode->next = head.p;
  357.              head.p->prev = tailNode;
  358.              head.p = first.p;
  359.          }
  360.          else
  361.          {
  362.              position.p->prev->next = first.p;
  363.              first.p->prev = position.p->prev;
  364.  ​
  365.              tailNode->next = position.p;
  366.              position.p->prev = tailNode;
  367.          }
  368.      }
  369.  ​
  370.      // 指定位置元素的合并
  371.      template<class T>
  372.      inline void list<T>::splice(iterator position, list& x, iterator i)
  373.      {
  374.          auto next = i;
  375.          this->splice(position, x, i, ++next);
  376.      }
  377.  ​
  378.      // 排序合并两个list 
  379.      template<class T>
  380.      void list<T>::merge(list& x)
  381.      {
  382.          auto it1 = begin(), it2 = x.begin();
  383.          while (it1 != end() && it2 != x.end())
  384.          {
  385.              if (*it1 <= *it2)
  386.              {
  387.                  ++it1;
  388.              }
  389.              else
  390.              {
  391.                  auto temp = it2++;
  392.                  this->splice(it1, x, temp);
  393.              }
  394.          }
  395.  ​
  396.          if (it1 == end())
  397.          {
  398.              this->splice(it1, x, it2, x.end());
  399.          }
  400.      }
  401.  ​
  402.      template<class T>
  403.      template<class Compare>
  404.      inline void list<T>::merge(list& x, Compare comp)
  405.      {
  406.          auto it1 = begin(), it2 = x.begin();
  407.          while (it1 != end() && it2 != x.end())
  408.          {
  409.              if (comp(*it2, *it1))
  410.              {
  411.                  auto temp = it2++;
  412.                  this->splice(it1, x, temp);             
  413.              }
  414.              else
  415.              {
  416.                  ++it1;
  417.              }
  418.          }
  419.  ​
  420.          if (it1 == end())
  421.          {
  422.              this->splice(it1, x, it2, x.end());
  423.          }
  424.      }
  425.  ​
  426.      // 从list删除元素 或 指定条件删除
  427.      template<class T>
  428.      inline void list<T>::remove(const value_type& val)
  429.      {
  430.          for (auto it = begin(); it != end();)
  431.          {
  432.              if (*it == val)
  433.                  it = erase(it);
  434.              else
  435.                  ++it;
  436.          }
  437.      }
  438.  ​
  439.      template<class T>
  440.      template<class Predicate>
  441.      inline void list<T>::remove_if(Predicate pred)
  442.      {
  443.          for (auto it = begin(); it != end();) 
  444.          {
  445.              if (pred(*it))
  446.                  it = erase(it);
  447.              else
  448.                  ++it;
  449.          }
  450.      }
  451.  ​
  452.      //  删除list中相邻重复的元素
  453.      template<class T>
  454.      void list<T>::unique()
  455.      {
  456.          nodePtr curNode = head.p;
  457.  ​
  458.          while (curNode != tail.p->prev)
  459.          {
  460.              nodePtr nextNode = curNode->next;
  461.  ​
  462.              if (curNode->data == nextNode->data)
  463.              {
  464.                  if (nextNode == tail.p)
  465.                  {
  466.                      curNode->next = nullptr;
  467.                      tail.p = curNode;
  468.                  }
  469.                  else
  470.                  {
  471.                      curNode->next = nextNode->next;
  472.                      nextNode->next->prev = curNode;
  473.                  }
  474.                  deleteNode(nextNode);
  475.              }
  476.              else
  477.              {
  478.                  curNode = nextNode;
  479.              }
  480.          }
  481.      }
  482.  ​
  483.      template<class T>
  484.      template<class BinaryPredicate>
  485.      inline void list<T>::unique(BinaryPredicate binary_pred)
  486.      {
  487.      }
  488.  ​
  489.      // 给list排序 
  490.      template<class T>
  491.      void list<T>::sort()
  492.      {
  493.          sort(mySTL::less<T>());
  494.      }
  495.  ​
  496.      template<class T>
  497.      template<class Compare>
  498.      inline void list<T>::sort(Compare comp)
  499.      {
  500.          // 侯捷书说是：快速排序， 个人认为更像是归并排序
  501.          // 空链表和只有一个元素不进行操作
  502.          if (empty() || head.p->next == tail.p) return;
  503.  ​
  504.          // 一些新的lists，作为中介数据存放区
  505.          list carry;         // 临时变量
  506.          list counter[64];   // 可以储存2^64 - 1数据
  507.          int fill = 0;       // 数据放置了小于2^fill - 1个数据
  508.          
  509.          while (!empty())
  510.          {
  511.              carry.splice(carry.begin(), *this, begin());    // carry每次获取一个数据
  512.              int i = 0;
  513.  ​
  514.              while (i < fill && !counter[i].empty())
  515.              {
  516.                  counter[i].merge(carry, comp);              // 归并
  517.                  carry.swap(counter[i++]);                   // 数据临时存放至carry
  518.              }
  519.  ​
  520.              carry.swap(counter[i]);
  521.  ​
  522.              if (i == fill)                                  // 数据增加最多2^fill - 1个数据
  523.                  ++fill;
  524.          }
  525.          // 归并所有项
  526.          for (int i = 1; i != fill; ++i)
  527.          {
  528.              counter[i].merge(counter[i - 1], comp);
  529.          }
  530.          // 返回原先的变量
  531.          swap(counter[fill - 1]);
  532.          
  533.      }
  534.  ​
  535.      //  把list的元素倒转
  536.      template<class T>
  537.      typename list<T>::reverse_iterator list<T>::rbegin()
  538.      {
  539.          return reverse_iterator(tail);
  540.      }
  541.  ​
  542.      template<class T>
  543.      typename list<T>::reverse_iterator list<T>::rend() {
  544.          return reverse_iterator(head);
  545.      }
  546.  ​
  547.      template<class T>
  548.      void list<T>::reverse() //采用尾插法
  549.      {
  550.          if (empty() || head.p->next == tail.p) return;
  551.          auto curNode = head.p;
  552.          head.p = tail.p->prev;
  553.          head.p->prev = nullptr;
  554.  ​
  555.          do {
  556.              auto nextNode = curNode->next;
  557.              
  558.              curNode->next = head.p->next;
  559.              head.p->next->prev = curNode;
  560.              curNode->prev = nextNode;
  561.  ​
  562.              // 更新
  563.              head.p->next = curNode;         
  564.              curNode = nextNode;
  565.  ​
  566.          } while (curNode != head.p);
  567.  ​
  568.      }
  569.  ​
  570.      // 拓展 == 、！=
  571.      template<class T>
  572.      bool operator==(const list<T>& lhs, const list<T>& rhs)
  573.      {
  574.          auto node1 = lhs.head.p, node2 = rhs.head.p;
  575.          while ( node1 != lhs.tail.p && node2 != rhs.tail.p ) 
  576.          {
  577.              if (node1->data != node2->data)
  578.                  break;
  579.              node1 = node1->next, node2 = node2->next;
  580.          }
  581.          if (node1 == lhs.tail.p && node2 == rhs.tail.p)
  582.              return true;
  583.          return false;
  584.      }
  585.  ​
  586.      template<class T>
  587.      bool operator!=(const list<T>& lhs, const list<T>& rhs)
  588.      {
  589.          return !(lhs == rhs);
  590.      }
  591.  ​
  592.  }
  593.  #endif

sort案例解析

sort算法流程：

stl_list_test.h

 
  1. #ifndef _LIST_TEST_H_
  2.  #define _LIST_TEST_H_
  3.  ​
  4.  #include "../p2_STL_Source/stl_list.h"
  5.  #include <list>
  6.  ​
  7.  #include <cassert>
  8.  #include <functional>
  9.  #include <string>
  10.  #include <random>
  11.  #include <time.h>
  12.  ​
  13.  namespace mySTL {
  14.      namespace listTest {
  15.          template<class T>
  16.          using stdL = std::list<T>;
  17.          template<class T>
  18.          using myL = mySTL::list<T>;
  19.  ​
  20.          template<class T>
  21.          void stdPrint(std::list<T>& l);
  22.          template<class T>
  23.          void myPrint(mySTL::list<T>& l);
  24.          void test01();  // 完成无参构造，和size、emptys push pop功能测试，继续拓展
  25.          void test02();  // 完成insert erase clear 完成基本功能
  26.          void test03();  // 深入拓展，有参构造 拷贝构造 多项insert
  27.          void test04();  // splice merge
  28.          void test05();  // remove remove_if unique
  29.          void test06();  // sort reverse
  30.      }
  31.  }
  32.  ​
  33.  #endif

stl_list_test.cpp

这个测试函数你可以自己写

  1.  #include "stl_list_test.h"
  2.  ​
  3.  using namespace std;
  4.  ​
  5.  namespace mySTL {
  6.      namespace listTest {
  7.          template<class T>
  8.          void stdPrint(std::list<T>& l)
  9.          {
  10.              cout << "stdSTL: ";
  11.              for (auto i = l.begin(); i != l.end(); i++)
  12.              {
  13.                  
  14.                  cout << *i <<"  ";
  15.              }
  16.              cout << endl;
  17.          }
  18.          template<class T>
  19.          void myPrint(mySTL::list<T>& l)
  20.          {
  21.              cout << "mySTL:  ";
  22.              for (auto i = l.begin(); i != l.end(); i++)
  23.              {
  24.                  cout << *i << "  ";
  25.              }
  26.              cout << endl;
  27.          }
  28.  ​
  29.          void test01()
  30.          {
  31.              stdL<int> l1;
  32.              myL<int> l2;
  33.              cout << "-------------create test----------" << endl;
  34.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  35.              cout << "l1: " << l1.empty() << "\tl2: " << l2.empty() << endl;
  36.  ​
  37.              l1.push_front(2);
  38.              l2.push_front(3);
  39.              l1.push_back(10);
  40.              l2.push_back(12);
  41.              l1.push_back(100);
  42.              l2.push_back(112);
  43.              cout << "-------------push test----------" << endl;
  44.              cout << "l1: " << l1.front() << "\tl2: " << l2.front() << endl;
  45.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  46.              cout << "l1: " << l1.back() << "\tl2: " << l2.back() << endl;
  47.  ​
  48.  ​
  49.              l1.pop_front();
  50.              l2.pop_front();
  51.              l1.pop_back();
  52.              l2.pop_back();
  53.              cout << "-------------pop test----------" << endl;
  54.              cout << "l1: " << l1.front() << "\tl2: " << l2.front() << endl;
  55.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  56.              cout << "l1: " << l1.back() << "\tl2: " << l2.back() << endl;
  57.  ​
  58.              stdL<string> l3;
  59.              myL<string> l4;
  60.              
  61.              cout << "-------------string type test----------" << endl;
  62.              cout << boolalpha << "l1: " << l3.empty() << "\tl2: " << l4.empty() << endl;
  63.              l3.push_back("xfy");
  64.              l4.push_back("xfy");
  65.              cout << "l3: " << l3.front() << "\tl4: " << l4.front() << endl;
  66.  ​
  67.              cout << "-------------string type 2 test----------" << endl;
  68.              std::string arr[] = { "1", "2", "3" };
  69.              myL<std::string> l(std::begin(arr), std::end(arr));
  70.              l.front() = "front";
  71.              l.back() = "back";
  72.  ​
  73.              myPrint(l);
  74.          }
  75.          void test02()
  76.          {
  77.              stdL<int> l1;
  78.              myL<int> l2;
  79.              l1.push_front(2);
  80.              l2.push_front(3);
  81.              l1.push_back(10);
  82.              l2.push_back(12);
  83.              l1.push_back(100);
  84.              l2.push_back(112);
  85.  ​
  86.              cout << "-------------print test----------" << endl;
  87.              stdPrint(l1);
  88.              myPrint(l2);
  89.  ​
  90.              cout << "-------------insert test----------" << endl;
  91.              auto tmpL1 = l1.begin();
  92.              l1.insert(++tmpL1, 20);
  93.              tmpL1 = l1.end();
  94.              l1.insert(--tmpL1, 20);
  95.              stdPrint(l1);
  96.              auto tmpL2 = l2.begin();
  97.              l2.insert(++tmpL2, 30);
  98.              tmpL2 = l2.end();
  99.              l2.insert(--tmpL2, 30);
  100.              myPrint(l2);
  101.  ​
  102.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  103.  ​
  104.              cout << "-------------erase test----------" << endl;
  105.              l1.insert(--tmpL1, 20);
  106.              l1.insert(--tmpL1, 60);
  107.              l1.insert(--tmpL1, 70);
  108.              stdPrint(l1);
  109.              l2.insert(--tmpL2, 40);
  110.              l2.insert(--tmpL2, 50);
  111.              l2.insert(--tmpL2, 30);
  112.              myPrint(l2);
  113.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  114.  ​
  115.              tmpL1 = l1.begin();
  116.              tmpL2 = l2.begin();
  117.  ​
  118.              l1.erase(++tmpL1);
  119.              l2.erase(++tmpL2);
  120.              stdPrint(l1);           
  121.              myPrint(l2);
  122.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  123.  ​
  124.              l1.erase(++l1.begin(), --l1.end());
  125.              l2.erase(++l2.begin(), --l2.end());
  126.              stdPrint(l1);
  127.              myPrint(l2);
  128.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  129.  ​
  130.              cout << "-------------clear test----------" << endl;
  131.              l1.clear();
  132.              l2.clear();
  133.              stdPrint(l1);
  134.              myPrint(l2);
  135.              cout << "l1: " << l1.size() << "\tl2: " << l2.size() << endl;
  136.          }
  137.  ​
  138.          void test03()
  139.          {
  140.              stdL<int> l1(10, 6);
  141.              myL<int> l2(10, 7);
  142.  ​
  143.              cout << "-------------param constructor test----------" << endl;
  144.              stdPrint(l1);
  145.              myPrint(l2);
  146.  ​
  147.              cout << "-------------copy constructor test----------" << endl;
  148.              stdL<int> l3(l1.begin(), l1.end());
  149.              myL<int> l4(l2.begin(), l2.end());
  150.              stdPrint(l3);
  151.              myPrint(l4);
  152.  ​
  153.              cout << "------------- copy2 test----------" << endl;
  154.              auto l5(l1);
  155.              auto l6(l2);
  156.              stdPrint(l5);
  157.              myPrint(l6);
  158.  ​
  159.              cout << "------------- copy3( = ) test----------" << endl;
  160.              auto l7 = l1;
  161.              auto l8 = l2;
  162.              stdPrint(l7);
  163.              myPrint(l8);
  164.  ​
  165.              cout << "------------- insert1 test----------" << endl;
  166.              l7.insert(++l7.begin(), 3, 3);
  167.              l8.insert(++l8.begin(), 3, 4);
  168.              stdPrint(l7);
  169.              myPrint(l8);
  170.  ​
  171.  ​
  172.  ​
  173.              cout << "------------- insert2 test----------" << endl;
  174.              stdL<int> l9(5, 9);
  175.              myL<int> l10(5, 8);
  176.              l7.insert(++l7.begin(), l9.begin(), l9.end());
  177.              l8.insert(++l8.begin(), l10.begin(), l10.end());
  178.              stdPrint(l7);
  179.              myPrint(l8);
  180.  ​
  181.          }
  182.  ​
  183.          void test04()
  184.          {
  185.              cout << "------------- splice test----------" << endl;
  186.              std::string arr1[] = { "1", "2", "3" };
  187.              myL<std::string> l1(std::begin(arr1), std::end(arr1));
  188.  ​
  189.              std::string arr2[] = { "4", "5", "6", "a", "b", "c" };
  190.              myL<std::string> l2(std::begin(arr2), std::end(arr2));
  191.  ​
  192.              
  193.              
  194.              cout << "------------- raw print test----------" << endl;
  195.              myPrint(l1);
  196.              myPrint(l2);
  197.              cout << "------------- splice1 print test----------" << endl;
  198.              l1.splice(l1.end(), l2, l2.begin());
  199.              myPrint(l1);
  200.              myPrint(l2);
  201.              cout << "------------- splice2 print test----------" << endl;
  202.              auto tmp = l2.begin();
  203.              for (int i = 3; i >= 0; --i) ++tmp;
  204.              l1.splice(l1.end(), l2, l2.begin(), tmp);
  205.              myPrint(l1);
  206.              myPrint(l2);
  207.              cout << "------------- splice3 print test----------" << endl;
  208.              l1.splice(l1.end(), l2);
  209.              myPrint(l1);
  210.              myPrint(l2);
  211.  ​
  212.              cout << "------------- merge  test----------" << endl;
  213.              myL<int> l3, l4;
  214.              myL<int> l5, l6;
  215.              srand(time(NULL));
  216.              for (int i = 0; i < 10; ++i)
  217.              {
  218.                  int tmp = rand() % 10 + 1;
  219.                  l3.push_back(tmp);
  220.                  l5.push_back(tmp);
  221.              }
  222.              for (int i = 0; i < 10; ++i)
  223.              {
  224.                  int tmp = rand() % 10 + 1;
  225.                  l4.push_back(tmp);
  226.                  l6.push_back(tmp);
  227.              }
  228.              
  229.              cout << "------------- raw print test----------" << endl;
  230.              myPrint(l3);
  231.              myPrint(l4);
  232.              cout << "------------- merge1  test----------" << endl;
  233.              l3.merge(l4);
  234.              myPrint(l3);
  235.              myPrint(l4);
  236.  ​
  237.              cout << "------------- raw print test----------" << endl;
  238.              myPrint(l5);
  239.              myPrint(l6);
  240.              cout << "------------- merge2 comp  test----------" << endl;
  241.              l5.merge(l6, [](int x, int y) {return x > y; });
  242.              myPrint(l5);
  243.              myPrint(l6);
  244.              
  245.          }
  246.  ​
  247.          void test05()
  248.          {
  249.              int arr[] = { 0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 8, 8, 9, 11 };
  250.              stdL<int> l1(std::begin(arr), std::end(arr));
  251.              myL<int> l2(std::begin(arr), std::end(arr));
  252.              stdL<int> l3(std::begin(arr), std::end(arr));
  253.              myL<int> l4(std::begin(arr), std::end(arr));
  254.  ​
  255.              cout << "------------- raw  test----------" << endl;
  256.              stdPrint(l1);
  257.              myPrint(l2);
  258.              cout << "------------- remove  test----------" << endl;
  259.              l1.remove(4);
  260.              l2.remove(4);
  261.              stdPrint(l1);
  262.              myPrint(l2);
  263.  ​
  264.              cout << "------------- remove_if  test----------" << endl;
  265.              l1.remove_if([](int x) {return x % 2; });
  266.              l2.remove_if([](int x) {return x % 2; });
  267.              stdPrint(l1);
  268.              myPrint(l2);
  269.  ​
  270.              cout << "------------- raw  test----------" << endl;
  271.              stdPrint(l3);
  272.              myPrint(l4);
  273.              //cout << "l3: " << l3.size() << "\tl4: " << l4.size() << endl;
  274.              cout << "------------- unique  test----------" << endl;
  275.              l3.unique();
  276.              l4.unique();
  277.              stdPrint(l3);
  278.              myPrint(l4);
  279.  ​
  280.          }
  281.  ​
  282.          void test06()
  283.          {
  284.          
  285.              
  286.              myL<int> l1;
  287.              srand(time(NULL));
  288.              for (int i = 0; i < 10; ++i)
  289.              {
  290.                  int tmp = rand() % 100 + 1;
  291.                  l1.push_back(tmp);
  292.              }
  293.              cout << "------------- raw  test----------" << endl;
  294.              myPrint(l1);
  295.              cout << "------------- sort  test----------" << endl;
  296.              l1.sort();
  297.              myPrint(l1);
  298.              cout << "------------- sort compare  test----------" << endl;
  299.              l1.sort([](int x, int y) {return x > y; });
  300.              myPrint(l1);
  301.              cout << "------------- reverse  test----------" << endl;
  302.              l1.reverse();
  303.              myPrint(l1);
  304.          }
  305.      }
  306.  }

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/128134
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号