list的介绍
list的文档介绍
![]()
list的构造
| 构造函数 | 接口说明 |
|---|
| 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 |
list iterator的使用
| 函数声明 | 接口说明 |
|---|
| begin + end | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的 reverse_iterator (即 end 位置) + 返回最后一个元素下一个位置的 reverse_iterator (即 begin 位置) |
![]()
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
list capacity
| 函数声明 | 接口说明 |
|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点的个数 |
list element access
| 函数声明 | 接口说明 |
|---|
| front | 返回 list 的第一个节点中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
list modifiers
| 函数声明 | 接口说明 |
|---|
| 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 中的有效元素 |
#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; //int main() //{ // 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 it = lt.begin(); // while (it != lt.end()) // { // *it += 10; // // cout << *it << " "; // ++it; // } // cout << endl; // // 范围for遍历 // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // 逆置 // lt.reverse(); // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // return 0; //} void test_op1() { srand(time(0)); const int N = 1000000; list<int> lt1; list<int> lt2; vector<int> v; for (int i = 0; i < N; ++i) { auto e = rand(); lt1.push_back(e); v.push_back(e); } int begin1 = clock(); sort(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); lt1.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); } void test_op2() { srand(time(0)); const int N = 1000000; list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); lt1.push_back(e); lt2.push_back(e); } int begin1 = clock(); // vector vector<int> v(lt2.begin(), lt2.end()); // sort(v.begin(), v.end()); // lt2 lt2.assign(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); lt1.sort(); int end2 = clock(); printf("list copy vector sort copy list sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); } //int main() //{ // list<int> lt; // lt.push_back(1); // lt.push_back(4); // lt.push_back(2); // lt.push_back(2); // lt.push_back(2); // lt.push_back(2); // lt.push_back(4); // lt.push_back(3); // // lt.push_back(5); // // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // 先排序再去重 // lt.sort(); // lt.unique(); // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // //sort(lt.begin(), lt.end()); // test_op2(); // // return 0; //} int main() { // LRU list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; // 把2转移到列表的尾部 lt.splice(lt.end(), lt, find(lt.begin(), lt.end(), 2)); for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
list的迭代器失效
可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给 其赋值 l.erase(it); ++it; } } // 改正 void TestListIterator() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { l.erase(it++); // it = l.erase(it); } }
