公主请阅
1.list的相关常用接口emplace_back和push/back的区别insert关于find函数的返回值： splicesort---升序和降序1. 数组或 vector的正序和逆序排序正序（升序）排序逆序（降序）排序 2. list 容器中的排序正序（升序）排序逆序（降序）排序 总结 2.常用接口总结1. 元素的插入与删除2. 访问元素3. 大小与容量 4. 排序与合并5. 赋值与交换6. 迭代器相关7. 删除特定元素8. 链表操作总结 3.list的模拟实现
1.list的相关常用接口
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.emplace_back(10);list<int>lt2 = { 1,2,4,5,6 };list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end())//迭代器{cout << *it1<<" ";++it1;}cout << endl;//支持迭代器就支持范围forfor (auto e : lt2){cout << e << " ";}cout << endl;}emplace_back和push/back的区别
class pos{int _row;int _col;public:pos(int row,int col):_row(row),_col(col){}};int main(){list<pos>lt;pos p1(1, 1);lt.push_back(p1);//传一个有名对象lt.push_back(pos(2,2));//传一个匿名对象//使用花括号初始化列表lt.push_back({3,3});//多参数的隐式类型转换，花括号里面的会隐式类型转换成poslt.emplace_back(p1);//传一个有名对象lt.emplace_back(pos(2, 2));//传一个匿名对象//lt.emplace_back({ 3,3 });//多参数的隐式类型转换，花括号里面的会隐式类型转换成pos//emplace可以传多个参数,pos个对象我们传pos个，我们也可以传初始化pos的值lt.emplace_back(3,3 );//emplace_back 会直接在容器末尾构造对象，它可以接受构造函数所需的参数，并直接在容器中构造新元素。/*使用 emplace_back(3, 3); 直接传递构造参数比 push_back(pos(3, 3)); 更为高效，因为 emplace_back 会在列表中直接创建 pos 对象。*/return 0;}/* push_back的话先会调用构造函数，然后再调用拷贝构造在一处代码但是emplace是直接构造的*/在 C++ 的标准库中，push_back 和 emplace_back 都是用于向容器（如 std::vector）的末尾添加元素的操作，但它们在功能和性能上有一些细微的区别：
push_back：会创建一个临时对象，并将其拷贝或移动到容器末尾。它要求我们传入一个已经构造好的对象。
emplace_back：直接在容器末尾构造对象，而不需要创建临时对象。这意味着可以直接传入构造参数，而不是完整的对象。它通过在容器内部直接构造对象，避免了额外的拷贝或移动操作。
push_back：在需要临时对象的情况下性能较慢，因为它可能会触发额外的拷贝或移动。
emplace_back：性能相对更高，因为它避免了临时对象的创建，直接在容器内构造对象，这在某些情况下可以提高效率。
如果要添加一个已经构造好的对象，用 push_back。
如果需要构造一个新的对象并直接放到容器末尾，用 emplace_back。
示例：
std::vector<std::string> vec;// 使用 push_back，需要传入一个已经构造好的对象std::string str = "hello";vec.push_back(str); // 需要拷贝 str// 使用 emplace_back，直接传入构造参数vec.emplace_back("hello"); // 直接在 vector 中构造总结来说，emplace_back 是更高效的选择，特别是当元素的构造比较复杂或昂贵时。
insert
我们使用Insert的时候通常是需要用到find的，但是我们list里面是没有的，但是我们的算法库里面是存在的
添加头文件#include
关于find函数的返回值：
C++ 标准库中的 find 函数通常用于在容器中查找特定元素，其返回值为一个迭代器。具体返回值取决于是否找到了目标元素：
找到目标元素：find 函数返回一个指向目标元素的迭代器。
未找到目标元素：find 函数返回一个指向容器末尾的迭代器（end()），表示没有找到指定的元素。
#include <iostream>#include <vector>#include <algorithm>int main() { std::vector<int> vec = {1, 2, 3, 4, 5}; int target = 3; // 使用 find 函数查找目标元素 auto it = std::find(vec.begin(), vec.end(), target); if (it != vec.end()) { std::cout << "找到目标元素 " << target << "，位置为：" << std::distance(vec.begin(), it) << std::endl; } else { std::cout << "未找到目标元素 " << target << std::endl; } return 0;}注意事项
返回的迭代器类型与容器相同，例如 std::vector<int>::iterator。
find 函数只查找第一个匹配项，如果目标元素有多个相同值，则只返回第一个找到的迭代器。
如果需要查找容器中某个元素是否存在，可以通过比较返回值是否等于 end() 来判断。
int main() {list<int> lt1 = { 1,2,3,4,5 };int x;cin >> x;//输入我们要删除的数据for (auto e : lt1){cout << e << " ";}cout << endl;auto it = find(lt1.begin(),lt1.end(), x);//find函数的参数是迭代区间和查找的值if (it != lt1.end())//就说明找到了，那么我们就进行删除的操作{lt1.erase(it);//将当前的值进行删除操作}for (auto e : lt1){cout << e << " ";}cout << endl;return 0;}splice
在C++中，splice 是一个用于操作双向链表（std::list）的成员函数。std::list 是一种双向链表容器，支持常数时间的插入和删除操作，而 splice 函数则提供了一种高效的方法来在两个链表之间移动元素，而不需要实际的复制或重新分配内存。
splice 函数的主要作用是将一个 std::list 的内容移动到另一个 std::list 中。它的复杂度是常数时间 O(1)，因为它只是修改了链表节点的指针而没有进行内存复制。这使得它在处理大量数据时非常高效。
splice 的用法主要有以下几种形式：
list1.splice(position, list2);将 list2 的所有元素插入到 list1 的 position 位置。
插入后，list2 变为空。
list1.splice(position, list2, it);将 list2 中的迭代器 it 指向的元素插入到 list1 的 position 位置。
it 所指向的元素从 list2 中删除。
list1.splice(position, list2, first, last);将 list2 中 [first, last) 范围内的元素插入到 list1 的 position 位置。
[first, last) 范围内的元素从 list2 中删除。
示例代码
#include <iostream>#include <list>int main() { std::list<int> list1 = {1, 2, 3}; std::list<int> list2 = {4, 5, 6}; // 将 list2 整体插入到 list1 的末尾 list1.splice(list1.end(), list2); // 输出 list1 的内容 for (int n : list1) { std::cout << n << ' '; // 输出：1 2 3 4 5 6 } std::cout << '\n'; // list2 现在为空，因为它的所有元素已被移动到 list1 std::cout << "list2 size: " << list2.size() << '\n'; // 输出：list2 size: 0 return 0;}总结
splice 函数在C++的 std::list 中非常有用，尤其在需要在链表之间移动数据而不希望开销过高的情况下。它提供了灵活高效的数据移动方式，适合需要频繁操作链表数据的场景。
sort—升序和降序
在C++中，sort 函数用于对数组或容器中的元素进行排序。它在 <algorithm> 头文件中定义，可以实现正序（升序）和逆序（降序）排序。
1. 数组或 vector的正序和逆序排序
假设有一个 vector<int> 或数组 int[]，可以这样使用 sort 函数来排序：
正序（升序）排序
#include <iostream>#include <vector>#include <algorithm>int main() { std::vector<int> v = {5, 3, 8, 1, 9}; std::sort(v.begin(), v.end()); // 升序排序 for (int i : v) { std::cout << i << " "; } return 0;}逆序（降序）排序
#include <iostream>#include <vector>#include <algorithm>int main() { std::vector<int> v = {5, 3, 8, 1, 9}; std::sort(v.begin(), v.end(), std::greater<int>()); // 降序排序 for (int i : v) { std::cout << i << " "; } return 0;}2. list 容器中的排序
std::list 中没有提供 sort 函数的 begin 和 end 指针的方式。为了对 std::list 进行排序，list 自身提供了一个成员函数 sort()，可以直接调用。
正序（升序）排序
#include <iostream>#include <list>int main() { std::list<int> lst = {5, 3, 8, 1, 9}; lst.sort(); // 默认升序排序 for (int i : lst) { std::cout << i << " "; } return 0;}逆序（降序）排序
#include <iostream>#include <list>#include <functional> // 用于 std::greaterint main() { std::list<int> lst = {5, 3, 8, 1, 9}; lst.sort(std::greater<int>()); // 降序排序 for (int i : lst) { std::cout << i << " "; } return 0;}总结
sort 函数适用于支持随机访问迭代器的容器（如 vector），可以通过第三个参数控制排序顺序。
list 使用其成员函数 sort() 进行排序，也可以使用 std::greater<int>() 来指定降序排序。
int main(){list<int> lt1 = { -1,59,1,45,26,20 };//默认我们这里的排序是升序的，那么我们怎么将排序结果变成降序的呢？lt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;greater<int>gt;lt1.sort(gt);//这里就可以将排序结果变成降序了for (auto e : lt1){cout << e << " ";}cout << endl;vector<int>v1 = { 1,20,3,-4,5 };for (auto e : v1){cout << e << " ";}cout << endl;//升序sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;//降序sort(v1.begin(), v1.end(),greater<int>());for (auto e : v1){cout << e << " ";}cout << endl;return 0;}2.常用接口总结
好的，下面我会详细描述 C++ 标准库中 std::list 的每一个常用接口，以便更好地理解它们的用途和具体实现方式。
1. 元素的插入与删除
push_back(const T& val)：
功能：在列表的末尾插入一个新元素 val。
使用场景：当需要在双向链表的尾部追加元素时非常高效，因为 std::list 的尾部插入是 O(1) 复杂度。
push_front(const T& val)：
功能：在列表的头部插入一个新元素 val。
使用场景：如果需要频繁在链表头部插入元素，这个函数非常有用，因为头部插入的复杂度是 O(1)。
emplace_back(Args&&... args)：
功能：在尾部直接构造元素，可以减少不必要的拷贝。
使用场景：当元素复杂，需要减少构造和拷贝操作的成本时，可以使用 emplace_back。
emplace_front(Args&&... args)：
功能：在头部直接构造元素。
使用场景：和 emplace_back 类似，但作用在头部，减少了创建临时对象的开销。
insert(iterator pos, const T& val)：
功能：在 pos 迭代器位置前插入一个元素 val。
使用场景：当需要在链表中的某个特定位置插入元素时使用。
erase(iterator pos)：
功能：删除 pos 位置的元素，返回指向被删除元素的下一个元素的迭代器。
使用场景：删除链表中的某个特定元素，复杂度是 O(1)。
pop_back()：
功能：删除链表尾部的元素。
使用场景：需要移除最后一个元素时使用。
pop_front()：
功能：删除链表头部的元素。
使用场景：需要移除第一个元素时使用。
clear()：
功能：清空整个链表，移除所有元素。
使用场景：当需要重新初始化链表时非常有用。
2. 访问元素
front()：
功能：返回链表中第一个元素的引用。
使用场景：需要访问链表头部的元素，例如获取最先插入的元素。
back()：
功能：返回链表中最后一个元素的引用。
使用场景：需要获取链表尾部的元素，例如最后追加的元素。
3. 大小与容量
size()：
功能：返回链表中的元素个数。
使用场景：需要知道链表的长度时，复杂度为 O(n)。
empty()：
功能：判断链表是否为空，返回布尔值。
使用场景：判断链表是否有元素，例如在进行某些操作之前确认链表非空。
max_size()：
功能：返回链表理论上可以容纳的最大元素数量。
使用场景：通常用来检查链表的最大可能容量，受限于内存的可用量。
4. 排序与合并
sort()：
功能：对链表中的元素按升序排序，元素需支持 < 比较运算符。
使用场景：当需要对链表进行排序时，直接调用 sort()。注意，该排序函数是原地排序（in-place），复杂度为 O(n log n)。
merge(list& other)：
功能：将另一个已排序链表 other 合并到当前链表中。链表必须是有序的。
使用场景：用于两个有序链表的合并操作，合并后的链表依然有序。
reverse()：
功能：将链表中的元素顺序反转。
使用场景：当需要从后向前访问链表时，使用 reverse() 可以方便地调整元素顺序。
unique()：
功能：移除链表中连续重复的元素，保留唯一值。
使用场景：去除链表中的重复值，通常配合 sort() 使用以确保所有重复值都是连续的。
5. 赋值与交换
assign(size_type n, const T& val)：
功能：将链表赋值为 n 个值为 val 的元素。
使用场景：需要用特定值重新填充链表时使用。
assign(iterator first, iterator last)：
功能：将链表赋值为范围 [first, last) 的元素。
使用场景：从另一个容器中取一段元素来重新填充当前链表。
swap(list& other)：
功能：交换当前链表和另一个链表的内容。
使用场景：用于高效交换两个链表的元素，避免不必要的复制。
6. 迭代器相关
begin()：
功能：返回指向链表第一个元素的迭代器。
使用场景：用于遍历链表，从头开始。
end()：
功能：返回指向链表最后一个元素之后的迭代器。
使用场景：用于表示链表遍历结束的位置。
rbegin()：
功能：返回指向链表最后一个元素的反向迭代器。
使用场景：需要从后向前遍历链表时使用。
rend()：
功能：返回指向链表第一个元素之前的反向迭代器。
使用场景：表示反向遍历的终止位置。
cbegin()、cend()：
功能：返回指向链表第一个元素和最后一个元素后的常量迭代器，不能通过它修改元素。
使用场景：当不需要修改元素时使用，保证安全性。
7. 删除特定元素
remove(const T& val)：
功能：删除链表中所有值等于 val 的元素。
使用场景：需要从链表中移除特定值的元素。
remove_if(Predicate pred)：
功能：删除链表中满足谓词 pred 条件的所有元素。
使用场景：需要删除符合特定条件的元素，例如按某种逻辑判断是否删除。
8. 链表操作
splice(iterator pos, list& other)：
功能：将链表 other 的内容插入到当前链表的 pos 位置，other 会被清空。
使用场景：合并两个链表。
splice(iterator pos, list& other, iterator it)：
功能：将链表 other 中的某个元素 it 插入到当前链表的 pos 位置。
使用场景：从一个链表中提取一个元素，插入到另一个链表中。
splice(iterator pos, list& other, iterator first, iterator last)：
功能：将 other 中 [first, last) 范围内的元素插入到 pos 位置。
使用场景：从一个链表中提取一部分元素插入到当前链表中。
总结
std::list 提供了丰富的接口，能够满足各种链表操作需求，包括元素的插入、删除、访问、排序、合并、反转等。每个接口的使用场景各异，结合链表的特性可以实现高效、灵活的数据操作。掌握这些接口可以帮助我们更好地进行链表的管理和处理。
3.list的模拟实现
list.h
#pragma once#include<assert.h>namespace kai{template <class T>//全部是公用的话我们就使用structstruct list_node//链表节点{T _data;list_node <T>* _next;list_node <T>* _prev;list_node(const T& x = T())//构造:_data(x), _next(nullptr), _prev(nullptr){}};//模板化的结构体list_iterator表示链表的迭代器，提供了多个运算符重载函数//第二个参数是T的引用，第三个是T的地址template <class T,class Ref,class Ptr>struct list_iterator{typedef list_node<T> Node;//节点模版typedef list_iterator<T, Ref,Ptr> Self;//迭代器模版Node* _node;list_iterator(Node*node)//构造一个迭代器会用一个节点的指针进行构造:_node(node){}Ref operator*()//引用返回，可读可写达到，可以读数据也可以写数据，达到和指针一样的行为{return _node->_data;}Ptr operator->()//返回数据的地址{return &_node->_data;}Self &operator++()//前置++{_node = _node->_next;//从当前节点到第二个节点return *this;//前置++返回自己,类型是Self}Self operator++(int)//后置++{Self tmp(*this);_node = _node->_next;//从当前节点到第二个节点return tmp;//后置加加返回之前的结果}Self &operator--()//前置--{_node = _node->_prev;//从当前节点到前一个节点的位置return *this;//前置--返回自己,类型是Self}Self operator--(int)//前置--{Self tmp(*this);_node = _node->_prev;//从当前节点到前一个节点的位置return tmp;//后置减减返回之前的结果}bool operator!=(const Self& s)//两个迭代器比较{return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};//两个版本的迭代器的唯一不同就是*和->的重载函数的返回值是不同的const迭代器模板化的结构体list_const_iterator表示链表的迭代器，提供了多个运算符重载函数//template <class T>//struct list_const_iterator//{//typedef list_node<T> Node;//节点模版//typedef list_const_iterator<T> Self;//迭代器模版//Node* _node;//list_const_iterator(Node* node)//构造一个迭代器会用一个节点的指针进行构造//:_node(node)//{}//const T& operator*()//返回const别名我们就不能进行修改了////引用返回，可读可写达到，可以读数据也可以写数据，达到和指针一样的行为//{//return _node->_data;//}//const T* operator->()//返回数据的地址//{//return &_node->_data;//}//Self& operator++()//前置++//{//_node = _node->_next;//从当前节点到第二个节点//return *this;//前置++返回自己,类型是Self//}//Self& operator++(int)//后置++//{//Self tmp(*this);//_node = _node->_next;//从当前节点到第二个节点//return tmp;//后置加加返回之前的结果//}//Self& operator--()//前置--//{//_node = _node->_prev;//从当前节点到前一个节点的位置//return *this;//前置--返回自己,类型是Self//}//Self& operator--(int)//前置--//{//Self tmp(*this);//_node = _node->_prev;//从当前节点到前一个节点的位置//return tmp;//后置减减返回之前的结果//}//bool operator!=(const Self& s)//两个迭代器比较//{//return _node != s._node;//}//};//存在公有也存在私有的那么我们就使用classtemplate <class T>//带头双向循环所需要的class list{typedef list_node<T> Node;//节点模版public://typedef list_iterator<T> iterator;//迭代器模版//typedef list_const_iterator<T> const_iterator;//迭代器模版（const版本）typedef list_iterator<T,T&,T*> iterator;//迭代器模版typedef list_iterator<T, const T&, const T*> const_iterator;//迭代器模版（const版本）iterator begin(){return iterator(_head->_next);//有效数据的头结点}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);//有效数据的头结点}const_iterator end()const{return const_iterator(_head);}void empty_init(){_head = new Node();//带头双向循环所需要的_head->_next = _head;_head->_prev = _head;_size = 0;}list()//构造函数{empty_init();}//深拷贝构造//lt2(lt1) //这个lt就是lt1的别名list(const list <T>& lt){empty_init();for (auto &e:lt){push_back(e);}}//lt2=lt3 lt就是lt3的别名//list<T>& operator=( list<T> lt)//我们这里给上赋值重载函数就行了//类里面是可以不加模版参数的list& operator=(list lt)//我们这里给上赋值重载函数就行了{//lt是lt3的拷贝，有一样大的空间一样大的值，那么我们将lt2和lt交换下就行了swap(lt);//这个swap是this进行调用的，this指针指向的是lt2return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& tmp){std::swap(_head,tmp._head);//交换下哨兵位的指针就行了std::swap(_size, tmp._size);//交换下哨兵位的指针就行了}void clear(){auto it = begin();while (it != end()){it=erase(it);//这里返回的是下一个节点的迭代器}}list(size_t n,const T&val=T())//n个val的构造函数{empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}void push_back(const T& x)//尾插{插入节点的时候处理好前后节点与插入节点的关系//Node* new_node = new Node(x);//Node* tail = _head->_prev;//原先的尾节点//tail->_next = new_node;//那么新插入的节点就是原先尾节点的下个节点了//new_node->_prev = tail;//那么新插入的节点的头结点就指向我们的之前的尾节点了//new_node->_next = _head;//那么新节点的下个节点就是哨兵位//_head->_prev = new_node;//那么哨兵位的前一个节点就是我们的当前插入的节点了insert(end(),x);//哨兵位就是尾节点}void push_front(const T& x)//头插{insert(begin(), x);//}void pop_front()//头删{erase(begin());}void pop_back()//尾删{erase(--end());//我们的end需要--就能到达尾节点，就是哨兵位结点--我们就可以到达这个尾节点}iterator insert(iterator pos, const T& val)//在pos位置之前插入一个值{Node* cur = pos._node;//pos位置节点的指针Node* newnode = new Node(val);//新插入的节点的指针Node* prev = cur->_prev;//插入节点之前的节点//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;//返回一个迭代器指向新插入的节点return iterator(newnode);}iterator erase(iterator pos){//删除是不能删除哨兵位的assert(pos!=end());//这里给end的原因是因为end就是这个哨兵位的头结点构造的迭代器Node* del = pos._node;//删除的节点Node* prev = del->_prev;//删除节点的前一个节点Node* next = del->_next;//让要删除节点的前一个节点和后一个节点连接起来 prev->_next = next;next->_prev = prev;delete del;//将要删除的节点进行释放操作--_size;return iterator(next);//返回删除位置的下一个节点}private:Node* _head;//哨兵位的头结点size_t _size;};template<class T>void swap(T& a, T& b){T c(a); a = b; b = c;}template<class T>void swap(list<T>& a, list<T>& b){a.swap(b);}}//使用类封装节点指针，重载运算符，模拟指针的行为