上海网站优化公司,青海省住房和建设厅网站,wordpress 私有文章,如何看到网站的建设时间文章目录 1.list的介绍2.list的使用2.1list的构造函数2.2list modifiers2.3list capacity2.4list elment access2.5iterator的使用 3.list的模拟实现3.1list的源码 1.list的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向… 文章目录 1.list的介绍2.list的使用2.1list的构造函数2.2list modifiers2.3list capacity2.4list elment access2.5iterator的使用 3.list的模拟实现3.1list的源码 1.list的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向 其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置比如头部或者尾部迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 2.list的使用
template class T, class Alloc allocatorT class list;
//list的使用需要使用显示实例化才能使用2.1list的构造函数
list (size_type n, const value_type val value_type())//构造的list中包含n个值为val的元素
list()//构造空的list
list (const list x)//拷贝构造函数
list (InputIterator first, InputIterator last)//用[first, last)区间中的元素构造listeg
void testlist1()
{listint lt1;listint lt2(10, 6);for (auto e : lt2){cout e ;}coutendl;listint lt3(lt2);for (auto e : lt3){cout e ;}cout endl;listint lt4(lt3.begin(), lt3.end());for (auto e : lt4){cout e ;}cout endl;
}代码运行结果为
2.2list modifiers
void push_front (const value_type val);
//在首元素前插入值为val的元素
void pop_front();
//删除val的第一个元素
void push_back (const value_type val);
//在list的尾部插入值为val的
void pop_back();
//删除list中最后一个元素
single element (1)
iterator insert (iterator position, const value_type val);
//在list position位置插入值为val的元素
fill (2) void insert (iterator position, size_type n, const value_type val);
//在list position的位置插入n个值为val的元素
range (3)
template class InputIteratorvoid insert (iterator position, InputIterator first, InputIterator last);
//在list position的位置插入[first,last]区间的元素
iterator erase (iterator position);
//删除position位置的值
iterator erase (iterator first, iterator last);
//删除[first,last)区间的元素
void swap (list x);
//交换两个list中的元素
void clear();
//清空list中的数据eg1
void testlist2()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);for (auto e : lt1){cout e ;}cout endl;lt1.pop_front();for (auto e : lt1){cout e ;}cout endl;lt1.push_front(100);for (auto e : lt1){cout e ;}cout endl;lt1.pop_back();for (auto e : lt1){cout e ;}cout endl;
}代码编译运行的结果为 eg2
void testlist3()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);listint::iterator it lt1.begin();//在it位置插入99lt1.insert(it, 99);for (auto e : lt1){cout e ;}cout endl;it lt1.begin();//在it位置插入5个6lt1.insert(it, 5, 6);for (auto e : lt1){cout e ;}cout endl;it lt1.begin();listint lt2(6, 5);lt1.insert(it, lt2.begin(), lt2.end());for (auto e : lt1){cout e ;}cout endl;
}代码编译运行的结果为 eg3
void testlist4()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);listint::iterator it lt1.begin();lt1.erase(it);for (auto e : lt1){cout e ;}cout endl;lt1.erase(lt1.begin(), lt1.end());for (auto e : lt1){cout e ;}cout endl;
}代码编译运行的结果为 eg4
void testlist5()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);listint lt2(5, 6);printf(lt1的当前元素:);for (auto e : lt1){cout e ;}cout endl;printf(lt2的当前元素:);for (auto e : lt2){cout e ;}cout endl;swap(lt1, lt2);printf(lt1的当前元素:);for (auto e : lt1){cout e ;}cout endl;printf(lt2的当前元素:);for (auto e : lt2){cout e ;}cout endl;
}代码编译运行的结果为 eg5
void testlist6()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);for (auto e : lt1){cout e ;}cout endl;//清空lt1原有数据后插入66lt1.clear();lt1.push_back(66);for (auto e : lt1){cout e ;}cout endl;
}代码编译运行的结果为
2.3list capacity
bool empty() const;
//检测list是否为空是返回true否则返回false
size_type size() const;
//返回list中有效节点的个数2.4list elment access
reference front();
const_reference front() const;
//返回list的第一个节点中值的引用
reference back();
const_reference back() const;
//返回list的最后一个节点中值的引用eg1
void testlist7()
{listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt1.push_back(50);lt1.push_back(60);cout list头部元素为: lt1.front() endl;cout list尾部元素为: lt1.back() endl;
}代码运行的结果为
2.5iterator的使用
iterator begin();
const_iterator begin() const;
//返回第一个元素的迭代器
iterator end();
const_iterator end() const;
//返回最后一个元素下一个位置的迭代器
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
//返回第一个元素的reverse_iterator,即end位置
reverse_iterator rend();
const_reverse_iterator rend() const;
//返回最后一个元素下一个位置的reverse_iterator,即begin位置list容器使用迭代器
void testlist8()
{listint lt1(5, 6);listint::iterator it lt1.begin(); while (it ! lt1.end()){cout *it ;it;}cout endl;
}代码运行的结果为 迭代器分类
input iterator//输入迭代器
output iterator//输出迭代器
forward iterator//单向迭代器可以 适用forward_list/unorderd_xxx容器
bidirectional iterator//双向迭代器可以/-- 适用list/map/set容器
random access iteartor//任意迭代器可以/--//- 适用于vector/string/deque容器随机迭代器可以使用双向迭代器反之双向迭代器不可以使用随机迭代器较多功能的容器迭代器可以使用适配较少功能的迭代器的算法接口函数反之则不可以 栗子 list的迭代器为 算法接口函数为
void testlist9()
{listint lt1;lt1.push_back(16);lt1.push_back(8);lt1.push_back(99);lt1.push_back(18);lt1.push_back(36);lt1.push_back(6);//不可以使用algorithm//sort(lt1.begin(), lt1.end());//可以使用list自己的sort进行排序lt1.sort();for (auto e : lt1){cout e ;}cout endl;
}代码编译运行的结果为 list的迭代器为双向迭代器不能使用算法接口函数中适配任意迭代器的sort函数只能使用list的sort函数。 3.list的模拟实现
3.1list的源码
#pragma once
#includeiostream
using namespace std;
namespace newspace
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()):_prev(nullptr), _next(nullptr), _val(val){}};templateclass T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;Node* _node;typedef __list_iteratorT, Ref, Ptr self;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_val;}Ptr operator-(){return _node-_val;}//__list_iteratorT,Ref,Ptr operator()self operator(){_node _node-_next;return *this;}__list_iteratorT, Ref, Ptr operator(int)//self operator(int){//__list_iteratorT, Ref, Ptr tmp(*this);self tmp(*this);_node _node-_next;return tmp;}__list_iteratorT, Ref, Ptr operator--()//self operator--(int){_node _node-_prev;return *this;}//__list_iteratorT, Ref, Ptr operator--(int)self operator--(int){//__list_iteratorT, Ref, Ptr tmp(*this);self tmp(*this);_node _node-_prev;return tmp;}bool operator(const __list_iteratorT, Ref, Ptr it){return _node it._node;}bool operator!(const __list_iteratorT, Ref, Ptr it){return _node ! it._node;}};//templateclass T//struct __list_const_iterator//{// typedef list_nodeT Node;// Node* _node;// __list_const_iterator(Node* node)// :_node(node)// {}// const T operator*()// {// return _node-_val;// }// __list_const_iteratorT operator()// {// _node _node-_next;// return *this;// }// __list_const_iteratorT operator(int)// {// __list_const_iteratorT tmp(*this);// _node _node-_next;// return *this;// }// bool operator(const __list_const_iteratorT it)// {// return _node it._node;// }// bool operator!(const __list_const_iteratorT it)// {// return _node ! it._node;// }//};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;//这样设计太冗余了//typedef __list_const_iteratorT const_iterator;//这样设计const迭代器是不行的因为const迭代器期望修饰内容不被修改//这样设计迭代器本身不能修改//typedef const _list_iteratorT const_iterator;//如何设计const对象的iterator//const T* ptr1;//ptr1本身不能修改//T* const ptr2;//ptr2指向的内容不能修改iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin()const{return _head-_next;}const_iterator end()const{return _head;}void empty_init(){_head new Node;_head-_prev _head;_head-_next _head;_size 0;}//构造函数list(){empty_init();}list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}const listT operator(listT lt){swap(lt);return *this;}void clear(){if (_head ! nullptr){iterator it begin();while (it ! end()){it erase(it);}_size 0;}}~list(){clear();delete _head;_head nullptr;_size 0;}//void push_back(const T x)//{// Node* tail new Node(x);// tail-_prev _head-_prev;// tail-_prev-_next tail;// _head-_prev tail;// tail-_next _head;//}void push_back(const T x){//Node* tail _head-_prev;//Node* newnode new Node(x);//newnode-_prev tail;//tail-_next newnode;//_head-_prev newnode;//newnode-_next _head;insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(end()--);}void pop_front(){erase(begin());}//在pos位置插入数据iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;}//删除pos位置的数据iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;--_size;delete cur;return next;}size_t size()const{//const_iterator it begin();//size_t size 0;//while (it ! end())//{// size;// it;//}//return size;return _size;}private:Node* _head;size_t _size;};
