结婚网站模板,闵行网站制作公司,厦门网站建设招标,石排镇网站建设公司介绍
list的数据结果是一个带头双向链表。
使用
有了前面string、vector的基础#xff0c;后续关于list使用的讲解主要提及与string和vector的不同之处。
使用文档#xff1a;cplusplus.com/reference/list/list/?kwlist
迭代器问题
insert以后迭代器不失效
#include…介绍
list的数据结果是一个带头双向链表。
使用
有了前面string、vector的基础后续关于list使用的讲解主要提及与string和vector的不同之处。
使用文档cplusplus.com/reference/list/list/?kwlist
迭代器问题
insert以后迭代器不失效
#include iostream
#include list
#include vector
using namespace std;int main() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);//在元素3的位置上插入30auto it find(lt.begin(), lt.end(), 3);if (it ! lt.end()){lt.insert(it, 30);// insert以后it不失效*it * 100;}return 0;
}
erase以后迭代器会失效
#define _CRT_SECURE_NO_EARNINGS 1
#include iostream
#include list
#include vector
using namespace std;int main() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);//在元素3的位置上插入30auto it find(lt.begin(), lt.end(), 3);if (it ! lt.end()){lt.insert(it, 30);// insert以后it不失效*it * 100;}it find(lt.begin(), lt.end(), 2);if (it ! lt.end()){lt.erase(it);//erase以后it失效了//*it * 100;//error}return 0;
}
容器和迭代器类型
不同的容器在C标准模板库STL中有不同的底层结构和迭代器类型。这些迭代器类型决定了容器支持哪些算法操作
单向迭代器forward_list、unordered_map、unordered_set 这些容器仅支持向前遍历即仅支持操作。双向迭代器list、map、set 这些容器支持向前和向后遍历即支持和--操作。随机访问迭代器vector、string、deque 这些容器支持高效的随机访问即支持---以及比较操作。
我们再通过vector和list的insert、erase来理解一下上面的讲解
insert:
#include iostream
#include list
#include vector
using namespace std;int main() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);vectorint v { 1,2,3,4,5 };//vector在第5个位置插入数据v.insert(v.begin() 5, 100);//list在第5个位置插入数据//lt.insert(lt.begin() 5, 100);//错误做法auto it lt.begin();for (size_t i 0; i 5; i){it;}lt.insert(it, 100);return 0;
}
erase:
#include iostream
#include list
#include vector
using namespace std;int main() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);vectorint v { 1,2,3,4,5 };//vector删除第5个元素v.erase(v.begin() 5);//list删除第5个元素//lt.erase(begin() 5);//错误做法it lt.begin();for (size_t i 0; i 5; i) {it;}lt.erase(it);return 0;
}
排序
sort
如果需要对一组数据sort排序建议使用vector进行sort排序而不要使用list因为在数据量很大的情况下vector排序的效率远高于list。我们通过一个代码来验证一下
void test_op()
{srand(time(0));const int N 1000000;vectorint v;v.reserve(N);listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt2.push_back(e);lt1.push_back(e);}// 拷贝到vector排序排完以后再拷贝回来int begin1 clock();// 先拷贝到vectorfor (auto e : lt1){v.push_back(e);}// 排序sort(v.begin(), v.end());// 拷贝回去size_t i 0;for (auto e : lt1){e v[i];}int end1 clock();int begin2 clock();lt2.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}
merge合并排序
#include iostream
#include list
#includealgorithm
using namespace std;void print(listint lt) {cout lt: ;for (auto e : lt) {cout e ;}cout endl;
}void test_merge(int a1[], int a2[],int len1,int len2) {sort(a1, a1 len1);sort(a2, a2 len2);listint lt(10);merge(a1, a1 len1, a2, a2 len2, lt.begin());print(lt);
}int main() {int first[] { 5,10,15,20,25 };int second[] { 50,40,30,20,10 };int len1 sizeof(first) / sizeof(first[0]);int len2 sizeof(second) / sizeof(second[0]);test_merge(first, second, len1, len2);return 0;
}
其他算法
unique:去重
#include iostream
#include list
#includealgorithm
using namespace std;int main() {// 创建一个包含重复元素的 listlistint myList { 1, 7, 2, 3, 4, 4, 4, 5, 6, 6 };// 注意std::unique 需要已排序的容器myList.sort(); // 先排序auto lastUnique unique(myList.begin(), myList.end());// 擦除重复的元素myList.erase(lastUnique, myList.end());// 打印去重后的 listfor (auto e : myList) {cout e ;}cout endl;return 0;
}
remove:删除指定元素
int main() {listint mylist { 9,89,23,67 };mylist.remove(89);for (auto e : mylist){cout e ;}cout endl;return 0;
}
splice:把一个链表的内容转移到另一个链表上
//splice(iterator pos, list other)
//将整个源列表other的所有元素移动到目标列表的pos位置之前。源列表将变为空。
void test_splice1(listint mylist1,listint mylist2) {auto it mylist1.begin();it; // points to 2//mylist2全部转移到mylist1的第二个位置之前mylist1.splice(it, mylist2);cout spliced mulist1: ;for (auto e : mylist1){cout e ;}cout endl;
}//splice(iterator pos, list other, iterator first)
//将源列表other中将 first 指向的元素移动到目标列表的pos位置之前。源列表中 first 元素将被移除。
void test_splice2(listint mylist1, listint mylist2) {auto it mylist1.begin();it; // points to 2// 部分转移// mylist2的mylist2.begin()的元素转移到mylist1的第二个位置之前mylist1.splice(it, mylist2, mylist2.begin());cout spliced mulist1: ;for (auto e : mylist1){cout e ;}cout endl;
}//splice(iterator pos, list other, iterator first, iterator last)
//将源列表other中从 first 到 last不包括 last之间的所有元素移动到目标列表的pos位置之前。源列表other中这部分元素将被移除
void test_splice3(listint mylist1, listint mylist2) {auto it mylist1.begin();it; // points to 2// mylist2的mylist2.begin()之后的元素转移到mylist1的第二个位置之前mylist1.splice(it, mylist2, mylist2.begin(), mylist2.end());cout spliced mulist1: ;for (auto e : mylist1){cout e ;}cout endl;
}
int main() {listint mylist1, mylist2;listint::iterator it;// set some initial values:for (int i 1; i 4; i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i 1; i 3; i)mylist2.push_back(i * 10); // mylist2: 10 20 30test_splice1(mylist1,mylist2);test_splice2(mylist1,mylist2);test_splice3(mylist1,mylist2);return 0;
}
