公主请阅
listfont_3">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);
- 将链表的一个元素插入到另一个链表中
list1.splice(position, list2, it);
- 将链表的一个范围插入到另一个链表中
list1.splice(position, list2, first, last);
示例代码
#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 现在为空,因为它的所有元素已被移动到 list1std::cout << "list2 size: " << list2.size() << '\n'; // 输出:list2 size: 0return 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;
}
list_font_325">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
提供了丰富的接口,能够满足各种链表操作需求,包括元素的插入、删除、访问、排序、合并、反转等。每个接口的使用场景各异,结合链表的特性可以实现高效、灵活的数据操作。掌握这些接口可以帮助我们更好地进行链表的管理和处理。
listfont_638">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);}}//使用类封装节点指针,重载运算符,模拟指针的行为