std::list

std::list是C++标准库中的一个序列容器，它提供了双向链表的功能。std::list允许在序列的任何位置高效地插入和删除元素，而不会引起其他元素的移动，这使得std::list在需要频繁插入和删除操作的场景中非常有用。

std::list的特性：

• 双向链表：std::list存储的元素在内存中不是连续的，而是通过指针连接的节点
• 不保证元素顺序：与std::vector不同，std::list不保证元素的物理存储顺序与声明顺序相同
• 高效的插入和删除：可以在任意位置快速插入和删除元素（O(1)），而不需要移动其他元素；但由于其没有随机访问的能力，因此查找的速度较慢（O(n)）
• 模板类：std::list是一个模板类，可以存储任何类型的数据

std::list有如下一些成员函数：

• std::list()：默认构造一个空的链表；还可以拷贝构造和移动构造
• operator =：赋值操作，用于将一个链表的内容赋给另一个链表
• swap()：交换两个链表的内容
• front()：访问链表的第一个元素
• back()：访问链表的最后一个元素
• insert(const_iterator pos, const T& value)：在指定位置插入一个元素
• emplace(const_iterator pos, Args&&… args)：在指定位置就地构造一个元素
• erase(const_iterator pos)：删除指定位置的元素
• erase(const_iterator first, const_iterator last)：删除指定范围内的元素
• push_back()：末尾添加一个元素
• emplace_back()：末尾就地构造一个元素
• push_front()：表头添加一个元素
• emplace_front()：表头就地构造一个元素
• pop_back()：删除末尾元素
• pop_front()：删除表头元素
• size()：返回链表中元素的数量
• empty()：检查链表是否为空
• sort()：对链表中的元素进行排序，默认按升序排列
• reverse()：反转链表中元素的顺序
• splice()：将一个链表的元素移动到另一个链表

// 创建一个双向链表，并进行初始化
std::list<int> lst = { 1, 2, 3, 4, 5 };  
for (auto value : lst) {std::cout << value << std::endl;  // 1 2 3 4 5
}// 拷贝构造，深拷贝
std::list<int> new_lst1(lst);  
for (auto value : new_lst1) {std::cout << value << std::endl;  // 1 2 3 4 5
}
std::cout << lst.size() << std::endl;  // 5// 移动构造
std::list<int> new_lst2(std::move(lst));  
for (auto value : new_lst2) {std::cout << value << std::endl;  // 1 2 3 4 5
}
std::cout << lst.size() << std::endl;  // 0// 赋值操作
std::list<int> new_lst3{3, 2, 1, 4, 5, 6, 7};
lst = new_lst3;
for (auto value : lst) {std::cout << value << std::endl;  // 3 2 1 4 5 6 7
}// 交换内容
lst.swap(new_lst1);
for (auto value : lst) {std::cout << value << std::endl;  // 1 2 3 4 5
}
for (auto value : new_lst1) {std::cout << value << std::endl;  // 3 2 1 4 5 6 7
}// 访问元素
std::cout << lst.front() << std::endl;  // 访问第一个元素，1
std::cout << lst.back() << std::endl;  // 访问最后一个元素，5// 插入元素
auto it = lst.begin();  // 获取迭代器，指向第一个元素
std::advance(it, 2);  // 将迭代器前移两个元素，指向第三个元素
lst.insert(it, 6);  // 在第三个元素位置插入新元素
for (auto value : lst) {std::cout << value << std::endl;  // 1 2 6 3 4 5
}
std::cout << *it << std::endl;  // 此时迭代器指向第四个元素3
lst.emplace(it, 7);  // 就地构造一个元素插入
for (auto value : lst) {std::cout << value << std::endl;  // 1 2 6 7 3 4 5
}// 删除元素
lst.erase(it);  // 删除指定位置元素，此时迭代器指向第五个元素3
for (auto value : lst) {std::cout << value << std::endl;  // 1 2 6 7 4 5
}
lst.erase(lst.begin(), lst.end());  // 删除指定范围的元素，左闭右开
std::cout << lst.size() << std::endl;  // 0// 末尾添加元素
lst.push_back(8);  // 末尾添加元素8
lst.push_back(9);  // 末尾添加元素9
lst.emplace_back(10);  // 就地构造末尾元素10
for (auto value : lst) {std::cout << value << std::endl;  // 8 9 10
}// 末尾删除元素
lst.pop_back();
for (auto value : lst) {std::cout << value << std::endl;  // 8 9
}// 表头添加元素
lst.push_front(7);  // 表头添加元素7
lst.push_front(6);  // 表头添加元素6
lst.emplace_front(5);  // 就地构造表头元素5
for (auto value : lst) {std::cout << value << std::endl;  // 5 6 7 8 9
}// 表头删除元素
lst.pop_front();
for (auto value : lst) {std::cout << value << std::endl;  // 6 7 8 9 
}// 排序
lst.push_back(4);
lst.push_back(1);
lst.sort();  // 默认按升序排列
for (auto value : lst) {std::cout << value << std::endl;  // 1 4 6 7 8 9 
}// 反转
lst.push_back(0);
lst.reverse();  // 反转元素顺序
for (auto value : lst) {std::cout << value << std::endl;  // 0 9 8 7 6 4 1
}// 合并
lst.splice(lst.begin(), new_lst1);  // 将new_lst1的元素合并到lst的第一个元素位置
for (auto value : lst) {std::cout << value << std::endl;  // 3 2 1 4 5 6 7 0 9 8 7 6 4 1
}

std::list的优点：

• 高效的插入和删除：在任意位置插入和删除元素的时间复杂度为O(1)
• 内存利用率：没有内存浪费，因为不需要像std::vector那样预留空间

std::list的缺点：

• 访问效率低：不能像std::vector那样通过索引随机访问元素，访问特定元素可能需要O(n)的时间
• 内存开销：由于需要存储额外的指针，内存开销比std::vector高