list的介绍
list本质是一个带头的双向循环链表
- list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立结点当中，在结点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似，最主要的不同在于forward_list是单链表，只能进行单方向迭代。
- 与其他容器相比，list通常在任意位置进行插入、删除元素的执行效率更高。
- list和forward_list最大的缺陷是不支持在任意位置的随机访问，其次，list还需要一些额外的空间，以保存每个结点之间的关联信息（对于存储的类型较小元素来说这可能是一个重要的因素）。
list常见接口的介绍
list的构造函数
1.无参构造:list()
list<int> lt1;
2.用n个值为val的元素构造:list(size_type n,const value_type& val=value_type())
list<int> lt2(10,2);
3.拷贝构造:list(const list& lt)
list<int> lt3(lt2);
4. 用一段区间的元素构造list:list(Inputlterator first,Inputlterator last)
1. string s("hello world"); 2. list<char> lt4(s.begin(),s.end());
实例演示
void PrintList(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } void test4() { list<int> lt1; list<int> lt2(5, 2); list<int> lt3(lt2); list<int> lt4(lt2.begin(), lt2.end()); cout << "lt1:"; PrintList(lt1); cout << "It2:"; PrintList(lt2); cout << "It3:"; PrintList(lt3); cout << "It4:"; PrintList(lt4); }
代码运行结果如下:
list中迭代器
1.begin和end
通过begin函数可以得到容器中第一个元素的正向迭代器，通过end函数可以得到容器中最后一个元素的后一个位置的正向迭代器。
void test12() { list<int> lt(10, 2); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; }
运行结果:
2.rbegin和rend
通过rbegin函数可以得到容器中最后一个元素的反向迭代器，通过rend函数可以得到容器中第一个元素的前一个位置的反向迭代器。
void test13() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::reverse_iterator it = lt.rbegin(); while (it != lt.rend()) { cout << *it << " "; it++; } cout << endl; }
运行结果
list的迭代器遍历
void TestList2() { list<int>lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_front(0); lt.push_front(-1); lt.push_front(-2); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; }
运行结果:
list的增删查改
1.push_front和pop_front
push_front函数用于头插一个数据，pop_front函数用于头删一个数据。
void test5() { list<int> lt; lt.push_front(1); lt.push_front(2); lt.push_front(3); lt.push_front(4); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; }
演示:
2.push_back和pop_back
push_back函数用于尾插一个数据，pop_back函数用于尾删一个数据。
void test6() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); for (auto e : lt) { cout << e << " "; } cout << endl; }
演示
3.insert
list当中的insert函数支持三种插入方式：
- 在指定迭代器位置插入一个数。
- 在指定迭代器位置插入n个值为val的数。
- 在指定迭代器位置插入一段迭代器区间（左闭右开）。
void test7() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); //1.在指定迭代器位置插入一个数 list<int>::iterator pos = find(lt.begin(), lt.end(), 2); lt.insert(pos, 9); for (auto e : lt) { cout << e << " "; } cout << endl; //2.在指定迭代器位置插入n个值为val的数 pos = find(lt.begin(), lt.end(), 3); lt.insert(pos, 2, 8); for (auto e : lt) { cout << e << " "; } cout << endl; }
演示:
4.erase
list当中的erase函数支持两种删除方式:
1.删除指定迭代器位置的元素。
2.删除指定迭代器区间的所有元素
void test8() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); //删除指定迭代器位置的元素 list<int>::iterator pos = find(lt.begin(), lt.end(), 2); lt.erase(pos); for (auto e : lt) { cout << e << " "; } cout << endl; //删除指定迭代器区间的所有元素 pos = find(lt.begin(), lt.end(), 4); lt.erase(pos, lt.end()); for (auto e : lt) { cout << e << " "; } cout << endl; }
演示
