list的学习

石小疯  论坛元老 | 3 天前 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1844|帖子 1844|积分 5532

list的介绍

list文档的介绍


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

list中的接口比较多，此处雷同，只必要掌握如何精确的使用，然后再去深入研究背后的原理，已达到可扩展的本领。以下为list中一些常见的重要接口。
list的构造


explicit list (const allocator_type& alloc = allocator_type());


  • 表明：构造一个空的容器，里面没有任何元素
    `explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
  • 表明：构造一个包罗 n 个元素的容器。每个元素都是 val 的副本
    list (InputIterator first, InputIterator last)
  • 表明：构造一个容器，里面的元素是[first,last)，里面的每个元素都来自这个范围里对应的元素，顺序相同 。
    list (const list& x)
  • 表明：构造一个容器，此中包罗 x 中每个元素的，顺序相同。
  • 示例：
  1. void test_list1()
  2. {
  3.     list<int> l1;                         // 构造空的l1
  4.     list<int> l2(4, 100);                 // l2中放4个值为100的元素
  5.     list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
  6.     list<int> l4(l3);                    // 用l3拷贝构造l4
  8.     // 以数组为迭代器区间构造l5
  9.     int array[] = { 16,2,77,29 };
  10.     list<int> l5(array, array + sizeof(array) / sizeof(int));
  12.     // 列表格式初始化C++11
  13.     list<int> l6{ 1,2,3,4,5 };
  15.     // 用迭代器方式打印l5中的元素
  16.     list<int>::iterator it = l5.begin();
  17.     while (it != l5.end())
  18.     {
  19.         cout << *it << " ";  //16 2 77 29
  20.         ++it;
  21.     }
  22.     cout << endl;
  24.     // C++11范围for的方式遍历
  25.     for (auto& e : l5)
  26.         cout << e << " ";  //16 2 77 29
  28.     cout << endl;
  29. }
复制代码
list的遍历
  1. // 注意：遍历链表只能用迭代器和范围for
  2. void PrintList(const list<int>& l)
  3. {
  4.     // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
  5.     for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
  6.     {
  7.         cout << *it << " ";
  8.         // *it = 10; 编译不通过
  9.     }
  10.     cout << endl;
  11. }
复制代码
1.list iterator的使用

此处，各人可临时将迭代器理解成一个指针，该指针指向list中的某个节点。
iterator begin();const_iterator begin() const;
iterator end();const_iterator end() const;
reverse_iterator rbegin();const_reverse_iterator rbegin() const
reverse_iterator rend();const_reverse_iterator rend() const;
这里的使用方法和string、vector一样，就不再过多介绍了。
   留意
1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
  
2.list capacity

empty
bool empty() const;


  • 表明：检测list是否为空，是返回true，否则返回false
  • 示例：
  1. void test_list2()
  2. {
  3.     list<int> l1;
  4.     list<int> l2;
  5.     l1.push_back(1);
  6.     l1.push_back(2);
  7.     l1.push_back(3);
  8.     l1.push_back(4);
  10.     cout << l1.empty() << endl;  //0
  11.     cout << l2.empty() << endl;  //1
  12. }
复制代码
size
size_type size() const;


  • 表明：返回list中有效节点的个数
    用法跟前面的一样，不在过多论述。
3.list 的元素的访问

front
reference front();const_reference front() const;


  • 表明：返回list的第一个节点中值的引用
  • 示例：
  1. void test_list3()
  2. {
  3.     list<int> mylist;
  5.     mylist.push_back(77);
  6.     mylist.push_back(22);
  8.     // now front equals 77, and back 22
  9.     mylist.front() -= mylist.back();
  10.     cout << "mylist.front() is now " << mylist.front() << '\n';  //mylist.front() is now 55
  12. }
复制代码
back
reference back();const_reference back() const;


  • 表明：返回list的最后一个节点中值的引用
  • 示例：
  1. void test_list3()
  2. {
  3.     list<int> mylist;
  4.     mylist.push_back(10);
  5.     while (mylist.back() != 0)
  6.     {
  7.         mylist.push_back(mylist.back() - 1);
  8.     }
  10.     cout << "mylist contains:";
  11.     for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
  12.         cout << ' ' << *it;  //mylist contains: 10 9 8 7 6 5 4 3 2 1 0
  13. }
复制代码
4.list的插入、删除、交换、清空

push_front



  • 表明：在list首元素前插入值为val的元素
    pop_front

  • 表明：删除list中第一个元素
    push_back

  • 表明：在list尾部插入值为val的元素
    pop_back

  • 表明：删除list中最后一个元素
  • 示例：
  1. void test_list4()
  2. {
  3.     int array[] = { 1, 2, 3 };
  4.     list<int> L(array, array + sizeof(array) / sizeof(array[0]));
  6.     // 在list的尾部插入4，头部插入0
  7.     L.push_back(4);
  8.     L.push_front(0);
  9.     list<int>::iterator it = L.begin();
  10.     while (it != L.end())
  11.     {
  12.         cout << *it << " ";  //0 1 2 3 4
  13.         ++it;
  14.     }
  15.     cout << endl;
  17.     // 删除list尾部节点和头部节点
  18.     L.pop_back();
  19.     L.pop_front();
  20.     list<int>::iterator it1 = L.begin();
  21.     while (it1 != L.end())
  22.     {
  23.         cout << *it1 << " ";  //1 2 3
  24.         ++it1;
  25.     }
  26. }
复制代码
insert



  • 表明：在position位置之前，插入值为val的元素。别的情势的用法和之前一样。
    erase

  • 表明：删除position位置的值大概删除某个区间的所有元素。
  • 示例：
  1. void test_list5()
  2. {
  3.     //这里的PrintList(L)就是上面list的遍历
  4.     int array1[] = { 1, 2, 3 };
  5.     list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
  7.     // 获取链表中第二个节点
  8.     auto pos = ++L.begin();
  9.     cout << *pos << endl;  //2
  11.     // 在pos前插入值为4的元素
  12.     L.insert(pos, 4);
  13.     PrintList(L);  //1 4 2 3
  15.     // 在pos前插入5个值为5的元素
  16.     L.insert(pos, 5, 5);
  17.     PrintList(L);  //1 4 5 5 5 5 5 2 3
  19.     // 在pos前插入[v.begin(), v.end)区间中的元素
  20.     vector<int> v{ 7, 8, 9 };
  21.     L.insert(pos, v.begin(), v.end());
  22.     PrintList(L);  //1 4 5 5 5 5 5 7 8 9 2 3
  24.     // 删除pos位置上的元素
  25.     L.erase(pos);
  26.     PrintList(L);  //1 4 5 5 5 5 5 7 8 9 3
  28.     // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
  29.     L.erase(L.begin(), L.end());
  30.     PrintList(L);  //
  31. }
复制代码
swap



  • 表明交换两个list中的元素。
    clear

  • 表明：清空list中的有效元素。
  • 示例：
  1. void test_list6()
  2. {
  3.     // 用数组来构造list
  4.     int array1[] = { 1, 2, 3 };
  5.     list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
  6.     PrintList(l1);  //1 2 3
  8.     // 交换l1和l2中的元素
  9.     list<int> l2(3, 1);
  10.     l1.swap(l2);
  11.     PrintList(l1); //1 1 1
  12.     PrintList(l2); //1 2 3
  14.     // 将l2中的元素清空
  15.     l2.clear();
  16.     cout << l2.size() << endl;  //0
  17. }
复制代码
5.list的别的操作

sort



  • 表明：对列表中的元素进行排序，更改它们在容器中的位置。(默认是按照升序分列)
  • 示例：
  1. void test_list7()
  2. {
  3.     list<int> l1 = { 3,2,1,4,5 };
  4.     auto it = l1.begin();
  5.     while (it != l1.end())
  6.     {
  7.         cout << *it << " ";  //3 2 1 4 5
  8.         ++it;
  9.     }
  10.     cout << endl;
  11.    
  12.         //升序排列：less
  13.     l1.sort();
  14.     for (list<int>::iterator i = l1.begin(); i != l1.end(); i++)
  15.     {
  16.         cout << *i << " ";  //1 2 3 4 5
  17.     }
  18. }
复制代码
如果想按照降序分列，就按以下的方式写。这里就先展示如何写，到后面的学习在深入讲解这个知识点，也就是“仿函数”。
  1. void test_list7()
  2. {
  3.     list<int> l1 = { 3,2,1,4,5 };
  4.     auto it = l1.begin();
  5.     while (it != l1.end())
  6.     {
  7.         cout << *it << " ";
  8.         ++it;
  9.     }
  10.     cout << endl;
  12.     //降序排列：greater
  13.     //greater<int> gt;
  14.     //l1.sort(gt);
  15.     l1.sort(greater<int>());  //推荐这种写法
  16.     for (list<int>::iterator i = l1.begin(); i != l1.end(); i++)
  17.     {
  18.         cout << *i << " ";  //5 4 3 2 1
  19.     }
  20. }
复制代码



  • 表明：对[first,last)范围内的元素进行排序。也可以通过迭代器对指定范围内的元素进行排序。默认是按升序排序，固然也可以通过仿函数来按照降序分列。
  • 示例：
  1. int main()
  2. {
  3.     vector<int> v = { 6,3,4,5,2,1,7,9,8 };
  4.     sort(v.begin(), v.end());
  5.     for (auto i : v)
  6.     {
  7.         cout << i << " ";  //1 2 3 4 5 6 7 8 9
  8.     }
  9.     cout << endl;
  11.     vector<int> v1 = { 3,2,4,5,6,8,1 };
  12.     sort(v1.begin(), v1.begin() + 4);
  13.     for (auto x : v1)
  14.     {
  15.         cout << x << " ";  //2 3 4 5 6 8 1
  16.     }
  18.         return 0;
  19. }
复制代码
通过对list和算法库里的sort对比。我们可以知道list里的排序没法使用迭代器来进行排序，由于list的底层是带头双向循环链表，当使用end()时，由于像vector和string里的迭代器不同，它们的end是最后一个元素的下一个位置，而在链表中，链表的物理空间并不连续，end的下一个数据就会指向头结点。所以我们要对迭代器进行肯定的封装。让迭代器符合统一的迭代器使用规则。

那么如何进行封装呢？等到list的模拟实现的时候在给各位仔细讲解。
unique



  • 表明：从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素，也就是去除重复元素。留意，只有当元素与紧接其前面的元素相等时，才会从列表容器中删除该元素。因此，此函数对于排好序的列表特殊有用。（只对于版本1）
  • 示例：
  1. void test_list9()
  2. {
  3.     list<int> l1 = { 1,2,2,2,3,4,4,2,2,5 };
  4.     l1.unique();
  6.     auto i = l1.begin();
  7.     while (i != l1.end())
  8.     {
  9.         cout << *i << " ";  //1 2 3 4 2 5
  10.         ++i;
  11.     }
  12.     cout << endl;
  14.     list<int> l2 = { 1,1,3,4,2,5,5,5,6 };
  15.     l2.sort();
  16.     l2.unique();
  17.     auto x = l2.begin();
  18.     while (x != l2.end())
  19.     {
  20.         cout << *x << " ";  //1 2 3 4 5 6
  21.         ++x;
  22.     }
  23. }
复制代码
reverse



  • 表明：逆置列表中元素的顺序
  • 示例：
  1. int main()
  2. {
  3.     list<int> mylist;
  4.     for (int i = 1; i < 10; ++i)
  5.         mylist.push_back(i);
  7.     mylist.reverse();
  8.     cout << "mylist contains:";
  9.     for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
  10.         cout << ' ' << *it;  //mylist contains: 9 8 7 6 5 4 3 2 1
  12.     return 0;
  13. }
复制代码
list的模拟实现

List的模拟实现
list迭代器失效问题

前面说过，此处各人可将迭代器临时理解成雷同于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。由于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. }
  14. // 改正
  15. void TestListIterator()
  16. {
  17.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  18.     list<int> l(array, array + sizeof(array) / sizeof(array[0]));
  19.     auto it = l.begin();
  20.     while (it != l.end())
  21.     {
  22.         l.erase(it++); // it = l.erase(it);
  23.     }
  24. }
复制代码
list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其重要不同如下：
vectorlist底层结构动态顺序表，一段连续空间带头结点的双向循环链表随机访问支持随机访问，访问某个元素服从O(1)不支持随机访问，访问某个元素
服从O(N)插入和删除恣意位置插入和删除服从低，必要搬移元素，时间复杂度为O(N)，插入时有大概必要增容，增容：开发新空间，拷贝元素，开释旧空间，导致服从更低恣意位置插入和删除服从高，不必要搬移元素，时间复杂度为O(1)空间使用率底层为连续空间，不容易造成内存碎片，空间使用率高，缓存使用率高底层节点动态开发，末节点容易造成内存碎片，空间使用率低，缓存使用率低迭代器原生态指针对原生态指针(节点指针)进行封装迭代器失效在插入元素时，要给所有的迭代器重新赋值，由于插入元素有大概会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器必要重新赋值否则会失效。插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使用场景必要高效存储，支持随机访问，不关心插入删除服从大量插入和删除操作，不关心随机访问
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

石小疯

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表