C++初阶——list
一、什么是list
list是一个可以在序列的任意位置进行插入和删除的容器，并且可以进行双向迭代。list的底层是一个双向链表，双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。通过将每个元素与前一个元素的链接和后一个元素的链接关联起来，内部保持了顺序。
二、list的构造
| 构造函数 | 接口说明 |
| list(size_type n,const value_type& val = valur_type()) | 为构造的list，初始化n个空间，并根据第二个参数进行初始化 |
| list() | 构造空的list |
| list(const list* x) | 拷贝构造函数 |
| list(Inputlterator first, Inputlterator last) | 使用迭代器区间中的元素进行初始化 |
函数原型：
explicit list ();
explicit list (size_type n, const value_type& val = value_type());
template <class InputIterator>
list (InputIterator first, InputIterator last);
list (const list& x);list的构造使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<int> first;//无参构造
list<int> second(10, 1);//构造的list中包含10个1
list<int> third(s.begin() + 5, s.end());//迭代器构造
list<int> fourth(third);//拷贝构造函数
return 0;
}三、list的迭代器
迭代器，按照访问方式可以分为以下三种：
- 前向迭代器（Forward Iterators）：它支持多次遍历，只能递增不能递减。
- 双向迭代器（Bidirectional Iterators）：与前向迭代器类似，但是既能递增也能递减。
- 随机迭代器（Random Access Iterators）：它支持所有双向迭代器的操作，支持跳过元素，支持下标访问，支持比较操作。
list的迭代器属于双向迭代器，也就是说list不能像vector和数组那样通过[]进行访问。
| 函数声明 | 接口说明 |
| begin+end | begin返回第一个元素的迭代器，end返回逻辑上最后一个元素之后的位置 |
| rbegin+rend | rbegin返回最后一个元素的迭代器，这个迭代器指向的是理论上位于容器第一个元素之前的元素，即它不指向容器中的任何实际元素。 |
函数原型为：
iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator rend() nothrow;
const_reverse_iterator rend() const nothrow;迭代器的使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(), s.end());
list<char>::iterator it = first.begin();
list<char>::reverse_iterator r_it = first.rbegin();
cout << "正向迭代器：";
while (it != first.end())
{
cout << *it << " ";
++it;
}
cout << endl;
cout << "反向迭代器：";
while (r_it != first.rend())
{
cout << *r_it << " ";
++r_it;
}
}输出结果为：
四、list的容量相关
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
函数原型为：
size_type size() const noexcept;
bool empty() const noexcept;函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
list<int> first;
list<int> second(10, 1);
cout << first.empty() << endl;
cout << second.empty() << endl;
cout << first.size() << endl;
cout << second.size() << endl;
}五、list的访问
| 函数声明 | 接口说明 |
| front | 返回lsit的第一个节点的值的引用 |
| back | 返回list的最后一个节点的值的引用 |
函数原型为：
reference front();
const_reference front() const;
reference back();
const_reference back() const;函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.end());
cout << first.front() << " " << first.back();
}输出结果为:
六、list的修改
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入一个值 |
| pop_front | 删除list中的第一个元素 |
| push_back | 在尾部插入一个值 |
| pop_back | 删除list的最后一个元素 |
| insert | 在给定的迭代器对应位置插入元素 |
| erase | 删除迭代器对应的元素 |
| swap | 交换两个list中的元素 |
push_front和pop_front
函数原型：
void push_front (const value_type& val);
void push_front (value_type&& val);
void pop_front();
函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.end());
first.push_front('k');
cout << first.front() << endl;
first.pop_front();
cout << first.front() << endl;
}
输出结果：
push_back和pop_back
函数原型：
void push_back (const value_type& val);
void push_back (value_type&& val);
void pop_back();函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.end());
first.push_back('k');
cout << first.back() << endl;
first.pop_back();
cout << first.back() << endl;
}输出结果：
insert函数
函数原型：
iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, size_type n, const value_type& val);
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.end());
first.insert(first.begin(), 'c');
first.insert(first.begin(), 10, 'c');
first.insert(first.begin(), s.begin(), s.end());
}
erase函数
函数原型：
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.end());
first.erase(first.begin(), first.end());
}swap函数
函数原型：
void swap (list& x);函数使用：
#include<iostream>
#include<list>
#include<string>
using namespace std;
int main()
{
string s("hello world");
list<char> first(s.begin(),s.begin() + 5);
list<char> second(s.begin() + 5, s.end());
first.swap(second);
}
七、list的操作
| 函数声明 | 接口说明 |
| reverse | 反转容器中元素的顺序 |
| sort | 排序list中的元素，默认升序 |
| merge | 合并两个列表，它们必须是有序的 |
| unique | 消除列表中的重复元素，必须是有序的 |
| remove | 移除给定的元素 |
| splice | 将一个列表中的一个或一部分元素转移到另一个元素中 |
reverse函数
函数原型：
void reverse() noexcept;函数使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> first = { 1, 3, 5 };
first.reverse();
for (auto i : first)
{
cout << i << " ";
}
}输出结果为：
sort函数
函数原型：
void sort();
template <class Compare>
void sort (Compare comp);函数使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> first = { 4,5,2,1,7,5,9 };
first.sort();//默认升序
//也可以写成first.sort(less<int>());
for (auto i : first)
{
cout << i << " ";
}
cout << endl;
first.sort(greater<int>());//改为降序
for (auto i : first)
{
cout << i << " ";
}
}输出结果：
merge函数
函数原型
void merge (list& x);
template <class Compare>
void merge (list& x, Compare comp);comp是一个比较函数或比较器，它接受两个参数并返回一个布尔值，指示第一个参数是否应该在排序顺序中排在第二个参数之前。这个比较函数应该产生一个严格的弱排序。该函数将参数列表中序列x中的所有元素合并到当前列表中，同时保持排序顺序。两个列表在合并操作之前都必须根据comp提供的比较标准进行排序。
函数使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> first= { 1, 3, 5 };
list<int> second= { 2, 4, 6 };
// 使用自定义比较函数将 list2 合并到 list1
first.merge(second, less<int>());
// 打印合并后的列表
for (int num : first) {
cout << num << " ";
}
cout << endl;
// 合并后 list2 应该为空
if (second.empty()) {
cout << "合并后second 为空。" << endl;
}
return 0;
}输出结果为：
unique函数
函数原型：
void unique();
template <class BinaryPredicate>
void unique (BinaryPredicate binary_pred);函数使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
std::list<int> first = { 1, 2, 2, 3, 3, 3, 4, 4, 5 };
first.unique();
// 打印列表
for (int num : first) {
std::cout << num << " ";
}
cout << std::endl;
// 使用带参数版本的 unique 函数
list<int> second = { 1, 2, 2, 3, 3, 3, 4, 4, 5 };
second.unique(std::equal_to<int>());
// 打印列表
for (int num : second) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}输出结果为：
remove函数
函数原型：
void remove (const value_type& val);函数使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
std::list<int> first = { 1, 2, 2, 3, 4, 2, 5 };
first.remove(2);
for (int num : first) {
cout << num << " ";
}
cout << endl;
return 0;
}输出结果：
splice函数
函数原型：
void splice (const_iterator position, list& x);
void splice (const_iterator position, list& x, const_iterator i);
void splice (const_iterator position, list& x,
const_iterator first, const_iterator last);
代码使用：
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> first = { 1, 2, 3 };
list<int> second = { 4, 5, 6 };
first.splice(first.end(), second);
cout << "first: ";
for (int num : first) {
cout << num << " ";
}
cout << endl;
first.splice(first.end(), first, next(first.begin(), 1));
cout << "first after moving second element: ";
for (int num : first) {
cout << num << " ";
}
cout << endl;
first.splice(second.end(), first, first.begin(), next(first.begin(), 3));
cout << "second after moving elements: ";
for (int num : second) {
cout << num << " ";
}
cout << endl;
return 0;
}输出结果为：
