admin管理员组

文章数量:1130349

STL

一、list介绍

列表是序列容器，允许在序列内的任何位置执行恒定时间插入和擦除操作，以及双向迭代

列表容器作为双向链表实现;双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个和后一个元素

它们与forward_list非常相似：主要区别在于forward_list对象是单链表，因此它们只能向前迭代，从而更简单高效

与其他基本标准序列容器（array、vector和 deque）相比，list在任意位置进行插入、移除元素的执行效率更高

与其他序列容器相比，list和 forward_lists 的主要缺点是不支持任意位置的随机访问。例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要这些元素之间的距离的线性时间。它们还会消耗一些额外的内存来保持与每个元素关联的链接信息（这也许是影响存储小数据的大list的因素）

优点	缺点
任意位置高效插入删除	不能支持随机访问

二、list接口

详情可见

list - C++ Reference (cplusplus.com)/

1.常见构造

函数名称	功能说明
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)区间中的元素构造list

2.容量操作

函数名称	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

3.访问与遍历

函数名称	接口说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend	返回第一个元素的reverse_iterator，即end位置。返回最后一个元素下一个位置的reverse_iterator，即begin位置
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

rbegin与rend为反向迭代器，对迭代器执行++操作，迭代器向前移动

4.修改操作

函数名称	接口说明
push_front	在list首元素钱插入值为val的元素
pop_front	删除list中的第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list最后一个元素
insert	在list position位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

5.list迭代器失效

三、list模拟实现

迭代器实现

		iterator begin() { return iterator(_head->_next); }//匿名构造迭代器对象iterator begin()const { return iterator(_head->_next); }

返回值返回一个匿名对象构造的迭代器对象

为什么const还可以构造普通迭代器？

因为const修饰*this，也就是一个指针，指针本身不可以改变，但是可以对齐指针指向的内容修改。也就是_head本身不可以改变，但是_head指向的next可以改变

对于常量迭代器对象，可以采用重新实现普通迭代的方式，但是这种方式过于繁琐，并且与普通迭代器的事项方式基本相同，因此采用类模板多个参数的处理方式

//常量迭代器类template<class T>struct __list_const_iterator{typedef list_node<T> node;typedef __list_const_iterator<T> self;//类对象本身node* _node;__list_const_iterator(node* n)//迭代器初始化:_node(n){}const T& operator* ()//不能修改数据{return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& li){return _node != li._node;}bool operator==(const self& li){return _node == li._node;}};

自定义类型处理

list中除了可以存储内置类型之外，还可以存放自定义类型数据，因此还需要对list的迭代器做自定义类型内容的处理

	struct test_A{int _a1;int _a2;test_A(int a1=0, int a2=0):_a1(a1), _a2(a2){}};void test_2(){list<test_A> lt;//指定内部为自定义类型lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(2, 2));list<test_A>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;}

对于上图这样的一个简单自定义类型，如果仍然使用原来的迭代器输出方式，会产生报错

可将其改为

cout << (*it)._a1 << " ";

但是显然这样的输出方式并不符合一般的书写模式，一般情况下访问指针对象的成员并不会先解引用再读取成员。而是直接使用->的方式，因此需要重载->操作符

		T* operator->()//->运算符重载{return &_node->data}//此时的调用为cout<<it->_a1<<" ";
//相当于it.operator->()->_a1,也就是(test_A*) ->_a1
//但是为了可读性编译器会自动省略一个箭头

insert操作

与vector不同，list的insert操作传入的是迭代器，并且不会出现迭代器失效的位置，因为迭代器的相对位置并没有改变，指向也不改变

#pragma once
#include<iostream>
#include<assert.h>
using std::cout;
using std::endl;
namespace my_list
{//节点类template<class T>struct list_node//默认访问权限是public，不对成员的访问限制{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x=T())//匿名对象做缺省值，T需要默认构造:_next(nullptr), _data(x), _prev(nullptr){}};//迭代器是原生指针或者是自定义类型//普通迭代器类template<class T,class Ref,class Ptr>//Ref与Ptr是为了适用常量迭代器,Ref=T&	Ptr=T*struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref,Ptr> self;//类对象本身node* _node;__list_iterator(node* n)//迭代器初始化:_node(n){}Ref operator* ()//常量迭代器与普通迭代器只有返回值不同{return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++()//返回迭代器类对象{_node = _node->_next;return *this;}self& operator++(int)//int只用于标识后置++{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& li){return _node != li._node;}bool operator==(const self& li){return _node == li._node;}};//链表类template<class T>class list{typedef list_node<T> node;//节点public:typedef __list_iterator<T,T&,T*> iterator;//普通迭代器typedef __list_iterator<T, const T&,const T*> const_iterator;//常量迭代器//typedef __list_const_iterator<T> const_iterator;//常量迭代器void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template<class Iterator>list(Iterator first, Iterator last){empty_init();//空初始化while (first != last){push_back(*first);first++;}}void swap(list<T>& tmp)//套用std库中的swap方便实现拷贝{std::swap(_head, tmp._head);}list(const list<T>& cst)//拷贝构造{empty_init();list<T> tmp(cst.begin(), cst.end());swap(tmp);}list<T>& operator=(list<T> lt)//赋值构造//如果引用传参会导致拷贝{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}//迭代器iterator begin() { return iterator(_head->_next); }//匿名构造迭代器对象const_iterator begin()const { return const_iterator(_head->_next); }iterator end() { return iterator(_head); }const_iterator end()const { return const_iterator(_head); }//增删查改void push_back(const T& x){node* tail = _head->_prev;node* newnode = new node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;newnode->_data = x;}//void push_back(const T& x)//{//	insert(end(), x);//}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void insert(iterator pos,const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node();prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;new_node->_data = x;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it=erase(it);}}private:node* _head;//哨兵位，不含数据};template<typename T>void show(const list<T>& ls){//auto it = ls.begin();//while (it != ls.end())//{//	cout << *it << " ";//	++it;//}//cout << endl;for (auto ch : ls){cout << ch << " ";}cout << endl;}void test_1(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);show(l1);const list<int> lt1;//const对象在定义的时候是不具有const属性的，否则无法进行初始化list<int> l2;l2 = l1;show(l2);list<int> l3 = l1;show(l3);}struct test_A{int _a1;int _a2;test_A(int a1=0, int a2=0):_a1(a1), _a2(a2){}};void test_2(){list<test_A> lt;//指定内部为自定义类型lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(3, 3));list<test_A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " ";cout << it->_a1 << " " << it->_a2 <<endl;it++;}cout << endl;}void test_3(){list<test_A> lt;lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(3, 3));lt.insert(lt.begin(), test_A(5,5));list<test_A>::iterator it_2 = lt.begin();while (it_2 != lt.end()){//cout << (*it)._a1 << " ";cout << it_2->_a1 << " " << it_2->_a2 << endl;it_2++;}}
}

STL

一、list介绍

列表是序列容器，允许在序列内的任何位置执行恒定时间插入和擦除操作，以及双向迭代

列表容器作为双向链表实现;双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个和后一个元素

它们与forward_list非常相似：主要区别在于forward_list对象是单链表，因此它们只能向前迭代，从而更简单高效

与其他基本标准序列容器（array、vector和 deque）相比，list在任意位置进行插入、移除元素的执行效率更高

与其他序列容器相比，list和 forward_lists 的主要缺点是不支持任意位置的随机访问。例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要这些元素之间的距离的线性时间。它们还会消耗一些额外的内存来保持与每个元素关联的链接信息（这也许是影响存储小数据的大list的因素）

优点	缺点
任意位置高效插入删除	不能支持随机访问

二、list接口

详情可见

list - C++ Reference (cplusplus.com)/

1.常见构造

函数名称	功能说明
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)区间中的元素构造list

2.容量操作

函数名称	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

3.访问与遍历

函数名称	接口说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend	返回第一个元素的reverse_iterator，即end位置。返回最后一个元素下一个位置的reverse_iterator，即begin位置
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

rbegin与rend为反向迭代器，对迭代器执行++操作，迭代器向前移动

4.修改操作

函数名称	接口说明
push_front	在list首元素钱插入值为val的元素
pop_front	删除list中的第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list最后一个元素
insert	在list position位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

5.list迭代器失效

三、list模拟实现

迭代器实现

		iterator begin() { return iterator(_head->_next); }//匿名构造迭代器对象iterator begin()const { return iterator(_head->_next); }

返回值返回一个匿名对象构造的迭代器对象

为什么const还可以构造普通迭代器？

因为const修饰*this，也就是一个指针，指针本身不可以改变，但是可以对齐指针指向的内容修改。也就是_head本身不可以改变，但是_head指向的next可以改变

对于常量迭代器对象，可以采用重新实现普通迭代的方式，但是这种方式过于繁琐，并且与普通迭代器的事项方式基本相同，因此采用类模板多个参数的处理方式

//常量迭代器类template<class T>struct __list_const_iterator{typedef list_node<T> node;typedef __list_const_iterator<T> self;//类对象本身node* _node;__list_const_iterator(node* n)//迭代器初始化:_node(n){}const T& operator* ()//不能修改数据{return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& li){return _node != li._node;}bool operator==(const self& li){return _node == li._node;}};

自定义类型处理

list中除了可以存储内置类型之外，还可以存放自定义类型数据，因此还需要对list的迭代器做自定义类型内容的处理

	struct test_A{int _a1;int _a2;test_A(int a1=0, int a2=0):_a1(a1), _a2(a2){}};void test_2(){list<test_A> lt;//指定内部为自定义类型lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(2, 2));list<test_A>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;}

对于上图这样的一个简单自定义类型，如果仍然使用原来的迭代器输出方式，会产生报错

可将其改为

cout << (*it)._a1 << " ";

但是显然这样的输出方式并不符合一般的书写模式，一般情况下访问指针对象的成员并不会先解引用再读取成员。而是直接使用->的方式，因此需要重载->操作符

		T* operator->()//->运算符重载{return &_node->data}//此时的调用为cout<<it->_a1<<" ";
//相当于it.operator->()->_a1,也就是(test_A*) ->_a1
//但是为了可读性编译器会自动省略一个箭头

insert操作

与vector不同，list的insert操作传入的是迭代器，并且不会出现迭代器失效的位置，因为迭代器的相对位置并没有改变，指向也不改变

#pragma once
#include<iostream>
#include<assert.h>
using std::cout;
using std::endl;
namespace my_list
{//节点类template<class T>struct list_node//默认访问权限是public，不对成员的访问限制{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x=T())//匿名对象做缺省值，T需要默认构造:_next(nullptr), _data(x), _prev(nullptr){}};//迭代器是原生指针或者是自定义类型//普通迭代器类template<class T,class Ref,class Ptr>//Ref与Ptr是为了适用常量迭代器,Ref=T&	Ptr=T*struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref,Ptr> self;//类对象本身node* _node;__list_iterator(node* n)//迭代器初始化:_node(n){}Ref operator* ()//常量迭代器与普通迭代器只有返回值不同{return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++()//返回迭代器类对象{_node = _node->_next;return *this;}self& operator++(int)//int只用于标识后置++{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& li){return _node != li._node;}bool operator==(const self& li){return _node == li._node;}};//链表类template<class T>class list{typedef list_node<T> node;//节点public:typedef __list_iterator<T,T&,T*> iterator;//普通迭代器typedef __list_iterator<T, const T&,const T*> const_iterator;//常量迭代器//typedef __list_const_iterator<T> const_iterator;//常量迭代器void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template<class Iterator>list(Iterator first, Iterator last){empty_init();//空初始化while (first != last){push_back(*first);first++;}}void swap(list<T>& tmp)//套用std库中的swap方便实现拷贝{std::swap(_head, tmp._head);}list(const list<T>& cst)//拷贝构造{empty_init();list<T> tmp(cst.begin(), cst.end());swap(tmp);}list<T>& operator=(list<T> lt)//赋值构造//如果引用传参会导致拷贝{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}//迭代器iterator begin() { return iterator(_head->_next); }//匿名构造迭代器对象const_iterator begin()const { return const_iterator(_head->_next); }iterator end() { return iterator(_head); }const_iterator end()const { return const_iterator(_head); }//增删查改void push_back(const T& x){node* tail = _head->_prev;node* newnode = new node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;newnode->_data = x;}//void push_back(const T& x)//{//	insert(end(), x);//}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void insert(iterator pos,const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node();prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;new_node->_data = x;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it=erase(it);}}private:node* _head;//哨兵位，不含数据};template<typename T>void show(const list<T>& ls){//auto it = ls.begin();//while (it != ls.end())//{//	cout << *it << " ";//	++it;//}//cout << endl;for (auto ch : ls){cout << ch << " ";}cout << endl;}void test_1(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);show(l1);const list<int> lt1;//const对象在定义的时候是不具有const属性的，否则无法进行初始化list<int> l2;l2 = l1;show(l2);list<int> l3 = l1;show(l3);}struct test_A{int _a1;int _a2;test_A(int a1=0, int a2=0):_a1(a1), _a2(a2){}};void test_2(){list<test_A> lt;//指定内部为自定义类型lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(3, 3));list<test_A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " ";cout << it->_a1 << " " << it->_a2 <<endl;it++;}cout << endl;}void test_3(){list<test_A> lt;lt.push_back(test_A(1, 1));lt.push_back(test_A(2, 2));lt.push_back(test_A(3, 3));lt.insert(lt.begin(), test_A(5,5));list<test_A>::iterator it_2 = lt.begin();while (it_2 != lt.end()){//cout << (*it)._a1 << " ";cout << it_2->_a1 << " " << it_2->_a2 << endl;it_2++;}}
}

本文标签： STL