C++学习篇(8)-序列式容器list

list

个人认为list相当于数据结构里面的双向链表，但是实现功能更加复杂。它的好处是每次插入或删除元素时，就要配置或释放一个元素空间，因此，对空间不会产生浪费，对于任何位置的元素插入或删除是都是O(1)的时间复杂度。

list节点

list迭代器

注意：在list中使用erase只会使得当前迭代器失效，其他位置的元素在在迭代器访问时不会失效。

原因是：vector是连续的线性存储空间，当删除元素时，从当前位置后的所有元素都需要向前移动一位，这就导致后面元素的迭代器完全失效，但是对于list来说，其存储元素时不连续的存储空间，所以删除当前元素不会对其他位置的元素产生影响，也不会导致其他位置的迭代器失效。

list使用方法

//创建ilist
list<int> ilist;

//获取ilist对象大小
cout << "size = " << ilist.size() << endl; //size = 0;


//添加元素
ilist.push_back(0);
ilist.push_back(1);
ilist.push_back(2);
ilist.push_back(3);

//遍历数据，迭代器it的原本类型是 it = list<int>::iterator;
for(auto it = ilist.begin(); it != ilist.end(); ++it){
   cout << *it << " ";
}
cout << endl;


//查找元素
list<int>::iterator itf = find(ilist.begin(), ilist.end(), 3);

//插入元素
ilist.insert(ilist.begin(), 99);

//删除元素
ilist.erase(ilist.begin());

list和vector的区别？

1、list不能够像vector一样以普通指针作为迭代器，因为节点不保证连续的存储空间； 但是vector是连续的线性存储空间，当容量不足时会进行2/1.5倍扩容操作；

2、list插入和删除操作不会引起其他元素的迭代器失效，但是vector会；

3、list不仅是双向链表，而且是环状双向链表，所以它的迭代器是双向迭代器，只需要一个指针 ；

4、list不像vector那样可以在空间不足的时候重新配置、数据移动的操作，所以插入前的所有迭代器都是有效的。

5、相较于vector直接分配连续的空间来说。list节点每次插入和删除都需要分配和释放空间；

6、vector的查找时间复杂度为O(1)，但是插入和删除为O(n)；list的插入和删除时间复杂度为O(1)，但是查找为O(n);

7、可以从缺页中断谈起，因为对于vector是连续的线性存储空间，所以对于数据访问时产生的缺页中断次数更少，最差情况下也仅需要少量的页面换入换出即可，但是list是不连续的存储空间，所以导致缺页中断的几率更高。