• 【C++】【STL】【list类的使用】【list类的模拟实现】

    目录

    一、list的介绍

    迭代器失效问题

    list中的sort问题

    二、list类的模拟实现

    1.定义节点类，list类，迭代器类

    ①定义节点类

    ②定义list类

    ③定义迭代器类

    2.迭代器类中具体功能的定义

    ①迭代器所指向数据的比较

    ②迭代器的++，--

    ③迭代器->符号的重载

    3.list中具体功能的定义

     ①常量迭代器和迭代器的初始和结束位置的返回

    ②列表的构造函数

    ③列表的insert插入

    ④列表的头插和尾插

    ⑤列表的擦除函数erase

    ⑥列表的头插和头删

    4.深浅拷贝的问题

    析构函数

    clear函数

    初始化函数

    定义深拷贝的拷贝函数

    定义赋值拷贝

    测试代码

    5.细节问题

    三、头文件代码汇总

    四、测试代码汇总

    一、list的介绍

    1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
    2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
    3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
    4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
    5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

    构造函数（ (constructor)）

    接口说明

    list (size_type n, const value_type& val = value_type())

    构造的list中包含n个值为val的元素

    list()

    构造空的list

    list (const list& x)

    拷贝构造函数

    list (InputIterator first, InputIterator last)

    用[first, last)区间中的元素构造list

    函数声明

    接口说明

    begin +end

    返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

    rbegin +rend

    返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的

    reverse_iterator,即begin位置

    注意：

    1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
    2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 

    函数声明

    接口说明

    empty

    检测list是否为空，是返回true，否则返回false

    size

    返回list中有效节点的个数

    函数声明

    接口说明

    front

    返回list的第一个节点中值的引用

    back

    返回list的最后一个节点中值的引用

    函数声明

    接口说明

    push_front

    在list首元素前插入值为val的元素

    pop_front

    删除list中第一个元素

    push_back

    在list尾部插入值为val的元素

    pop_back

    删除list中最后一个元素

    insert

    在list position 位置中插入值为val的元素

    erase

    删除list position位置的元素

    swap

    交换两个list中的元素

    clear

    清空list中的有效元素

    1. void test_list1()
    2. {
    3.     list<int> lt;
    4.     lt.push_back(1);
    5.     lt.push_back(2);
    6.     lt.push_back(3);
    7.     lt.push_back(4);
    8.     lt.push_back(5);
    9.  
    10.     list<int>::iterator  it=lt.begin();
    11.     while(it!=lt.end())
    12.     {
    13.         cout<<*it<<" ";
    14.         ++it;
    15.     }
    16.     cout<
    17.  
    18.     it=lt.begin();
    19.     while(it!=lt.end())
    20.     {
    21.         (*it) *=2;
    22.         ++it;
    23.     }
    24.     it=lt.begin();
    25.     while(it!=lt.end())
    26.     {
    27.         cout<<*it<<" ";
    28.         ++it;
    29.     }
    30.     cout<
    31.     for(auto e: lt)
    32.     {
    33.         cout<" ";
    34.     }
    35.     cout<
    36.  
    37.  
    38.     lt.push_front(10);
    39.     lt.push_front(20);
    40.     lt.pop_back();
    41.     for(auto e: lt)
    42.     {
    43.         cout<" ";
    44.     }
    45.     cout<
    46.  
    47. };

     

    迭代器失效问题

    迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代
    器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

    1. void TestListIterator1()
    2. {
    3.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    4.     list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    5.     auto it = l.begin();
    6.     while (it != l.end())
    7.     {
    8. // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
    9.         l.erase(it);
    10.         ++it;
    11.     }
    12. }
    13. int main() {
    14.     TestListIterator1();
    15.     return 0;
    16. }

    1. // 改正
    2. void TestListIterator()
    3. {
    4.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    5.     list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    6.     auto it = l.begin();
    7.     while (it != l.end())
    8.     {
    9.         l.erase(it++); // it = l.erase(it);
    10.     }
    11. }
    12. int main() {
    13.     TestListIterator();
    14.     return 0;
    15. }

    1. void test_list2() {
    2.     list<int> lt;
    3.     lt.push_back(1);
    4.     lt.push_back(2);
    5.     lt.push_back(3);
    6.     lt.push_back(4);
    7.     lt.push_back(5);
    8.  
    9.     auto pos=find(lt.begin(),lt.end(),3);
    10.  
    11.     //找到了就插入
    12.     if(pos !=lt.end())
    13.     {
    14.         //pos是否会失效？不会
    15.         //相对位置关系是不会发生变化的，同时也不会产生野指针
    16.         //因为这是一个链表
    17.         lt.insert(pos,30);
    18.     }
    19.     for(auto e: lt)
    20.     {
    21.         cout<" ";
    22.     }
    23.     cout<
    24.     auto pos1=find(lt.begin(),lt.end(),3);
    25.     if(pos1!=lt.end())
    26.     {
    27.         //pos是否会失效？
    28.         lt.erase(pos1);
    29.         cout<<*pos1<
    30.     }
    31.     for(auto e: lt)
    32.     {
    33.         cout<" ";
    34.     }
    35.     cout<
    36. }

    remove的简单测试

    remove会将list中所有指定的要删除的元素全部都删掉

    1. void test_list3() {
    2.     list<int> lt;
    3.     lt.push_back(1);
    4.     lt.push_back(2);
    5.     lt.push_back(3);
    6.     lt.push_back(4);
    7.     lt.push_back(3);
    8.     lt.push_back(5);
    9.     for(auto e: lt)
    10.     {
    11.         cout<" ";
    12.     }
    13.     cout<
    14.     //remove会将list中全部的3都去除掉
    15.     lt.remove(3);
    16.  
    17.     for(auto e: lt)
    18.     {
    19.         cout<" ";
    20.     }
    21.     cout<
    22. }

    list中的sort问题

    1. void test_list4() {
    2.     list<int> lt;
    3.     lt.push_back(1);
    4.     lt.push_back(2);
    5.     lt.push_back(3);
    6.     lt.push_back(4);
    7.     lt.push_back(3);
    8.     lt.push_back(5);
    9.     //这个算法库中的sort是没办法用的
    10.     //sort(lt.begin(),lt.end());
    11.     //sort算法的迭代器用的是随机访问迭代器，链表的不是，因此不能用该算法
    12.     //使用list专门的sort是可以的，其采用归并的思路
    13.     lt.sort();
    14.     for(auto e: lt)
    15.     {
    16.         cout<" ";
    17.     }
    18.     cout<
    19. }

    1. //N个数据需要排序，vector+算法sort 还是list+sort？
    2. //虽然快排和归并的效率是差不多的，但是vector支持随机访问，在大量的数据的情况下会比list+sort有很大的提升
    3. //使用vector排完再拷贝回去都比list+sort快

    1. // N个数据需要排序，vector+ 算法sort  list+ sort
    2. void test_op()
    3. {
    4.     srand(time(0));
    5.     const int N = 100000;
    6.     vector<int> v;
    7.     v.reserve(N);
    8.  
    9.     list<int> lt1;
    10.     list<int> lt2;
    11.  
    12.     for (int i = 0; i < N; ++i)
    13.     {
    14.         auto e = rand();
    15.         //v.push_back(e);
    16.         lt1.push_back(e);
    17.         lt2.push_back(e);
    18.     }
    19.  
    20.     // 拷贝到vector排序，排完以后再拷贝回来
    21.     int begin1 = clock();
    22.     for (auto e : lt1)
    23.     {
    24.         v.push_back(e);
    25.     }
    26.     sort(v.begin(), v.end());
    27.     size_t i = 0;
    28.     for (auto& e : lt1)
    29.     {
    30.         e = v[i++];
    31.     }
    32.     int end1 = clock();
    33.  
    34.     int begin2 = clock();
    35.     // sort(lt.begin(), lt.end());
    36.     lt2.sort();
    37.     int end2 = clock();
    38.  
    39.     printf("copy vector sort:%d\n", end1 - begin1);
    40.     printf("list sort:%d\n", end2 - begin2);
    41. }
    42.  
    43. int main()
    44. {
    45.     test_op();
    46.     return 0;
    47. }

    容器+sort比list+sort快出了不只一点点 

    二、list类的模拟实现

    1.定义节点类，list类，迭代器类

    ①定义节点类

    1.  template<class T>
    2.     struct list_node
    3.     {
    4.         T _data;
    5.         list_node* _next;
    6.         list_node* _prev;
    7.         
    8.         //构造函数
    9.         list_node(const T& x = T())
    10.                 :_data(x)
    11.                 , _next(nullptr)
    12.                 , _prev(nullptr)
    13.         {}
    14.     };

    ②定义list类

    1. template<class T>
    2.     class list
    3.     {
    4.         typedef list_node Node;
    5.     public:
    6.         //采用复用的方式构建我们的普通迭代器和const迭代器
    7.         //第一个参数就是我们的list对象，后面两个参数用来区分是普通迭代器还是const迭代器
    8.         typedef __list_iterator iterator;
    9.         //迭代器返回的是&T
    10.         typedef __list_iteratorconst T&, const T*> const_iterator;
    11.  
    12.     private:
    13.         Node* _head;
    14.     };

    ③定义迭代器类

    1. // 像指针一样的对象
    2.     template<class T, class Ref, class Ptr>
    3.     struct __list_iterator
    4.     {
    5.         typedef list_node Node;
    6.         //采用复用的方式构建我们的普通迭代器和const迭代器
    7.         //第一个参数就是我们的list对象，后面两个参数用来区分是普通迭代器还是const迭代器
    8.         typedef __list_iterator iterator;
    9.  
    10.         typedef bidirectional_iterator_tag iterator_category;
    11.         typedef T value_type;
    12.         typedef Ptr pointer;
    13.         typedef Ref reference;
    14.         typedef ptrdiff_t difference_type;
    15.  
    16.  
    17.         Node* _node;
    18.  
    19.         __list_iterator(Node* node)
    20.                 :_node(node)
    21.         {}
    22.         //不需用写迭代器的析构函数
    23.         //因为我们迭代器仅仅是用来遍历链表的，如果在遍历完成将这个结点给释放了
    24.         //那么我们的链表就断掉了！！！
    25.  
    26.         //不需用写迭代器的拷贝构造
    27.         //因为默认的就是浅拷贝，也就是两个迭代器指向统一个结点，这也正是我们期望的
    28.  
    29.         
    30.     };

    2.迭代器类中具体功能的定义

    ①迭代器所指向数据的比较

    1.         bool operator!=(const iterator& it) const
    2.         {
    3.             return _node != it._node;
    4.         }
    5.  
    6.         bool operator==(const iterator& it) const
    7.         {
    8.             return _node == it._node;
    9.         }

    ②迭代器的++，--

    用于迭代器的遍历

    注意：链表结点的依次遍历和之前的数组是不同的！

    1. // ++it
    2.         iterator& operator++()
    3.         {
    4.             _node = _node->_next;
    5.             return *this;
    6.         }
    7.  
    8.         // it++
    9.         iterator operator++(int)
    10.         {
    11.             iterator tmp(*this);
    12.             _node = _node->_next;
    13.             return tmp;
    14.         }
    15.  
    16.         // --it
    17.         iterator& operator--()
    18.         {
    19.             _node = _node->_prev;
    20.             return *this;
    21.         }
    22.  
    23.         // it--
    24.         iterator operator--(int)
    25.         {
    26.             iterator tmp(*this);
    27.             _node = _node->_prev;
    28.             return tmp;
    29.         }

    ③迭代器->符号的重载

    箭头是用来访问结构成员的。

    1.         Ref operator*()
    2.         {
    3.             return _node->_data;
    4.         }
    5.  
    6.         //T* operator->()
    7.         Ptr operator->()
    8.         {
    9.             //&(_node->_data)
    10.             return &(operator*());
    11.         }

    按照上面的代码，我们其实是需要输入it->->_a1来访问it迭代器中的_a1参数的，其中it->是调用了

     it->会被转化成it.operator->()，也就是返回一个T*对象

    而T*在会调用上面的函数

    返回T*->_data

    但是写两个箭头太难看了，编译器为了方便，就变成只输入一个->就可以了。 

     并且由于我们上面迭代器的定义方式，我们这里也并没有把是不是const属性给写死，这样下面函数中的Ref和Ptr会随着我们上面模板中的定义而随之改变，也就不用区分是不是const了。

    3.list中具体功能的定义

     ①常量迭代器和迭代器的初始和结束位置的返回

    1.         const_iterator begin() const
    2.         {
    3.             return const_iterator(_head->_next);
    4.         }
    5.  
    6.         const_iterator end() const
    7.         {
    8.             return const_iterator(_head);
    9.         }
    10.  
    11.         iterator begin()
    12.         {
    13.             return iterator(_head->_next);
    14.         }
    15.  
    16.         iterator end()
    17.         {
    18.             return iterator(_head);
    19.         }

    ②列表的构造函数

    1.         list()
    2.         {
    3.             _head = new Node;
    4.             _head->_next = _head;
    5.             _head->_prev = _head;
    6.         }

    ③列表的insert插入

    1.         iterator insert(iterator pos, const T& x)
    2.         {
    3.             Node* cur = pos._node;
    4.             Node* prev = cur->_prev;
    5.  
    6.             Node* newnode = new Node(x);
    7.  
    8.             // prev newnode cur
    9.             prev->_next = newnode;
    10.             newnode->_prev = prev;
    11.             newnode->_next = cur;
    12.             cur->_prev = newnode;
    13.  
    14.             return iterator(newnode);
    15.         }

    ④列表的头插和尾插

    1.         void push_back(const T& x)
    2.         {
    3.         //可以手动重新写一个
    4.             //Node* tail = _head->_prev;
    5.             //Node* newnode = new Node(x);
    6.  
    7.              _head          tail  newnode
    8.             //tail->_next = newnode;
    9.             //newnode->_prev = tail;
    10.             //newnode->_next = _head;
    11.             //_head->_prev = newnode;
    12.         //也可以复用insert
    13.             insert(end(), x);
    14.         }
    15.  
    16.         void push_front(const T& x)
    17.         {
    18.             insert(begin(), x);
    19.         }

    ⑤列表的擦除函数erase

    1.         iterator erase(iterator pos)
    2.         {
    3.             assert(pos != end());
    4.  
    5.             Node* cur = pos._node;
    6.             Node* prev = cur->_prev;
    7.             Node* next = cur->_next;
    8.  
    9.             prev->_next = next;
    10.             next->_prev = prev;
    11.             delete cur;
    12.  
    13.             return iterator(next);
    14.         }

    ⑥列表的头插和头删

    1.         void pop_back()
    2.         {
    3.             erase(--end());
    4.         }
    5.  
    6.         void pop_front()
    7.         {
    8.             erase(begin());
    9.         }

    4.深浅拷贝的问题

    如果我们给我们上面的代码添上析构函数，就会发生报错。因为我们两个list在发生拷贝的时候是浅拷贝，对于同一个结点会释放两次，所以就会发生报错。这里我们就需要将我们的浅拷贝调整为深拷贝

    析构函数

    1.         ~list()
    2.         {
    3.             clear();
    4.             delete _head;
    5.             _head= nullptr;
    6.         }

    在析构之前我们最好提供一个clear函数

    clear仅仅是清除数据，但是头结点是不清除的的

    clear函数

    1.         void clear()
    2.         {
    3.             iterator it=begin();
    4.             while(it!=end())
    5.             {
    6.                 //返回下一个位置的迭代器，防止迭代器失效
    7.                 it=erase(it);
    8.             }
    9.         }

    初始化函数

    这里我们单独将初始化函数定义出来，然后其他的代码复用初始化函数 

    1.         //创建并初始化哨兵位头结点
    2.         void empty_init()
    3.         {
    4.             _head = new Node;
    5.             _head->_next = _head;
    6.             _head->_prev = _head;
    7.         }
    8.         //lt2(lt1)
    9.         list(const list& lt)
    10.         {
    11.             //现代写法，最好先初始化一下
    12.             empty_init();
    13.             list tmp(lt.begin(),lt.end());
    14.             swap(tmp);
    15.         }
    16.         void swap(list lt)
    17.         {
    18.             std::swap(_head,lt._head);
    19.         }
    20.         list()
    21.         {
    22.             empty_init();
    23.         }

    定义深拷贝的拷贝函数

    1.         template<class InputIterator>
    2.         list(InputIterator first,InputIterator last)
    3.         {
    4.             empty_init();
    5.             while(first!=last)
    6.             {
    7.                 //将节点中的内容一个一个拷贝
    8.                 push_back(*first);
    9.                 ++first;
    10.             }
    11.         }

    定义赋值拷贝

    1.         //lt1=lt3
    2.         list& operator=(list lt)
    3.         {
    4.             swap(lt);
    5.             return *this;
    6.         }

    测试代码

    1. void test_list4()
    2. {
    3.     list<int> lt;
    4.     lt.push_back(1);
    5.     lt.push_back(3);
    6.     lt.push_back(2);
    7.     lt.push_back(3);
    8.     lt.push_back(4);
    9.     lt.push_back(3);
    10.     lt.push_back(3);
    11.     lt.push_back(5);
    12.  
    13. //    listcopy(lt);
    14.     list<int> copy=lt;
    15.     for (auto e : lt)
    16.     {
    17.         cout << e << " ";
    18.     }
    19.     cout << endl;
    20.  
    21.     list<int>::iterator it =copy.begin();
    22.     while(it!=copy.end())
    23.     {
    24.         (*it)*=2;
    25.         it++;
    26.     }
    27.     cout<
    28. //    cout<<(*copy.begin()*=2)<
    29.     for (auto e : copy)
    30.     {
    31.         cout << e << " ";
    32.     }
    33.     cout << endl;
    34.     for (auto e : lt)
    35.     {
    36.         cout << e << " ";
    37.     }
    38.     cout << endl;
    39. }

    我们观察到修改拷贝的list，我们原来的list并不会发生变化

    5.细节问题

    在类外面必须带上模板参数，比方说下面这里

     在类里面编译器会做优化，比方说这里的其实不写也可以，但是写上最好

    可以看到编译器并没有报错。

     

    三、头文件代码汇总

    1. #ifndef LIST_TEST2_LIST_H
    2. #define LIST_TEST2_LIST_H
    3. #pragma once
    4.  
    5. #include 
    6.  
    7. namespace zhuyuan
    8. {
    9.     template<class T>
    10.     struct list_node
    11.     {
    12.         T _data;
    13.         list_node* _next;
    14.         list_node* _prev;
    15.  
    16.         list_node(const T& x = T())
    17.                 :_data(x)
    18.                 , _next(nullptr)
    19.                 , _prev(nullptr)
    20.         {}
    21.     };
    22.  
    23.     // typedef __list_iterator             iterator;
    24.     // typedef __list_iterator const_iterator;
    25.  
    26.     // 像指针一样的对象
    27.     template<class T, class Ref, class Ptr>
    28.     struct __list_iterator
    29.     {
    30.         typedef list_node Node;
    31.         typedef __list_iterator iterator;
    32.  
    33.         typedef bidirectional_iterator_tag iterator_category;
    34.         typedef T value_type;
    35.         typedef Ptr pointer;
    36.         typedef Ref reference;
    37.         typedef ptrdiff_t difference_type;
    38.  
    39.  
    40.         Node* _node;
    41.  
    42.  
    43.         __list_iterator(Node* node)
    44.                 :_node(node)
    45.         {}
    46.  
    47.         bool operator!=(const iterator& it) const
    48.         {
    49.             return _node != it._node;
    50.         }
    51.  
    52.         bool operator==(const iterator& it) const
    53.         {
    54.             return _node == it._node;
    55.         }
    56.  
    57.         // *it  it.operator*()
    58.         // const T& operator*()
    59.         // T& operator*()
    60.         Ref operator*()
    61.         {
    62.             return _node->_data;
    63.         }
    64.  
    65.         //T* operator->()
    66.         Ptr operator->()
    67.         {
    68.             return &(operator*());
    69.         }
    70.  
    71.         // ++it
    72.         iterator& operator++()
    73.         {
    74.             _node = _node->_next;
    75.             return *this;
    76.         }
    77.  
    78.         // it++
    79.         iterator operator++(int)
    80.         {
    81.             iterator tmp(*this);
    82.             _node = _node->_next;
    83.             return tmp;
    84.         }
    85.  
    86.         // --it
    87.         iterator& operator--()
    88.         {
    89.             _node = _node->_prev;
    90.             return *this;
    91.         }
    92.  
    93.         // it--
    94.         iterator operator--(int)
    95.         {
    96.             iterator tmp(*this);
    97.             _node = _node->_prev;
    98.             return tmp;
    99.         }
    100.     };
    101.  
    102.     template<class T>
    103.     class list
    104.     {
    105.         typedef list_node Node;
    106.     public:
    107.         typedef __list_iterator iterator;
    108.         typedef __list_iteratorconst T&, const T*> const_iterator;
    109.  
    110.         const_iterator begin() const
    111.         {
    112.             return const_iterator(_head->_next);
    113.         }
    114.  
    115.         const_iterator end() const
    116.         {
    117.             return const_iterator(_head);
    118.         }
    119.  
    120.         iterator begin()
    121.         {
    122.             return iterator(_head->_next);
    123.         }
    124.  
    125.         iterator end()
    126.         {
    127.             return iterator(_head);
    128.         }
    129.  
    130.         list()
    131.         {
    132.             empty_init();
    133.         }
    134.  
    135.         template<class InputIterator>
    136.         list(InputIterator first,InputIterator last)
    137.         {
    138.             empty_init();
    139.             while(first!=last)
    140.             {
    141.                 //将节点中的内容一个一个拷贝
    142.                 push_back(*first);
    143.                 ++first;
    144.             }
    145.         }
    146.         //创建并初始化哨兵位头结点
    147.         void empty_init()
    148.         {
    149.             _head = new Node;
    150.             _head->_next = _head;
    151.             _head->_prev = _head;
    152.         }
    153.         //lt2(lt1)
    154.         list(const list& lt)
    155.         {
    156.             //现代写法，最好先初始化一下
    157.             empty_init();
    158.             list tmp(lt.begin(),lt.end());
    159.             swap(tmp);
    160.         }
    161.         void swap(list lt)
    162.         {
    163.             std::swap(_head,lt._head);
    164.         }
    165.         ~list()
    166.         {
    167.             clear();
    168.             delete _head;
    169.             _head= nullptr;
    170.         }
    171.         void clear()
    172.         {
    173.             iterator it=begin();
    174.             while(it!=end())
    175.             {
    176.                 //返回下一个位置的迭代器，防止迭代器失效
    177.                 it=erase(it);
    178.             }
    179.         }
    180.  
    181.         //lt1=lt3
    182.         list& operator=(list lt)
    183.         {
    184.             swap(lt);
    185.             return *this;
    186.         }
    187.         void push_back(const T& x)
    188.         {
    189.             //Node* tail = _head->_prev;
    190.             //Node* newnode = new Node(x);
    191.  
    192.              _head          tail  newnode
    193.             //tail->_next = newnode;
    194.             //newnode->_prev = tail;
    195.             //newnode->_next = _head;
    196.             //_head->_prev = newnode;
    197.  
    198.             insert(end(), x);
    199.         }
    200.  
    201.         void push_front(const T& x)
    202.         {
    203.             insert(begin(), x);
    204.         }
    205.  
    206.         iterator insert(iterator pos, const T& x)
    207.         {
    208.             Node* cur = pos._node;
    209.             Node* prev = cur->_prev;
    210.  
    211.             Node* newnode = new Node(x);
    212.  
    213.             // prev newnode cur
    214.             prev->_next = newnode;
    215.             newnode->_prev = prev;
    216.             newnode->_next = cur;
    217.             cur->_prev = newnode;
    218.  
    219.             return iterator(newnode);
    220.         }
    221.  
    222.         void pop_back()
    223.         {
    224.             erase(--end());
    225.         }
    226.  
    227.         void pop_front()
    228.         {
    229.             erase(begin());
    230.         }
    231.  
    232.         iterator erase(iterator pos)
    233.         {
    234.             assert(pos != end());
    235.  
    236.             Node* cur = pos._node;
    237.             Node* prev = cur->_prev;
    238.             Node* next = cur->_next;
    239.  
    240.             prev->_next = next;
    241.             next->_prev = prev;
    242.             delete cur;
    243.  
    244.             return iterator(next);
    245.         }
    246.  
    247.     private:
    248.         Node* _head;
    249.     };
    250.  
    251.     void test_list1()
    252.     {
    253.         list<int> lt;
    254.         lt.push_back(1);
    255.         lt.push_back(2);
    256.         lt.push_back(3);
    257.         lt.push_back(4);
    258.         lt.push_back(5);
    259.  
    260.         list<int>::iterator it = lt.begin();
    261.         while (it != lt.end())
    262.         {
    263.             cout << *it << " ";
    264.             ++it;
    265.         }
    266.         cout << endl;
    267.  
    268.         it = lt.begin();
    269.         while (it != lt.end())
    270.         {
    271.             *it *= 2;
    272.             ++it;
    273.         }
    274.         cout << endl;
    275.  
    276.         for (auto e : lt)
    277.         {
    278.             cout << e << " ";
    279.         }
    280.         cout << endl;
    281.     }
    282.  
    283.     struct Pos
    284.     {
    285.         int _a1;
    286.         int _a2;
    287.  
    288.         Pos(int a1 = 0, int a2 = 0)
    289.                 :_a1(a1)
    290.                 ,_a2(a2)
    291.         {}
    292.     };
    293.  
    294.     void test_list2()
    295.     {
    296.         int x = 10;
    297.         int* p1 = &x;
    298.  
    299.         cout << *p1 << endl;
    300.  
    301.         Pos aa;
    302.         Pos* p2 = &aa;
    303.         p2->_a1;
    304.         p2->_a2;
    305.  
    306.         list lt;
    307.         lt.push_back(Pos(10, 20));
    308.         lt.push_back(Pos(10, 21));
    309.  
    310.         list::iterator it = lt.begin();
    311.         while (it != lt.end())
    312.         {
    313.             //cout << (*it)._a1 << ":" << (*it)._a2 << endl;
    314.             cout << it->_a1 << ":" << it->_a2 << endl;
    315.  
    316.             ++it;
    317.         }
    318.         cout << endl;
    319.     }
    320.  
    321.     void Func(const list<int>& l)
    322.     {
    323.         list<int>::const_iterator it = l.begin();
    324.         while (it != l.end())
    325.         {
    326.             //*it = 10;
    327.  
    328.             cout << *it << " ";
    329.             ++it;
    330.         }
    331.         cout << endl;
    332.     }
    333.  
    334.     void test_list3()
    335.     {
    336.         list<int> lt;
    337.         lt.push_back(1);
    338.         lt.push_back(2);
    339.         lt.push_back(3);
    340.         lt.push_back(4);
    341.         lt.push_back(5);
    342.  
    343.         Func(lt);
    344.     }
    345.  
    346.     void test_list4()
    347.     {
    348.         list<int> lt;
    349.         lt.push_back(1);
    350.         lt.push_back(2);
    351.         lt.push_back(3);
    352.         lt.push_back(4);
    353.         lt.push_back(5);
    354.  
    355.         list<int>::iterator it = lt.begin();
    356.         while (it != lt.end())
    357.         {
    358.             cout << *it << " ";
    359.             ++it;
    360.         }
    361.         cout << endl;
    362.  
    363.         it = lt.begin();
    364.         while (it != lt.end())
    365.         {
    366.             *it *= 2;
    367.             ++it;
    368.         }
    369.         cout << endl;
    370.  
    371.         for (auto e : lt)
    372.         {
    373.             cout << e << " ";
    374.         }
    375.         cout << endl;
    376.  
    377.         lt.push_front(10);
    378.         lt.push_front(20);
    379.         lt.push_front(30);
    380.         lt.push_front(40);
    381.  
    382.         lt.pop_back();
    383.         lt.pop_back();
    384.  
    385.         for (auto e : lt)
    386.         {
    387.             cout << e << " ";
    388.         }
    389.         cout << endl;
    390.  
    391.         auto pos = find(lt.begin(), lt.end(), 4);
    392.         if (pos != lt.end())
    393.         {
    394.             // pos是否会失效？不会
    395.             lt.insert(pos, 40);
    396.             //lt.insert(pos, 30);
    397.             *pos *= 100;
    398.         }
    399.  
    400.         for (auto e : lt)
    401.         {
    402.             cout << e << " ";
    403.         }
    404.         cout << endl;
    405.  
    406.         lt.clear();
    407.     }
    408. }
    409. #endif //LIST_TEST2_LIST_H

    四、测试代码汇总

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7.  
    8. #include "list.h"
    9.  
    10. void test_list1()
    11. {
    12.     list<int> lt;
    13.     lt.push_back(1);
    14.     lt.push_back(2);
    15.     lt.push_back(3);
    16.     lt.push_back(4);
    17.     lt.push_back(5);
    18.  
    19.     list<int>::iterator it = lt.begin();
    20.     while (it != lt.end())
    21.     {
    22.         cout << *it << " ";
    23.         ++it;
    24.     }
    25.     cout << endl;
    26.  
    27.     it = lt.begin();
    28.     while (it != lt.end())
    29.     {
    30.         *it *= 2;
    31.         ++it;
    32.     }
    33.     cout << endl;
    34.  
    35.     for (auto e : lt)
    36.     {
    37.         cout << e << " ";
    38.     }
    39.     cout << endl;
    40.  
    41.     lt.push_front(10);
    42.     lt.push_front(20);
    43.     lt.push_front(30);
    44.     lt.push_front(40);
    45.  
    46.     lt.pop_back();
    47.     lt.pop_back();
    48.  
    49.     for (auto e : lt)
    50.     {
    51.         cout << e << " ";
    52.     }
    53.     cout << endl;
    54. }
    55.  
    56. void test_list2()
    57. {
    58.     list<int> lt;
    59.     lt.push_back(1);
    60.     lt.push_back(2);
    61.     lt.push_back(3);
    62.     lt.push_back(4);
    63.     lt.push_back(5);
    64.  
    65.     auto pos = find(lt.begin(), lt.end(), 3);
    66.     if (pos != lt.end())
    67.     {
    68.         // pos是否会失效？不会
    69.         lt.insert(pos, 30);
    70.         //lt.insert(pos, 30);
    71.         *pos *= 100;
    72.     }
    73.  
    74.     for (auto e : lt)
    75.     {
    76.         cout << e << " ";
    77.     }
    78.     cout << endl;
    79.  
    80.     pos = find(lt.begin(), lt.end(), 4);
    81.     if (pos != lt.end())
    82.     {
    83.         // pos是否会失效？会
    84.         lt.erase(pos);
    85.         // cout << *pos << endl;
    86.     }
    87.  
    88.     for (auto e : lt)
    89.     {
    90.         cout << e << " ";
    91.     }
    92.     cout << endl;
    93. }
    94.  
    95.  
    96. void test_list3()
    97. {
    98.     list<int> lt;
    99.     lt.push_back(1);
    100.     lt.push_back(3);
    101.     lt.push_back(2);
    102.     lt.push_back(3);
    103.     lt.push_back(4);
    104.     lt.push_back(3);
    105.     lt.push_back(3);
    106.     lt.push_back(5);
    107.  
    108.     /*for (auto e : lt)
    109.     {
    110.         cout << e << " ";
    111.     }
    112.     cout << endl;
    114.     lt.remove(3);
    116.     for (auto e : lt)
    117.     {
    118.         cout << e << " ";
    119.     }
    120.     cout << endl;*/
    121.  
    122.     // sort(lt.begin(), lt.end());
    123.     lt.sort();
    124.  
    125.     for (auto e : lt)
    126.     {
    127.         cout << e << " ";
    128.     }
    129.     cout << endl;
    130. }
    131.  
    132. // N个数据需要排序，vector+ 算法sort  list+ sort
    133. void test_op()
    134. {
    135.     srand(time(0));
    136.     const int N = 100000;
    137.     vector<int> v;
    138.     v.reserve(N);
    139.  
    140.     list<int> lt1;
    141.     list<int> lt2;
    142.  
    143.     for (int i = 0; i < N; ++i)
    144.     {
    145.         auto e = rand();
    146.         //v.push_back(e);
    147.         lt1.push_back(e);
    148.         lt2.push_back(e);
    149.     }
    150.  
    151.     // 拷贝到vector排序，排完以后再拷贝回来
    152.     int begin1 = clock();
    153.     for (auto e : lt1)
    154.     {
    155.         v.push_back(e);
    156.     }
    157.     sort(v.begin(), v.end());
    158.     size_t i = 0;
    159.     for (auto& e : lt1)
    160.     {
    161.         e = v[i++];
    162.     }
    163.     int end1 = clock();
    164.  
    165.     int begin2 = clock();
    166.     // sort(lt.begin(), lt.end());
    167.     lt2.sort();
    168.     int end2 = clock();
    169.  
    170.     printf("copy vector sort:%d\n", end1 - begin1);
    171.     printf("list sort:%d\n", end2 - begin2);
    172. }
    173.  
    174.  
    175. void test_list4()
    176. {
    177.     list<int> lt;
    178.     lt.push_back(1);
    179.     lt.push_back(3);
    180.     lt.push_back(2);
    181.     lt.push_back(3);
    182.     lt.push_back(4);
    183.     lt.push_back(3);
    184.     lt.push_back(3);
    185.     lt.push_back(5);
    186.  
    187. //    listcopy(lt);
    188.     list<int> copy=lt;
    189.     for (auto e : lt)
    190.     {
    191.         cout << e << " ";
    192.     }
    193.     cout << endl;
    194.  
    195.     list<int>::iterator it =copy.begin();
    196.     while(it!=copy.end())
    197.     {
    198.         (*it)*=2;
    199.         it++;
    200.     }
    201.     cout<
    202. //    cout<<(*copy.begin()*=2)<
    203.     for (auto e : copy)
    204.     {
    205.         cout << e << " ";
    206.     }
    207.     cout << endl;
    208.     for (auto e : lt)
    209.     {
    210.         cout << e << " ";
    211.     }
    212.     cout << endl;
    213. }
    214. int main()
    215. {
    216.     test_list4();
    217. //    test_op();
    218. //    bit::test_list4();
    219. //
    220.     return 0;
    221. }

  • 相关阅读:
    【昇腾开发全流程】MindSpore华为云模型训练
    浙江DAMA-CDGA/CDGP数据治理认证招生简章
    C++opencv 色彩空间转换和保存
    Nested loop（PostgreSQL 14 Internals翻译版）
    如何查看SSL证书是OV还是DV?
    【前端】JavaScript数据类型
    leetcode(力扣) 647. 回文子串 (动态规划)
    罗丹明聚乙二醇氨基，Rhodamine-PEG-NH2，NH2-PEG-Rhodamine荧光标记
    最短无序连续子数组
    《论文笔记》Multi-UAV Collaborative Monocular SLAM
  • 原文地址：https://blog.csdn.net/weixin_62684026/article/details/126910925