1.list的介绍及使用
1.1构造
| constructor | 说明 |
list (size_type n, const value_type& val = value_type()) |
构造的list中包含n个值为val的 元素 |
| list ( ) | |
| list (const list& x) | |
| list (InputIterator first, InputIterator last) | 用[first, last)区间元素构造 |
list<int> l1(4, 100);// l2中放4个值为100的元素
list<int> l2(l1.begin(), l1.end()); //左闭右开的区间构造l3
list<int> l3{ 1,2,3,4,5 };1.2 iterator
| begin + end | begin( )返回第一个元素的下一个位置 end( )返回最后一个元素下一个位置的迭代器 |
| rbegin+rend | 反向迭代器 |
对begin，end执行++操作，迭代器后移；对rbegin，rend执行++操作，迭代器前移（eg :++begin()）
1.3 Capacity
empty |
|
| size | 返回list中有效节点的个数 |
1.4 Element access
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
1.5 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 |
清空有效元素 |
1.6 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);
}
}2.模拟实现
3.list和vector对比
| vector | list | |
| 底层结构 | 具有连续空间的动态顺序表 | 带头节点的双向循环链表 |
| 随机访问 | 支持[ ]访问 | 不支持[ ] |
| 插入和删除 | 效率低，要搬移元素，可能发生扩容问题 | 效率高 |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |