List
1、list概述
相较于vector的连续线性空间，list是一个环状双向链表。
每次插入或删除一个元素，就配置或释放一个元素空间，时间复杂度为常数。
2、list的节点
以下是STL list的节点（node）结构：
template<class T>
struct __list_node{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
}
显然这是一个双向链表
3、list的迭代器
由于STL list是一个双向链表，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterator。
在C++中，**双向迭代器（Bidirectional Iterator）**是一种迭代器类型，允许在容器中双向移动，即不仅可以从前向后遍历（如前向迭代器），还可以从后向前遍历。这类迭代器提供了比输入迭代器、输出迭代器和前向迭代器更多的功能，通常用于双向链表（如 std::list）等容器。
list有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立。因为vector的插入操作可能造成记忆体重新配置，导致原有迭代器全部失效。甚至list的元素删除操作，也只有"指向被删除元素"的那个迭代器失效，其他迭代器不受任何影响。
4、list的数据结构
SGI list是一个环状双向链表，所以只需要一个指针，便可以完整表现整个链表：
template<class T, class Alloc = alloc>
class list{
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; //只需要一个指针，便可完成整个环状环状双向链表
}
如果让指针node指向尾端的一个空白节点（也可以理解为头部的空白节点，因为这是一个环状双向链表），node便能符合STL对于“前闭后开”区间的原则，成为last迭代器
iterator begin() { return (link_type)(*node).next; }
iterator end() { return node; }
bool empty() { return node->next == node; }
5、list的常用API
构造函数
// 默认构造函数，构造一个空的list
list();
// 构造包含n个val元素的list
explicit list(size_type n, const T& val = T());
// 使用区间[first, last)构造list
template <class InputIterator>
list(InputIterator first, InputIterator last);
// 拷贝构造函数
list(const list& x);
// 移动构造函数
list(list&& x) noexcept;
// 列表初始化构造函数
list(std::initializer_list<T> ilist);
赋值操作符
// 赋值操作符
list& operator=(const list& x);
// 移动赋值操作符
list& operator=(list&& x) noexcept;
// 列表赋值操作符
list& operator=(std::initializer_list<T> ilist);
大小相关函数
// 返回list中的元素个数
size_type size() const noexcept;
// 判断list是否为空
bool empty() const noexcept;
// 返回list可以容纳的最大元素个数
size_type max_size() const noexcept;
访问元素
// 返回第一个元素的引用
T& front();
const T& front() const;
// 返回最后一个元素的引用
T& back();
const T& back() const;
修改list
// 在末尾插入元素
void push_back(const T& val);
void push_back(T&& val);
// 在开头插入元素
void push_front(const T& val);
void push_front(T&& val);
// 移除末尾元素
void pop_back();
// 移除开头元素
void pop_front();
// 清空所有元素
void clear() noexcept;
// 插入元素
iterator insert(const_iterator position, const T& val);
iterator insert(const_iterator position, T&& val);
iterator insert(const_iterator position, size_type n, const T& val);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, std::initializer_list<T> ilist);
// 删除指定位置的元素
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
// 重置大小
void resize(size_type n);
void resize(size_type n, const T& val);
// 交换两个list
void swap(list& x) noexcept;
// 移除等于val的所有元素
void remove(const T& val);
// 移除满足谓词的所有元素
template <class Predicate>
void remove_if(Predicate pred);
迭代器
// 返回指向第一个元素的迭代器
iterator begin() noexcept;
const_iterator begin() const noexcept;
const_iterator cbegin() const noexcept;
// 返回指向末尾元素之后的迭代器
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;
特殊操作
// 合并另一个已排序的list到当前list
void merge(list& x);
template <class Compare>
void merge(list& x, Compare comp);
// 反转list中元素的顺序
void reverse() noexcept;
// 移除重复的元素
void unique();
template <class BinaryPredicate>
void unique(BinaryPredicate binary_pred);
// 对list中的元素进行排序
void sort();
template <class Compare>
void sort(Compare comp);
6、与vector进行比较
1. 底层实现
std::list：双向链表，每个元素都存储有前后两个指针，指向前一个和后一个元素。std::vector：动态数组，内存是连续的，元素按顺序排列在一块连续的内存空间中。
2. 内存分配
std::list：由于链表的性质，std::list中的元素分散存储，每个元素都有指向下一个和上一个节点的指针，内存不连续，存储效率较低。每次插入和删除时，可能需要动态分配或释放内存。std::vector：std::vector使用连续的内存块存储数据，内存效率更高，但如果vector扩展空间时需要重新分配内存，可能会导致性能下降。
3. 元素访问
std::list：由于是链表结构，无法通过下标直接访问元素。访问某个元素必须通过迭代器从头或尾遍历，时间复杂度为 O(n)。std::vector：支持随机访问，可以通过下标直接访问任何元素，时间复杂度为 O(1)。
4. 插入和删除操作
std::list：在中间或两端插入或删除元素的时间复杂度为 O(1)，因为只需要调整指针即可。插入或删除操作非常高效，适合频繁插入删除的场景。std::vector：插入和删除操作在两端（末尾）的时间复杂度为 O(1)，在中间的插入删除操作需要移动大量元素，时间复杂度为 O(n)。
5. 迭代器的稳定性
std::list：list的迭代器在插入或删除其他元素时仍然有效（除非是删除该迭代器指向的元素）。即，迭代器是稳定的。std::vector：vector的迭代器在重新分配内存（如扩容）时会失效，即迭代器在发生插入或删除操作后可能会变得无效。
6. 适用场景
std::list：适用于需要频繁在中间插入和删除元素的场景，如实现队列、双端队列等。同时适合大小不定的场景，因为不需要频繁分配和移动内存。std::vector：适用于需要随机访问和频繁查询的场景，如实现堆栈、数组等。由于支持快速随机访问，vector更适合需要频繁读取的情况。
7. 性能比较
- 内存开销：
std::list由于每个元素存储了两个指针（前驱和后继），因此在内存上开销较大。std::vector的内存开销较小，因为它只存储元素本身，且内存是连续的。 - 插入删除：
std::list插入和删除的性能通常优于std::vector，特别是在中间位置插入删除时。std::vector插入和删除的性能会因内存搬移和重新分配而下降。 - 遍历和访问：
std::vector在遍历和随机访问时具有更好的性能，因为内存是连续的，能更好地利用缓存。std::list的遍历速度较慢，特别是随机访问时性能较差。
8. 扩展性
std::list：每次插入或删除操作都只需调整相关节点的指针，不需要像vector那样重新分配或移动大块内存。因此，list适合不确定大小的动态操作。std::vector：当容量不足时，vector会一次性分配更多的内存，并将现有元素复制到新内存中，这样可以减少频繁的内存重新分配。因此，vector的扩展策略是一种渐进式的优化方式。
9. 常见操作的时间复杂度
| 操作 | std::list 时间复杂度 | std::vector 时间复杂度 |
|---|---|---|
| 访问元素 | O(n) | O(1) |
| 插入/删除（中间） | O(1) | O(n) |
| 插入/删除（末尾） | O(1) | O(1) |
| 插入/删除（开头） | O(1) | O(n) |
| 迭代器遍历 | O(n) | O(n) |
结论：
- 使用
std::list：当你需要频繁在容器中间插入或删除元素时，std::list是更好的选择，因为它能够在常数时间内完成这些操作。 - 使用
std::vector：当你需要频繁访问元素，特别是随机访问时，std::vector是更好的选择，它能够在常数时间内完成随机访问操作，并且在遍历时性能更好。
选择建议：
- 如果你的应用程序中更多是读取操作（比如通过下标访问元素），并且插入和删除操作相对较少，使用
std::vector。 - 如果你的应用程序中需要频繁地在容器中插入和删除元素，尤其是在中间位置操作，使用
std::list。