list 的定义

1. list 是一种可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立结点当中，在结点中通过指针指向其前一个元素和后一个元素。
3. list 与 forward_list 非常相似，最主要的不同在于 forward_list 是单链表，只能进行单方向迭代。
4. 与其他容器相比，list 通常在任意位置进行插入、删除元素的执行效率更高。
5. list 和 forward_list 最大的缺陷是不支持在任意位置的随机访问，其次，list 还需要一些额外的空间，以保存每个结点之间的关联信息

list 的构造函数

list<int> lt1; //构造int类型的空容器
list<int> lt2(10, 2); //构造含有10个2的int类型容器
list<int> lt3(lt2); //拷贝构造int类型的lt2容器的复制品
string s("hello world");
list<char> lt4(s.begin(),s.end()); //构造string对象某段区间的复制品
int arr[] = { 1, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(int);
list<int> lt5(arr, arr + sz); //构造数组某段区间的复制品

list 的大小

size

size 函数用于获取当前容器当中的元素个数

resize

void resize (size_type n, value_type val = value_type())

resize 的两种情况：

1. 当所给值大于当前的 size 时，将 size 扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
2. 当所给值小于当前的 size 时，将 size 缩小到该值。

list 的遍历

list<int> l;
l.push_back(100);
l.push_back(23);
l.push_back(1);
l.push_back(10);
l.push_front(99);

范围 for 循环

for(int i : l) {
    cout << i << " ";
}

迭代器

同之前的 vector，list 的迭代器使用原理一致

list<int>::iterator it = l.begin();
while(it != l.end()) {
    cout << *it << endl;
    it++;
}

list 的常用操作

front 和 back

这两个函数用于获取 list 的头和尾

sort

sort 函数可以将容器当中的数据默认排为升序

list<int> l;
l.push_back(100);
l.push_back(23);
l.push_back(1);
l.push_back(10);
l.push_front(99);
l.sort();

splice

void splice (iterator position, list& x);
void splice (iterator position, list& x, iterator i);
void splice (iterator position, list& x, iterator first, iterator last);	//[first,last)

注意： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了。（实际上就是将链表当中的指定结点拼接到了另一个容器当中）

remove 和 remove_if

remove 函数用于删除容器当中特定值的元素

remove_if 函数用于删除容器当中满足条件的元素

bool deleteOddNumber(int& i) {
    return i % 2 != 0;
}
int main() {
    list<int> l;
    list<int> li;
    li.push_back(200);
    li.push_back(2);
    l.push_back(100);
    l.push_back(23);
    l.push_back(1);
    l.push_back(10);
    l.push_front(99);

    l.remove(99);
    l.remove_if(deleteOddNumber);
    for(int i : l) {
        cout << i << " ";
    }

    return 0;

}

merge

merge 函数用于将一个有序 list 容器合并到另一个有序 list 容器当中，使得合并后的 list 容器任然有序。（类似于归并排序）

reverse

reverse 函数用于将容器当中元素的位置进行逆置

assign

assign 函数用于将新内容分配给容器，替换其当前内容，新内容的赋予方式有两种：

将 n 个值为 val 的数据分配给容器。 将所给迭代器区间当中的内容分配给容器。

#include <iostream>
#include <string>
#include <list>
using namespace std;

int main() {
	list<char> lt(3, 'a');
	lt.assign(3, 'b'); //将新内容分配给容器，替换其当前内容
	for (auto e : lt) {
		cout << e << " ";
	}
	cout << endl; //b b b
	string s("hello world");
	lt.assign(s.begin(), s.end()); //将新内容分配给容器，替换其当前内容
	for (auto e : lt) {
		cout << e << " ";
	}
	cout << endl; //h e l l o   w o r l d
	return 0;
}

vector 和 list 对比

既然有了 vector，为什么还会有 list?

• vector 缺点：

1. 头部和中部的插入和删除数据效率较低（因为需要挪动数据）
2. 空间不够，需要开辟空间，其中会重新拷贝数据，消耗较大

• vector 优点： 支持下标随机访问，进而很好地支持了二分查找、排序等

• list 优点： 与 vector 相反，插入和删除的效率较高，直接插入节点即可

• list 缺点： 不支持下标随机访问

---