C++第七讲:STL--list的使用及模拟实现
- 1.list的使用
- 1.1list是什么
- 1.2构造、析构、赋值运算符重载
- 1.3迭代器
- 1.4empty、size、max_size
- 1.5front、back
- 1.6assign -- 代替
- 1.7push_back和emplace_back
- 1.8emplace
- 1.9insert、erase、swap、resize、clear
- 1.10find
- 1.11splice
- 1.12remove、remove_if
- 1.13unique
- 1.14merge
- 1.15库中sort的不同使用
- 1.16reverse
- 2.list的模拟实现
- 2.1list模拟实现思路
- 2.2迭代器的实现
- 2.3->问题
- 2.4迭代器封装问题
- 2.5const_iterator实现问题
- 2.6多个swap问题
- 3.list的模拟实现代码
1.list的使用
list的使用和vector、string中的接口大概相同,我们只会详细讲述list的不同之处
1.1list是什么
list的底层其实是一个带头双向循环链表:
下面我们来看list的使用
1.2构造、析构、赋值运算符重载
int main()
{//构造list<int> ls1(3);//就相当于list<int> ls1(3, 0),表示构造一个容器,其中有三个结点,每一个结点都是0的副本//赋值运算符重载(内容改变 + 数据改变)list<int> ls2(4, 2);cout << ls1.size() << endl;//3cout << ls2.size() << endl;//4ls2 = ls1;cout << ls1.size() << endl;//3cout << ls2.size() << endl;//3return 0;
}
1.3迭代器
list实现的迭代器中,begin和end所指向的位置为:
int main()
{list<int> ls1(3, 2);list<int>::iterator it = ls1.begin();while (it != ls1.end()){cout << *it << " ";it++;}cout << endl;//C++11是支持initilizer_list进行构造的list<int> ls2({ 1, 2, 3, 4, 5 });list<int>::iterator it1 = ls2.begin();while (it1 != ls2.end()){cout << *it1 << " ";it1++;}cout << endl;return 0;
}
1.4empty、size、max_size
1.5front、back
1.6assign – 代替
int main()
{list<int> ls1(3, 2);list<int>::iterator it = ls1.begin();while (it != ls1.end()){cout << *it << " ";it++;}cout << endl;//assign的使用(用新的数据、空间代替原来的list)ls1.assign(2, 1);//迭代器区间、n个val、初始化列表ls1.assign({ 1, 2, 3, 4 });it = ls1.begin();while (it != ls1.end()){cout << *it << " ";it++;}cout << endl;return 0;
}
1.7push_back和emplace_back
我们在刷题的时候可能会看到emplace_back的使用,所以我们在这一先简单了解一下,之后我们会详细讲述该函数的功能
我们先看一下两个函数在使用时的差异:
class Pos
{
public://表示坐标int _row;int _col;//我们写一个构造和拷贝构造,如果调用构造或拷贝构造就显示出被调用Pos(int row, int col):_row(row), _col(col){cout << "Pos(int row, int col)" << endl;}Pos(const Pos& p):_row(p._row), _col(p._col){cout << " Pos(const Pos& p)" << endl;}
};
int main()
{//创建一个Pos类型的对象list<Pos> ls1;Pos p1(1, 2);ls1.push_back(p1);ls1.push_back(Pos(1, 2));ls1.push_back({2, 3});Pos p2(1, 2);ls1.emplace_back(p2);ls1.emplace_back(Pos(1, 2));ls1.emplace_back(2, 3);return 0;
}
我们再看一下两个函数的性能差异:
我们都知道,当形参传入实参时,会创建一个临时对象,然后临时对象再传入实参,比如double b = 1.0, int& a = b,这时会发生报错,因为传入给a的实际上时b的一个临时对象,所以要加上const修饰
所以说,对于最后一种情况,使用emplace_back的性能会好点,但是其它情况两者性能没什么区别
上面这几个函数都一样,不再讲
1.8emplace
该函数的作用就是构造 + 插入:
int main()
{list<int> ls1({1, 2, 3, 4, 5});ls1.emplace(ls1.begin(), 2);for (auto e : ls1){cout << e << " ";}cout << endl;// 2 1 2 3 4 5return 0;
}
1.9insert、erase、swap、resize、clear
1.10find
在list的库中,并没有实现find,所以我们还是要使用标准库中的find函数:
int main()
{list<int> ls1({ 1, 2, 3, 4 });for (auto e : ls1){cout << e << " ";}cout << endl;//找到并删除元素int x;cin >> x;auto it = find(ls1.begin(), ls1.end(), x);if (it != ls1.end()){ls1.erase(it);}for (auto e : ls1){cout << e << " ";}cout << endl;return 0;
}
1.11splice
该函数的作用为转移,将list x转移到迭代器指向的position位置、将迭代器指向的i元素转移到list x中的position位置、转移迭代器,要注意的是,因为是转移,如果是将x2中的数据转移到x1中,那么x2就是一个空的list
该函数在一般情况下不太常用,但是对于LRU(近期最少使用,如果最近使用过,就将使用的那一个程序向前排)情况很好用:
int main()
{//LRUlist<int> ls1({ 1, 2, 3, 4, 5 });for (auto e : ls1){cout << e << " ";}cout << endl;//splice函数不仅可以实现两个list之间的转移,还可以做到在自己的list中进行转移int x;while (cin >> x){auto pos = find(ls1.begin(), ls1.end(), x);if(pos != ls1.end()) {ls1.splice(ls1.begin(), ls1, pos);}for (auto e : ls1){cout << e << " ";}cout << endl;}return 0;
}
当出现一直循环的情况时,我们可以按ctrl+z进行截断,也可以使用ctrl+c,VS中ctrl+z和ctrl+c都是将流中的标识符设置为结束,这样就不能再提取东西了,而有的编译器下,ctrl+c的作用是直接将程序强制结束,会比较暴力
1.12remove、remove_if
在list中,remove的特别之处在于,remove删除时不用再传入迭代器,而是传入值进行删除:
int main()
{list<int> ls1({ 1, 2, 3, 4 });ls1.remove(1);for (auto e : ls1){cout << e << " ";}cout << endl;return 0;
}
remove_if以后再提
1.13unique
该函数可以对list进行去重操作:
int main()
{list<int> ls1({ 1, 1, 2, 2, 3, 4, 5 });for (auto e : ls1){cout << e << " ";}cout << endl;ls1.unique();for (auto e : ls1){cout << e << " ";}cout << endl;//1 2 3 4 5return 0;
}
1.14merge
merge必须针对于排序好了的list进行使用,然后对这两个list进行合并,合并方法为挑小的放进其中一个list中,这会使另一个list中没有数据:
int main()
{list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();second.sort();first.merge(second);//将second中的数据合并到first中for (auto e : first){cout << e << " ";}cout << endl;for (auto e : second)//second中没有数据{cout << e << " ";}cout << endl;return 0;
}
如果想要从大到小进行排序,这样使用:
int main()
{list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);//less和greater是两个结构体,可以传入sort中判断按从小到大排还是从大到小进行排序//first.sort(less<double>());//second.sort(less<double>());first.sort(greater<double>());second.sort(greater<double>());first.merge(second, greater<double>());//将second中的数据合并到first中for (auto e : first){cout << e << " ";}cout << endl;for (auto e : second)//second中没有数据{cout << e << " ";}cout << endl;return 0;
}
1.15库中sort的不同使用
我们可以发现,报错了,这是因为:迭代器其实也分为好几种,不同的迭代器有着不同的使用:
其实sort函数的形参我们就可以看出来迭代器的不同:
1.16reverse
逆置操作
2.list的模拟实现
2.1list模拟实现思路
2.2迭代器的实现
list的迭代器实现起来有点不同,因为list中的迭代器不能只是一个指针,如果只是一个指针的话,那么迭代器++,会找不到下一个结点,所以在这里,我们要将迭代器整合成一个类,在类中完成解引用、++的重载,因为迭代器中的数据会经常使用,按照惯例,我们还使用结构体封装
2.3->问题
我们看下面的代码:
class Pos
{
public://表示坐标int _row;int _col;Pos(int row = 1, int col = 1):_row(row), _col(col){cout << "Pos(int row, int col)" << endl;}Pos(const Pos& p):_row(p._row), _col(p._col){cout << " Pos(const Pos& p)" << endl;}
};int main()
{Mine::list<Pos> lt2;Pos p1(1, 1);lt2.push_back(p1);lt2.push_back(Pos(2, 2));lt2.push_back({ 3,3 });Mine::list<Pos>::iterator it2 = lt2.begin();while (it2 != lt2.end()){//*重载时返回的是Pos data,所以*it访问的是Pos的对象,这样我们就可以对它的数据进行访问了cout << (*it2)._row << ":" << (*it2)._col << endl;//这样是可以执行的++it2;}cout << endl;return 0;
}
那么可以使用->来访问吗?当然可以,只是我们需要重载一下:
这个重载的实现非常奇怪,而使用起来是这样:
T* operator->()
{return &_node->_data;
}int main()
{Mine::list<Pos> lt2;Pos p1(1, 1);lt2.push_back(p1);lt2.push_back(Pos(2, 2));lt2.push_back({ 3,3 });Mine::list<Pos>::iterator it2 = lt2.begin();while (it2 != lt2.end()){cout << (*it2)._row << ":" << (*it2)._col << endl;//cout << it2->_row << ":" << it2->_col << endl;//为了可读性,特殊处理,省略了一个->//第一个->的含义是调用它的重载,第二个->的含义为访问内容//cout << it2->->_row << ":" << it2->->_col << endl;//err:语法错误cout << it2->_row << ":" << it2->_col << endl;cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;++it2;}cout << endl;return 0;
}
2.4迭代器封装问题
对于容器,它们的底层有:数组、链表、树和哈希等等,但是我们可以发现:它们被访问的方式都有迭代器,这些迭代器的底层实现可能不同,但是对于我们使用者而言,却没什么区别,这就是C++中的封装概念:
2.5const_iterator实现问题
我们能不能直接这样写:
肯定不能,因为这里的const迭代器是一个类,不是一个指针的别名,如果直接这样实现的话,我们看下边:
所以我们只能够再实现一个const_iterator:
template<class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}Self& operator++()//前置++{_node = _node->_next;return *this;}Self& operator--()//前置--{_node = _node->_prev;return *this;}Self operator++(int)//后置++{Self ret(*this);_node = _node->_next;return ret;}Self operator--(int)//后置--{Self ret(*this);_node = _node->_prev;return ret;}bool operator!=(const Self& s){return _node != s._node;}const T* operator->(){return &_node->_data;}
};typedef list_const_iterator<T> const_iterator;
const_iterator begin() const
{return const_iterator(_head->_next);
}
const_iterator end() const
{return const_iterator(_head);
}
//n个val的构造
list(int n, const T& val = T())
{empty_init();for (size_t i = 0; i < n; i++){push_back(val);}
}int main()
{//const对象不能够push_back,因为const对象只有在定义时才有一次初始化的机会const Mine::list<int> ls1(10, 1);//ls1.push_back(1); errMine::list<int>::const_iterator it = ls1.begin();while (it != ls1.end()){cout << *it << " ";it++;}cout << endl;return 0;
}
但是,我们会发现:const迭代器的实现和普通的迭代器只有在*和->两个运算符重载时才有所不同,而不同只有它们的返回值,因为这两个都是访问操作符,const的作用就是防止访问的数据进行改变,那么我们可不可以将他们进行合并呢,我们看库是怎么实现的:
我们根据库中的实现自己实现一下:
2.6多个swap问题
这个问题我们之前谈过,就是为什么list中实现了两个swap函数:
3.list的模拟实现代码
#pragma once
#include <assert.h>namespace Mine
{//使用struct和class的唯一区别是,struct中的对象默认是public,而class中的默认是private//这里有一个惯例:如果一个对象中的成员全是全局对象,那么就将它们封装在一个struct中template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;//默认构造函数,因为后边new出结点时,可能会传参进行初始化对象list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};//迭代器的实现//typedef list_iterator<T, T&, T*> iterator;//typedef list_iterator<T, const T&, const T*> const_iterator;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;}Self& operator++()//前置++{_node = _node->_next;return *this;}Self& operator--()//前置--{_node = _node->_prev;return *this;}Self operator++(int)//后置++{Self ret(*this);_node = _node->_next;return ret;}Self operator--(int)//后置--{Self ret(*this);_node = _node->_prev;return ret;}bool operator!=(const Self& s){return _node != s._node;}Ptr operator->(){return &_node->_data;}};//template<class T>//struct list_const_iterator//{// typedef list_node<T> Node;// typedef list_const_iterator Self;// Node* _node;// list_const_iterator(Node* node)// :_node(node)// {}// const T& operator*()// {// return _node->_data;// }// Self& operator++()//前置++// {// _node = _node->_next;// return *this;// }// Self& operator--()//前置--// {// _node = _node->_prev;// return *this;// }// Self operator++(int)//后置++// {// Self ret(*this);// _node = _node->_next;// return ret;// }// Self operator--(int)//后置--// {// Self ret(*this);// _node = _node->_prev;// return ret;// }// bool operator!=(const Self& s)// {// return _node != s._node;// }// const T* operator->()// {// return &_node->_data;// }//};反向迭代器的实现//template<class T>//struct list_reserve_iterator//{// //反向迭代器中仍然也是一个Node// typedef list_node<T> Node;// typedef list_reserve_iterator Self;// Node* _node;// list_reserve_iterator(Node* node)// :_node(node)// {}// T& operator*()// {// return _node->_data;// }// Self& operator++()// {// _node = _node->_prev;// return *this;// }// Self& operator--()// {// _node = _node->_next;// return *this;// }// Self operator++(int)// {// Self tmp(*this);// _node = _node->_prev;// return tmp;// }// Self operator--(int)// {// Self tmp(*this);// _node = _node->_next;// return tmp;// }// bool operator!=(const Self& i1)// {// return _node != i1._node;// }//};///重点:template<class T>class list{typedef list_node<T> Node;private:Node* _head;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//typedef list_reserve_iterator<T> reserve_iterator;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);}//reserve_iterator rbegin()//{// return reserve_iterator(_head->_prev);;//}//reserve_iterator rend()//{// return reserve_iterator(_head);//}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}//析构函数iterator erase(iterator pos){assert(pos != end());//需要保存pos位置的上一个结点,以及下一个结点Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);}void clear(){auto it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//尾插void push_back(const T& x){/*Node* newnode = new Node(x);Node* ptail = _head->_prev;newnode->_prev = ptail;newnode->_next = _head;ptail->_next = newnode;_head->_prev = newnode;*/insert(end(), x);}//头插void push_front(const T& x){insert(begin(), x);}//n个val的构造list(int n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}//解决浅拷贝问题list(const list<T>& ls){//直接尾插即可empty_init();for (auto e : ls){push_back(e);}}//赋值运算符重载list<T>& operator=(list<T> ls){swap(ls);return *this;}//头删void pop_front(){erase(begin());}//尾删void pop_back(){erase(--end());}//在pos位置进行插入iterator insert(iterator pos, const T& val = T()){Node* newnode = new Node(val);Node* pcur = pos._node;Node* prev = pcur->_prev;newnode->_prev = prev;newnode->_next = pcur;prev->_next = newnode;pcur->_prev = newnode;return iterator(newnode);}//list类中实现的交换void swap(list<T>& ls){std::swap(_head, ls._head);}};//库中的swaptemplate <class T>void swap(T& a, T& b){T c(a); a = b; b = c;}//自己定义的全局swaptemplate <class T>void swap(list<T>& ls1, list<T>& ls2){ls1.swap(ls2);}
}