list的介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素
list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
list的构造
explicit list (const allocator_type& alloc = allocator_type());
- 解释：构造一个空的容器，里面没有任何元素
`explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type()); - 解释：构造一个包含 n 个元素的容器。每个元素都是 val 的副本
list (InputIterator first, InputIterator last) - 解释：构造一个容器，里面的元素是[first,last)，里面的每个元素都来自这个范围里对应的元素，顺序相同 。
list (const list& x) - 解释：构造一个容器，其中包含 x 中每个元素的，顺序相同。
- 示例：
void test_list1()
{
list<int> l1; // 构造空的l1
list<int> l2(4, 100); // l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l4(l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = { 16,2,77,29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
// 列表格式初始化C++11
list<int> l6{ 1,2,3,4,5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " "; //16 2 77 29
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " "; //16 2 77 29
cout << endl;
}
list的遍历
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
{
cout << *it << " ";
// *it = 10; 编译不通过
}
cout << endl;
}
1.list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
iterator begin();const_iterator begin() const;
iterator end();const_iterator end() const;
reverse_iterator rbegin();const_reverse_iterator rbegin() const
reverse_iterator rend();const_reverse_iterator rend() const;
这里的使用方法和string、vector一样，就不再过多介绍了。
注意
1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
2.list capacity
empty
bool empty() const;
- 解释：检测list是否为空，是返回true，否则返回false
- 示例：
void test_list2()
{
list<int> l1;
list<int> l2;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
cout << l1.empty() << endl; //0
cout << l2.empty() << endl; //1
}
size
size_type size() const;
- 解释：返回list中有效节点的个数
用法跟前面的一样，不在过多阐述。
3.list 的元素的访问
front
reference front();const_reference front() const;
- 解释：返回list的第一个节点中值的引用
- 示例：
void test_list3()
{
list<int> mylist;
mylist.push_back(77);
mylist.push_back(22);
// now front equals 77, and back 22
mylist.front() -= mylist.back();
cout << "mylist.front() is now " << mylist.front() << '\n'; //mylist.front() is now 55
}
back
reference back();const_reference back() const;
- 解释：返回list的最后一个节点中值的引用
- 示例：
void test_list3()
{
list<int> mylist;
mylist.push_back(10);
while (mylist.back() != 0)
{
mylist.push_back(mylist.back() - 1);
}
cout << "mylist contains:";
for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it; //mylist contains: 10 9 8 7 6 5 4 3 2 1 0
}
4.list的插入、删除、交换、清空
push_front
解释：在list首元素前插入值为val的元素
pop_front
解释：删除list中第一个元素
push_back
解释：在list尾部插入值为val的元素
pop_back
解释：删除list中最后一个元素
示例：
void test_list4()
{
int array[] = { 1, 2, 3 };
list<int> L(array, array + sizeof(array) / sizeof(array[0]));
// 在list的尾部插入4，头部插入0
L.push_back(4);
L.push_front(0);
list<int>::iterator it = L.begin();
while (it != L.end())
{
cout << *it << " "; //0 1 2 3 4
++it;
}
cout << endl;
// 删除list尾部节点和头部节点
L.pop_back();
L.pop_front();
list<int>::iterator it1 = L.begin();
while (it1 != L.end())
{
cout << *it1 << " "; //1 2 3
++it1;
}
}
insert
解释：在position位置之前，插入值为val的元素。其它形式的用法和之前一样。
erase
解释：删除position位置的值或者删除某个区间的所有元素。
示例：
void test_list5()
{
//这里的PrintList(L)就是上面list的遍历
int array1[] = { 1, 2, 3 };
list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
// 获取链表中第二个节点
auto pos = ++L.begin();
cout << *pos << endl; //2
// 在pos前插入值为4的元素
L.insert(pos, 4);
PrintList(L); //1 4 2 3
// 在pos前插入5个值为5的元素
L.insert(pos, 5, 5);
PrintList(L); //1 4 5 5 5 5 5 2 3
// 在pos前插入[v.begin(), v.end)区间中的元素
vector<int> v{ 7, 8, 9 };
L.insert(pos, v.begin(), v.end());
PrintList(L); //1 4 5 5 5 5 5 7 8 9 2 3
// 删除pos位置上的元素
L.erase(pos);
PrintList(L); //1 4 5 5 5 5 5 7 8 9 3
// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
L.erase(L.begin(), L.end());
PrintList(L); //
}
swap
解释交换两个list中的元素。
clear
解释：清空list中的有效元素。
示例：
void test_list6()
{
// 用数组来构造list
int array1[] = { 1, 2, 3 };
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
PrintList(l1); //1 2 3
// 交换l1和l2中的元素
list<int> l2(3, 1);
l1.swap(l2);
PrintList(l1); //1 1 1
PrintList(l2); //1 2 3
// 将l2中的元素清空
l2.clear();
cout << l2.size() << endl; //0
}
5.list的其它操作
sort
- 解释：对列表中的元素进行排序，更改它们在容器中的位置。(默认是按照升序排列)
- 示例：
void test_list7()
{
list<int> l1 = { 3,2,1,4,5 };
auto it = l1.begin();
while (it != l1.end())
{
cout << *it << " "; //3 2 1 4 5
++it;
}
cout << endl;
//升序排列：less
l1.sort();
for (list<int>::iterator i = l1.begin(); i != l1.end(); i++)
{
cout << *i << " "; //1 2 3 4 5
}
}
如果想按照降序排列，就按以下的方式写。这里就先展示如何写，到后面的学习在深入讲解这个知识点，也就是“仿函数”。
void test_list7()
{
list<int> l1 = { 3,2,1,4,5 };
auto it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//降序排列：greater
//greater<int> gt;
//l1.sort(gt);
l1.sort(greater<int>()); //推荐这种写法
for (list<int>::iterator i = l1.begin(); i != l1.end(); i++)
{
cout << *i << " "; //5 4 3 2 1
}
}
- 解释：对[first,last)范围内的元素进行排序。也可以通过迭代器对指定范围内的元素进行排序。默认是按升序排序，当然也可以通过仿函数来按照降序排列。
- 示例：
int main()
{
vector<int> v = { 6,3,4,5,2,1,7,9,8 };
sort(v.begin(), v.end());
for (auto i : v)
{
cout << i << " "; //1 2 3 4 5 6 7 8 9
}
cout << endl;
vector<int> v1 = { 3,2,4,5,6,8,1 };
sort(v1.begin(), v1.begin() + 4);
for (auto x : v1)
{
cout << x << " "; //2 3 4 5 6 8 1
}
return 0;
}
通过对list和算法库里的sort对比。我们可以知道list里的排序没法使用迭代器来进行排序，因为list的底层是带头双向循环链表，当使用end()时，由于像vector和string里的迭代器不同，它们的end是最后一个元素的下一个位置，而在链表中，链表的物理空间并不连续，end的下一个数据就会指向头结点。所以我们要对迭代器进行一定的封装。让迭代器符合统一的迭代器使用规则。
那么如何进行封装呢？等到list的模拟实现的时候在给各位细心讲解。
unique
- 解释：从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素，也就是去除重复元素。注意，只有当元素与紧接其前面的元素相等时，才会从列表容器中删除该元素。因此，此函数对于排好序的列表特别有用。（只对于版本1）
- 示例：
void test_list9()
{
list<int> l1 = { 1,2,2,2,3,4,4,2,2,5 };
l1.unique();
auto i = l1.begin();
while (i != l1.end())
{
cout << *i << " "; //1 2 3 4 2 5
++i;
}
cout << endl;
list<int> l2 = { 1,1,3,4,2,5,5,5,6 };
l2.sort();
l2.unique();
auto x = l2.begin();
while (x != l2.end())
{
cout << *x << " "; //1 2 3 4 5 6
++x;
}
}
reverse
- 解释：逆置列表中元素的顺序
- 示例：
int main()
{
list<int> mylist;
for (int i = 1; i < 10; ++i)
mylist.push_back(i);
mylist.reverse();
cout << "mylist contains:";
for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it; //mylist contains: 9 8 7 6 5 4 3 2 1
return 0;
}
list的模拟实现
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);
}
}
list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素 效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |