扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要因素
构造函数 接口说明 list() 构造空的list list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素 list (const list& x) 拷贝构造函数 list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
- list()
listlt1;
- list (size_type n, value_type& val = value_type())
listlt2(4， 1);//构造4个值为1的元素
- list (const list& x)
listlt3(lt2);//用lt2拷贝构造lt3
- list (InputIterator first, InputIterator last)
//1、用l2的[begin(), end()）左闭右开的区间构造lt4 listlt4(lt2.begin(), lt2.end()); //2、以数组为迭代器区间构造lt5 int array[] = {1,2,3,4 }; list lt5(array, array + sizeof(array) / sizeof(int));
2.1.begin和end
函数声明 接口说明 begin 返回第一个元素的迭代器 end 返回最后一个元素下一个位置的迭代器 rbegin 返回第一个元素的reverse_iterator,即end位置 rend 返回最后一个元素下一个位置的reverse_iterator,即begin位置
2.2.rbegin和rendbegin是返回第一个元素的迭代器，end是返回最后一个元素下一个位置的迭代器。可以通过迭代器进行元素访问：
void list_test1() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list ::iterator it = lt.begin(); while (it != lt.end()) //不能用it< lt.end() {cout<< *it<< " "; it++; } cout<< endl; }
- 注意：begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
2.3.范围for和先前学到的string类似，rbegin的第一个元素为尾部end位置，rend返回的是begin的位置。
void list_test1() {listlt(4, 1); list ::reverse_iterator rit = lt.rbegin(); //或者用auto自动识别类型：auto rit = lt.rbegin(); while (rit != lt.rend()) {cout<< *it<< " "; // 1 1 1 1 it++; } }
- 注意：rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。
2.4.迭代器的分类范围for的底层就是迭代器实现的，利用其也可进行元素访问：
void list_test1() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for(auto e : lt) {cout<< e<< " "; } cout<< endl; }
- 单向迭代器：只能++，不能–。比如单链表、哈希表等。
- 双向迭代器：既能++也能–。比如双向链表。
- 随机访问迭代器：既能++、–；又能+、-。比如vector、string。
- 迭代器是内嵌类型（内部类或定义在类里）
3.1.front和back
函数声明 接口声明 front 返回list第一个节点中值的引用 back 返回list最后一个节点中值的引用
front返回第一个元素，back返回最后一个元素
void list_test2() {listlt; for (int i = 1; i<= 4; i++) {lt.push_back(i);//1 2 3 4 } cout<< lt.front()<< endl;//1 cout<< lt.back()<< endl; //4 }
4.1.empty
函数声明 接口说明 empty 检测list是否为空，是返回true，不是返回false size 返回list中有效节点的个数 max_size 返回list中的大数据
4.2.size和max_sizeempty判断list是否为空
void list_test2() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); if(lt.empty()) cout<< "list empty"<< endl; lt.pop_back(); lt.pop_back(); lt.pop_back(); lt.pop_back(); if(lt.empty()) cout<< "list empty"<< endl; }
size用来获取list的元素个数，max_size用来获取list的大元素个数。
void list_test2() {list lt(5, 1); cout<< lt.size()<< endl;// 5 cout<< lt.max_size()<< endl; // 返回链表长度大值 }
5.1.push_front和pop_front
函数声明 接口声明 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中的有效数据 resize 为list开辟空间同时进行初始化
5.2.push_back和pop_backpush_front即头插，pop_front即头删。
void list_test3() {listlt; 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(); lt.pop_front(); for (auto e : lt) {cout<< e<< " "; } cout<< endl; }
5.3.insert和erasepush_back即尾插，pop_back即尾删。
void list_test3() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) {cout<< e<< " "; } cout<< endl; lt.pop_back(); lt.pop_back(); lt.pop_back(); lt.pop_back(); if(lt.empty()) cout<< "list empty"<< endl; }
5.3.clear和resizelist中的insert支持下列三种插入方式：
- 在指定位置插入一个值为val的元素
- 在指定位置插入n个值为val的元素
- 在指定位置插入一段左闭右开的迭代器区间
void list_test3() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list ::iterator pos = find(lt.begin(), lt.end(), 2); //1、在3的位置插入值20 lt.insert(pos, 20); for (auto e : lt) {cout<< e<< " ";//1 20 2 3 4 } cout<< endl; //2、在3的位置插入3个30 pos = find(lt.begin(), lt.end(), 3); lt.insert(pos, 3, 30); for (auto e : lt) {cout<< e<< " ";//1 20 2 30 30 30 3 4 } cout<< endl; //3、在7的位置插入迭代器区间 pos = find(lt.begin(), lt.end(), 20); list lt2(3, 0); lt.insert(pos, lt2.begin(), lt2.end()); for (auto e : lt) {cout<< e<< " ";//1 0 0 0 20 2 30 30 30 3 4 } cout<< endl; } erase支持下列两种删除方式：
删除在指定迭代器位置的元素
删除指定迭代器区间的元素
void list_test3() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); list ::iterator pos = find(lt.begin(), lt.end(), 2); //1、删除2位置的元素 lt.erase(pos); for (auto e : lt) {cout<< e<< " ";//1 3 4 5 6 } cout<< endl; //2、删除4到list末尾的所有元素 pos = find(lt.begin(), lt.end(), 4); lt.erase(pos, lt.end()); for (auto e : lt) {cout<< e<< " ";//1 3 } } 注意：这里的find使用的是算法库里面的，list并未提供find算法。
5.4.swapclear用来清空list中的有效数据。
void list_test4() {listlt(5, -1); for (auto e : lt) {cout<< e<< " ";//-1 -1 -1 -1 -1 } cout<< endl; lt.clear(); for (auto e : lt) {cout<< e<< " ";//空 } } resize扩容并初始化分为两种：
如果 n 小于当前容器大小，则内容将减少到其前n个元素，删除超出的元素（并销毁它们）。
如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到n的大小。如果指定了 val，则新元素将初始化为 val ，否则，它们将被值初始化为0 或者 匿名对象。
void list_test4() {listlt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); resize(5); for(auto e : ch) {cout<< e<< " "; // 1 2 3 4 5 } cout<< endl; resize(8, 10); for(auto e : ch) {cout<< e<< " "; // 1 2 3 4 5 10 10 10 } cout<< endl; resize(10); for(auto e : ch) {cout<< e<< " "; // 1 2 3 4 5 10 10 10 0 0 } cout<< endl; }
6.list的其他操作函数swap用于交换两个list的内容。
void list_test4() {listlt1(5, 1); list lt2(3, 2); lt2.swap(lt1); for (auto e : lt1) {cout<< e<< " "; //2 2 2 } cout<< endl; for (auto d : lt2) {cout<< d<< " "; //1 1 1 1 1 } }
6.1.sort
函数声明 接口说明 sort 对list进行排序 unique 删除list中的重复元素 splice 将元素从一个list剪切到另一个list move 删除具有特定值的元素 move_if 删除满足条件的元素 merge 合并排序list reverse 反转list元素的顺序
6.2.splicelist中的sort函数默认排升序。
void list_test5() {listlt; lt.push_back(2); lt.push_back(23); lt.push_back(6); lt.push_back(14); lt.push_back(10); lt.push_back(100); lt.remove(100); for (auto e : lt) {cout<< e<< " "; } cout<< endl; // list 双向循环链表提供 lt.sort(); // algorithm 算法库提供 //sort(lt.begin(), lt.end()); 报错 for (auto e : lt) {cout<< e<< " "; } cout<< endl; //迭代器功能分类 // 1.单向 ++ // 2.双向 -- // 3.随机 ++ -- + - ——>vector、string } 注意：
list单独提供排序是因为它不能用算法库中的排序。算法库中的排序是一个快排，需要满足三数取中以及传递随机访问迭代器，list并不能满足，所以不适用。而list自己提供的排序的底层是归并排序，但是它本身提供的排序比较慢，如果数据量较小，那效率还可以，但是如果数据量很大，我们宁愿把list中的数据尾插到vector中使用算法库中的快排，再拷贝回list中，也不会使用自身的归并排序。
测试一：vector使用算法库中的sortVSlist自身的sort
// N个数据需要排序，vector+ 算法sort list+ sort void test_op1() {srand((unsigned int)time(0)); const int N = 1000000; vectorv; v.reserve(N); list lt1; for (int i = 0; i< N; ++i) {auto e = rand(); v.push_back(e); lt1.push_back(e); } int begin1 = clock(); sort(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); //sort(lt2.begin(), lt2.end()); lt1.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); } 测试二：list先把数据拷贝到vector，再排序，排序完成后，再将数据拷贝回list所用时间VSlist使用自身的sort所用时间
void test_op2() {srand((unsigned int)time(0)); const int N = 10000000; vectorv; v.reserve(N); list lt1; list lt2; for (int i = 0; i< N; ++i) {auto e = rand(); //v.push_back(e); lt1.push_back(e); //lt2.push_back(e); } // 拷贝到vector排序，排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) {v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) {//e = v[i++]; lt2.push_back(e); } int end1 = clock(); int begin2 = clock(); //sort(lt2.begin(), lt2.end()); lt1.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
6.3.move和move_ifsplice将元素从一个list剪切到另一个list，被剪切的list没有元素了。
void list_test6() {listlt1; lt1.push_back(10); lt1.push_back(20); lt1.push_back(30); list lt2; lt2.push_back(1); lt2.push_back(2); lt2.push_back(3); lt2.push_back(4); auto it = lt2.begin(); ++it; // 迭代器下标为2 lt2.splice(it, lt1); // 把lt1的元素转移到lt2迭代器下标为2的位置 for (auto e : lt2) {cout<< e<< " "; // 1 10 20 30 2 3 4 } cout<< endl; for(auto e : lt1) {cout<< e<< " "; // 空 } }
6.4.unique和mergemove作用是从容器中删除所有与 val 相等的元素。这将调用这些对象的析构函数，并通过删除的元素数来减小容器大小。
void list_test6() {listlt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(2); lt1.move(2); for(auto e : lt1) {cout<< e<< " "; // 1 3 4 } cout<< endl; } move_if作用是移除满足条件的元素。这将调用这些对象的析构函数，并通过删除的元素数来减小容器大小。
// 是否为偶数 bool is_even(const int& value) {return (value % 2) == 0; } // 是否为奇数 struct is_odd {bool operator() (const int& value) { return (value % 2) == 1; } }; int main () {int arr[]= {15,36,7,17,20,39,4,1}; listlt1 (arr, arr+8); // 15 36 7 17 20 39 4 1 lt1.remove_if (is_even); for(auto e : lt1) {cout<< e<< " "; // 15 36 7 17 39 1 } cout<< endl; lt1.remove_if (is_odd()); for(auto e : lt1) {cout<< e<< " "; // 空 } cout<< endl; return 0; }
6.5.reverseunique是删除list中的重复元素。
void list_test5() {listlt; list lt; lt.push_back(2); lt.push_back(3); lt.push_back(6); lt.push_back(23); lt.push_back(10); lt.push_back(3); lt.push_back(10); lt.sort(); lt.unique(); for (auto e : lt) {cout<< e<< " ";//2 3 6 10 23 } }
- 注意：要想对list进行真正的去重，必须先排序。
merge的作用是合并两个链表，并且这两个链表必须是有序的。
void list_test6() {listlt1; lt1.push_back(10); lt1.push_back(30); lt1.push_back(20); list lt2; lt2.push_back(3); lt2.push_back(2); lt2.push_back(1); lt2.push_back(4); lt1.sort(); lt2.sort(); lt1.merge(lt2); for(auto e : lt1) { cout<< e<< " "; // 1 2 3 4 10 20 30 } cout<< endl;
reverse的作用是反转list中元素的顺序。
void list_test6() {listlt1; for(int i = 1; i<= 5; i++) {lt1.push_back(i); } reverse(lt1); for(auto e : lt1) {cout<< e<< " "; // 5 4 3 2 1 } cout<< endl; }
vector list 底层结构 动态顺序表，一段连续空间 带头结点的双向循环链表 随机访问 支持随机访问，访问某个元素效率O(1) 不支持随机访问，访问某个元素效率O(N) 插入和删除 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) 空间利用率 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 迭代器 原生态指针 对原生态指针(节点指针)进行封装 迭代器失效 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 使用场景 需要高效存储，支持随机访问，不关心插入删除效率 大量插入和删除操作，不关心随机访问
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网