网站申请支付宝接口,给个龙做罗拉的网站,网站建设需要实现哪些目标,医院网站内链优化STL系列学习参考#xff1a;
C STL系列__zwy的博客-CSDN博客https://blog.csdn.net/bite_zwy/category_12838593.html
学习C STL的三个境界#xff0c;会用#xff0c;明理#xff0c;能扩展#xff0c;STL中的所有容器都遵循这个规律#xff0c;下面我们就按照这三个境…STL系列学习参考
C STL系列__zwy的博客-CSDN博客https://blog.csdn.net/bite_zwy/category_12838593.html
学习C STL的三个境界会用明理能扩展STL中的所有容器都遵循这个规律下面我们就按照这三个境界来学习list
一、认识标准库中的list
list的参考文档
cplusplus.com/reference/list/list/?kwlisthttps://cplusplus.com/reference/list/list/?kwlist头文件为list list 成员变量 list是C标准库提供的类模板本质上是一个双向带头循环链表.
结构如下图所示 二、list的的常用接口
1、Construct 构造函数 1、list默认构造构造空的list
listint mylist1;
liststring mylist2;
//list中的元素类型为 vectorint
listvectorint mylist3; 默认构造的list元素个数都是0. 2、 list (size_type n, const value_type val) 构造的list中包含n个值为val的元素 //使用n个value构造
listint mylist1(10, 5);
liststring mylist2(3,hellolist);
//list中的元素类型为 vectorint
// 第二个参数是vector的initializer list构造
listvectorint mylist3(5,{1,2,3,4,5}); 其中mylist3有5个元素每个元素是size为5的vector. 3、list (const list x重点 拷贝构造 //使用n个value构造
listint mylist1(10, 5);
liststring mylist2(3,hellolist);
//list中的元素类型为 vectorint
// 第二个参数是vector的initializer list构造
listvectorint mylist3(5,{1,2,3,4,5});//拷贝构造
listint copy1(mylist1);
liststring copy2(mylist2);
listvectorint copy3(mylist3); 拷贝构造时要注意拷贝构造对象和被拷贝对象的实例化类型要相同否则无法构造。 4、list (InputIterator first, InputIterator last) 迭代器区间构造 //迭代器区间构造
vectorint v{ 1,2,3,4,5 };
//利用vector的整个区间构造
listint listint(v.begin(), v.end());string s(hellolist);
//使用string的部分区间构造
listchar listchar(s.begin() 1, s.end() - 2);//使用vectorvectorint 的迭代器区间
vectorvectorint vv(10, { 1,3,5,7,9 });
listvectorint listv(vv.begin() 2, vv.end() - 3); 使用迭代器区间构造也需要保证类型匹配 5、list的initializer list 构造 //list的initializer list 构造
listint list_int{ 1,2,3,4,5 };
liststring list_str{ hellolist,string,vector,list };
//list的initializer list 构造中嵌套了vector的initializer list 构造
listvectorint list_v{ {1,2,3},{3,4,5},{4,5,6} }; list 同样支持C11提出的initializer list 构造。 2、list iterator重点
此处大家可暂时将迭代器iterator理解成一个指针该指针指向list中的某个节点。
list的迭代器iterator只支持和--等自增自减操作不支持和-。
1、beginend 返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器 2、rbeginrend 返回第一个元素的 reverse_iterator, 即 end 位置 返回最后一个元素下一个位 置 reverse_iterator, 即 begin 位置 begin 与 end 为正向迭代器对迭代器执行 操作迭代器向后移动 rbegin(end) 与 rend(begin) 为反向迭代器对迭代器执行 操作迭代器向前移动 3、迭代器遍历 正向迭代器遍历 liststring list_s{ apple,banana,orange,grape,mango,strawberry};
liststring::iterator it list_s.begin();
while (it ! list_s.end())
{//迭代器支持解引用cout *it endl;it;
} 反向迭代器遍历 liststring list_s{ apple,banana,orange,grape,mango,strawberry};
liststring::reverse_iterator it list_s.rbegin();
while (it ! list_s.rend())
{//迭代器支持解引用cout *it endl;it;
} 3、Capacity 容量 1、empty 检查list是否为空为空返回true否则返回false listint list_int;
if (list_int.empty())cout list_int为空 endl;
elsecout list_int不为空 endl;liststring list_str{ 2,hellolist };
if (list_str.empty())cout list_str为空 endl;
elsecout list_str不为空 endl; 2、size 返回list当前的有效节点个数 listint myints{ 1,2,3,4,5 };
cout myints size: myints.size() endl;listchar mychars{ a,b,c,d,e,f };
cout mychars size: mychars.size() endl;liststring mystrs{ apple,banana,grape,strawberry};
cout mystrs size: mystrs.size() endl; 4、Element access list 元素访问 1、front 返回list的第一个节点中值的引用如果list中的元素被const修饰那么就返回const 引用. listint myints{ 1,2,3,4,5 };
cout myints.front() is: myints.front() endl;myints.front() - 10;
cout Now myints.front() is: myints.front() endl; 2、back 返回list的最后一个节点中值的引用如果list中的元素被const修饰那么同样返回const 引用. liststring mystrs{ string,vector,linux,windows};
cout mystrs.back() is: mystrs.back() endl;mystrs.back().append(WINDOWS);
cout Now mystrs.back() is: mystrs.back() endl; 3、const_reference 返回const引用的情况 const listint c_list{ 1,2,3,4,5 };
//list中元素被const修饰front和back返回const引用不能修改
//c_list.front() 10;
//c_list.back() - 10; 5、list modifiers 增删查改 list有关增删查改的接口很多我们只挑重点的来讲 1、push_front 在list首元素前插入值为val的元素即头插 2、push_back 在list尾部插入值为val的元素即尾插 void Test_listpush()
{vectorint v{ 1,2,3,4,5 };listint mylist(v.begin(), v.end());cout 插入前: endl;for (auto e : mylist){cout e ;}cout endl;mylist.push_front(0); mylist.push_back(6);cout 插入后 endl;for (auto e : mylist){cout e ;}cout endl;
} 3、pop_front 删除list中第一个元素 4、pop_back 删除list中最后一个元素 void Test_listpop()
{listchar mylist{ a,b,c,d,e };cout 删除前: endl;for (auto e : mylist){cout e ;}cout endl;mylist.pop_front(); mylist.pop_back();cout 删除后 endl;for (auto e : mylist){cout e ;}cout endl;
} 5、insert 在list position 位置前插入值为val的元素其中position是一个迭代器 如果成功插入则返回新插入的第一个元素的迭代器。 void Test_listinsert()
{liststring mylist{ Java,C,PHP,Python,C };cout insert前: endl;for (auto e : mylist){cout e ;}cout endl;//在position位置前插入valmylist.insert(mylist.begin(), bash);//在position位置前 插入 n个valmylist.insert(mylist.begin(), 3, C#);//在position位置前 插入一段迭代器区间vectorstring v{ Go,Rust,SQL };mylist.insert(mylist.end(), v.begin(), v.end());cout insert 后 endl;for (auto e : mylist){cout e ;}cout endl;
} 6、erase 删除list position位置的元素其中position同样是一个迭代器。返回值是一个迭代器指向被删除元素之后的那个元素。如果被删除的元素是list中的最后一个元素那么返回end erase的返回值非常重要有关list的迭代器失效问题 void Test_erase()
{liststring mylist{ Java,C,PHP,Python,C,bash,Go,Rust,SQL};cout erase前 endl;for (auto e : mylist){cout e ;}cout endl;//删除position位置的元素mylist.erase(mylist.begin());mylist.erase(--mylist.end());//删除一段迭代器区间[firsr,last) 左闭右开mylist.erase(mylist.begin(), --mylist.end());cout erase后 endl;for (auto e : mylist){cout e ;}cout endl;
} 7、swap 交换两个类型相同的list中的元素 void printlist(listint l)
{for (auto e : l){cout e ;}cout endl;
}
void Test_swap()
{listint list1{ 1,3,5,7,9 };listint list2{ 2,4,6,8,10 };cout swap前 endl;printlist(list1);printlist(list2);list1.swap(list2);cout swap后 endl;printlist(list1);printlist(list2);
} 8、clear 清除list中的所有元素 void Test_clear()
{liststring list_str{clear,swap,push_back,insert,erase,pop_front};cout clear前 endl;for (auto e : list_str){cout e ;}cout endl;list_str.clear();cout clear后 endl;for (auto e : list_str){cout e ;}
} 9、resize 如果n小于当前list的sizesize减少到前n个元素并删除超出的元素。 如果n大于当前容器的size则在末尾插入所需的元素,如果指定了val则将新元素初始化为val的否则将其进行值初始化。 nlist当前size的情况 void Test_resize()
{listint list_int{ 1,2,3,4,5 };cout resize前 endl;for (auto e : list_int){cout e ;}cout endl;list_int.resize(3);cout resize前 endl;for (auto e : list_int){cout e ;}
} nlist 当前size的情况 void Test_resize()
{listint list_int{ 1,2,3,4,5 };cout resize前 endl;for (auto e : list_int){cout e ;}cout endl;//不给value的情况 初始化默认值list_int.resize(10);cout resize前 endl;for (auto e : list_int){cout e ;}
} void Test_resize()
{listint list_int{ 1,2,3,4,5 };cout resize前 endl;for (auto e : list_int){cout e ;}cout endl;//给value就用value初始化list_int.resize(10,6);cout resize前 endl;for (auto e : list_int){cout e ;}
} 10、emplace系列接口 list 的emplace系列接口涉及到C11可变参数模板以及右值引用的移动语义问题在C11讲解中对emplace的使用及原理做了详细讲解大家请移步至下面这篇博文 深入探索C11 第三弹C11完结迈进高效编程的新纪元-CSDN博客https://blog.csdn.net/bite_zwy/article/details/143832840?spm1001.2014.3001.5501 三、list的迭代器失效问题重点 前面说过大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 接下来看一个迭代器失效的例子: void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值l.erase(it);it;}
} erase函数执行后it 指向的节点被释放此时 it 已经失效下面对it就会导致错误这就是list的迭代器失效问题 解决办法 之前我们说过erase会返回被删除的节点的下一个位置的迭代器所以我们只需要在使用it前将erase的返回值重新赋值给it即可. // 改正
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){it l.erase(it);}
} 四、list的模拟实现 1、List_Node的实现 // List的节点类
templateclass T
struct ListNode
{ListNode(const T val T()): _prev(nullptr), _next(nullptr), _val(val){}ListNodeT* _prev;ListNodeT* _next;T _val;
}; 2、iterator 和const_iterator的封装 List 的迭代器 迭代器有两种实现方式具体应根据容器底层数据结构实现 1. 原生态指针比如vector 2. 将原生态指针进行封装因迭代器使用形式与指针完全相同因此在自定义的类中必须实现以下方法 1. 指针可以解引用迭代器的类中必须重载operator*() 2. 指针可以通过-访问其所指空间成员迭代器类中必须重载oprator-() 3. 指针可以向后移动迭代器类中必须重载operator()与operator(int) 至于operator--()/operator--(int)释放需要重载根据具体的结构来抉择双向链表可以向前 移动所以需要重载如果是forward_list就不需要重载-- 4. 迭代器需要进行是否相等的比较因此还需要重载operator()与operator!() templateclass T, class Ref, class Ptr
class ListIterator
{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;// Ref 和 Ptr 类型需要重定义下实现反向迭代器时需要用到
public:typedef Ref Ref;typedef Ptr Ptr;
public://// 构造ListIterator(Node* node nullptr): _node(node){}//// 具有指针类似行为Ref operator*(){return _node-_val;}Ptr operator-(){return (operator*());}//// 迭代器支持移动Self operator(){_node _node-_next;return *this;}Self operator(int){Self temp(*this);_node _node-_next;return temp;}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self temp(*this);_node _node-_prev;return temp;}//// 迭代器支持比较bool operator!(const Self l)const{return _node ! l._node;}bool operator(const Self l)const{return _node ! l._node;}Node* _node;
};template class T
struct list_const_iterator
{typedef List_NodeT Node;typedef list_const_iteratorT Self;Node* _node;//list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_data;}Self operator(){_node _node-_next;return *this;}const T* operator-(){return _node-_data;}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 s)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}
}; 3、 reverse_list_Iierator实现 通过前面例子知道反向迭代器的就是正向迭代器的--反向迭代器的--就是正向迭代器的因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对 正向迭代器的接口进行包装即可。 templateclass Iteratorclass ReverseListIterator{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的一个类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;public://// 构造ReverseListIterator(Iterator it): _it(it){}//// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator-(){return (operator*());}//// 迭代器支持移动Self operator(){--_it;return *this;}Self operator(int){Self temp(*this);--_it;return temp;}Self operator--(){_it;return *this;}Self operator--(int){Self temp(*this);_it;return temp;}//// 迭代器支持比较bool operator!(const Self l)const{return _it ! l._it;}bool operator(const Self l)const{return _it ! l._it;}Iterator _it;};4、list类模板的实现 templateclass Tclass list{typedef ListNodeT Node;public:// 正向迭代器typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;// 反向迭代器typedef ReverseListIteratoriterator reverse_iterator;typedef ReverseListIteratorconst_iterator const_reverse_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T value T()){CreateHead();for (int i 0; i n; i)push_back(value);}template class Iteratorlist(Iterator first, Iterator last){CreateHead();while (first ! last){push_back(*first);first;}}list(const listT l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换listT temp(l.begin(), l.end());this-swap(temp);}listT operator(listT l){this-swap(l);return *this;}~list(){clear();delete _head;_head nullptr;}///// List的迭代器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);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}///// List的容量相关size_t size()const{Node* cur _head-_next;size_t count 0;while (cur ! _head){count;cur cur-_next;}return count;}bool empty()const{return _head-_next _head;}void resize(size_t newsize, const T data T()){size_t oldsize size();if (newsize oldsize){// 有效元素个数减少到newsizewhile (newsize oldsize){pop_back();oldsize--;}}else{while (oldsize newsize){push_back(data);oldsize;}}}// List的元素访问操作// 注意List不支持operator[]T front(){return _head-_next-_val;}const T front()const{return _head-_next-_val;}T back(){return _head-_prev-_val;}const T back()const{return _head-_prev-_val;}// List的插入和删除void push_back(const T val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* pNewNode new Node(val);Node* pCur pos._node;// 先将新节点插入pNewNode-_prev pCur-_prev;pNewNode-_next pCur;pNewNode-_prev-_next pNewNode;pCur-_prev pNewNode;return iterator(pNewNode);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){// 找到待删除的节点Node* pDel pos._node;Node* pRet pDel-_next;// 将该节点从链表中拆下来并删除pDel-_prev-_next pDel-_next;pDel-_next-_prev pDel-_prev;delete pDel;return iterator(pRet);}void clear(){Node* cur _head-_next;// 采用头删除删除while (cur ! _head){_head-_next cur-_next;delete cur;cur _head-_next;}_head-_next _head-_prev _head;}void swap(bite::listT l){std::swap(_head, l._head);}private:void CreateHead(){_head new Node;_head-_prev _head;_head-_next _head;}private:Node* _head;};五、list和vector的对比 std:liststd::vector底层存储结构 带头结点的双向循环链表。每个元素在内存中不连续存储通过节点中的指针指向下一个元素。 动态数组结构。元素在内存中是连续存储的。随机访问不支持高效的随机访问。要访问中间的元素需要从头部或尾部开始遍历链表时间复杂度为O(N)其中N是到目标元素的距离。支持高效的随机访问。可以通过下标运算符[]直接访问元素时间复杂度为O1。插入和删除元素在任意位置插入和删除元素效率高。在链表中间插入或删除一个元素只需要调整指针时间复杂度为O(1)不考虑查找插入位置的时间。在末尾插入元素效率高时间复杂度一般为当需要重新分配内存时可能会更复杂。但是在中间或者开头插入 / 删除元素效率较低因为需要移动插入 / 删除位置之后的所有元素平均时间复杂度为O(N)。内存分配每次插入新元素时只需分配新节点的内存不需要重新分配整个容器的内存除非内存不足。当元素数量超过当前容量时需要重新分配一块更大的连续内存空间并且将原有元素复制到新空间中这个过程可能比较耗时。迭代器失效删除操作只会使指向被操作元素的迭代器失效其他迭代器不受影响。 在插入元素时要给所有的迭代器重新赋值因为 插入元素有可能会导致重新扩容致使原来迭代器 失效删除时当前迭代器需要重新赋值否则会失 效 空间开销 除了存储元素本身每个节点还需要额外的指针来维护链表结构所以有一定的空间开销。 没有额外的指针开销但是可能会因为内存对齐等原因 浪费少量空间。 使用 场景 需要高效存储支持随机访问不关心插入删除效率。 大量插入和删除操作不关心随机访问。 六、小结 list也是STL中很基础同时也很重要的容器是非常重要的数据结构之一在操作系统日志记录等方面都有很重要的应用值得大家深入学习。 接下来会给大家带来C STL中其他容器的深度讲解创作不易还请多多互三支持。
