实现具备C++11现代特性的STL——list篇（使用shared_ptr智能指针实现，解决了循环引用问题）

实现具备C++11现代特性的STL——list篇（使用shared_ptr智能指针实现，解决了循环引用问题）

引言

本程序设计目的旨在熟悉C++11常见语法的使用（此程序重点在于理解并通过一个实例解决循环引用问题），实际上无论是从代码复杂度还是资源消耗上，都推荐使用裸指针实现list（STL使用的也是裸指针），也就是说，本程序就性能等来说，并不是一个优秀的设计（比如说明明使用了智能指针，但还需要设计析构函数来解决循环引用问题）

设计思路

对于使用shared智能指针实现list，最大的挑战其实就是循环引用问题，这里想到了两种解决方案：

1. 最简单的是将节点中的两个指针成员设置为weak类型，然后再控制一个set指向各个节点，以避免循环引用问题，erase节点时也可以通过set实现O(1)的查找（缺点是需要额外开一个set，空间复杂度会进一步提高）
2. 最复杂的是将节点中的两个指针成员一个设置为weak，另一个设置为shared（这里为直观，选择将next设置为shared的方案），但这样设计时，由于循环链表，所以首尾节点仍然会造成循环引用，这时，就需要创建一个析构函数，用于解环（即 在析构时将尾节点的shared指针设置为nullptr，以避免两个shared同时指向哨兵位）同时，方案二还需要额外注意，尾节点初始化时要用shared_ptr _head进行拷贝构造，而不能采取裸指针方案，裸指针初始化会导致两shared产生两独立的引用计数，最终不解环，也无需解环，但会导致对哨兵位的重复释放

既然是为了熟悉语法并深入理解循环引用，接下来会实现方案二这个更具挑战性的思路

源码

#pragmaonce#include<memory>#include<initializer_list>#include<utility>#include<assert.h>namespacedzh{template<classT>structListNode{ListNode()=default;ListNode(constT&value):_value(value){}T _value=T();std::shared_ptr<ListNode>_next=nullptr;std::weak_ptr<ListNode>_prev;// 需要注意，weak不支持使用nullptr进行初始化，若当前无需赋值，直接使用默认构造即可};template<classT>classMyList;template<classT,classRef,classPtr>classIterator{usingNode=ListNode<T>;friendclassMyList<T>;public:Iterator(Node*it):_it(it){}Refoperator*(){assert(_it);return_it->_value;}Ptroperator->(){assert(_it);return&(_it->_value);}Iteratoroperator++(){assert(_it->_next.get()!=_it);// 当迭代器的下一个节点不是自己，即有效节点个数不为空时，才能++（其实最好判断下当前迭代器是否为end，但是想判断还需要额外创建成员变量，这里直接判断有效节点个数也足够了）_it=_it->_next.get();returnIterator(_it);}Iteratoroperator++(int){assert(_it->_next.get()!=_it);Iteratornewit(_it);_it=_it->_next.get();returnnewit;}Iteratoroperator--(){assert(_it->_next.get()!=_it);_it=_it->_prev.lock().get();returnIterator(_it);}Iteratoroperator--(int){assert(_it->_next.get()!=_it);Iteratornewit(_it);_it=_it->_prev.lock().get();returnnewit;}booloperator!=(Iterator other){return_it!=other._it;}booloperator==(Iterator other){return_it==other._it;}private:Node*_it;};template<classT>classMyList{usingNode=ListNode<T>;friendclassIterator<T,T&,T*>;friendclassIterator<T,constT&,constT*>;usingiterator=Iterator<T,T&,T*>;usingconst_iterator=Iterator<T,constT&,constT*>;template<classU>friendstd::ostream&operator<<(std::ostream&os,constMyList<U>&list);public:// 构造函数创建哨兵位节点MyList(){_init();// 使用私有初始化辅助函数为构造函数们创建哨兵位节点以进行初始化操作，用以降低代码冗余度}MyList(std::initializer_list<T>init)// 这里没有采取const std::initializer_list<T>&的原因是为了仿照STL标准库中的实现，因为实际上，initializer容器内部仅存储了指针变量以及元素个数，因此，拷贝的代价很小，C++库中对于这种拷贝代价很小的容器往往采取的是传值传参（如迭代器也是如此）{_init();for(constauto&e:init){emplace_back(e);}}// 迭代器区间构造MyList(iterator begin,iterator end){_init();while(begin!=end){emplace_back(*begin++);}}MyList(const_iterator begin,const_iterator end){_init();while(begin!=end){emplace_back(*begin++);}}MyList(constMyList&other)// 拷贝构造中也要进行emplace操作，因此记得提前记得创建哨兵位{_init();for(constauto&e:other){emplace_back(e);}}MyList(MyList&&other)noexcept// 移动构造内部仅需要swap，无需emplace等操作，因此无需为this创建哨兵位***************才怪，移动结束后，匿名对象需要被析构，而析构中需要解环，也就是说需要解引用指针，因此，就连移动构造也必须初始化哨兵位{_init();swap(other);}MyList&operator=(constMyList&other)// 注意，因为还要构建移动赋值，所以这里赋值重载的参数不能为传值传参，会导致编译器无法正确选择调用哪个函数{MyListmid(other);swap(_head,mid._head);}MyList&operator=(MyList&&other)noexcept{swap(_head,other._head);}// 创建用于打破循环链表的析构函数~MyList(){_head->_prev.lock()->_next=nullptr;}iteratorbegin(){returniterator(_head->_next.get());}iteratorend(){returniterator(_head.get());}const_iteratorbegin()const{returnconst_iterator(_head->_next.get());}const_iteratorend()const{returnconst_iterator(_head.get());}// emplace系列template<class...Args>iteratoremplace(iterator pos,Args&&...args){++_size;std::shared_ptr<Node>posp=pos._it->_prev.lock()->_next;std::shared_ptr<Node>pposp=pos._it->_prev.lock()->_prev.lock()->_next;iteratorprev(pos._it->_prev.lock().get());prev._it->_next=std::make_shared<Node>(std::forward<Args>(args)...);prev._it->_next->_next=posp;pos._it->_prev=prev._it->_next;prev._it->_next->_prev=pposp;returniterator(prev._it->_next.get());}template<class...Args>voidemplace_back(Args&&...args){emplace(end(),std::forward<Args>(args)...);}template<class...Args>voidemplace_front(Args&&...args){emplace(begin(),std::forward<Args>(args)...);}iteratorinsert(iterator pos,constT&value){++_size;std::shared_ptr<Node>posp=pos._it->_prev.lock()->_next;// 由于shared需要赋值/拷贝才能触发同一引用计数，单凭裸指针初始化会造成一块空间被多个shared不同引用计数的后果，所以这里先取出初始化新节点next指针的shared类型指针std::shared_ptr<Node>pposp=pos._it->_prev.lock()->_prev.lock()->_next;// 这里同理，通过节点a的上个节点中的next成员变量，得到指向节点a的shared，用于初始化weakiteratorprev(pos._it->_prev.lock().get());prev._it->_next=std::make_shared<Node>(value);prev._it->_next->_next=posp;pos._it->_prev=prev._it->_next;prev._it->_next->_prev=pposp;returniterator(prev._it->_next.get());}iteratorinsert(iterator pos,T&&value){++_size;std::shared_ptr<Node>posp=pos._it->_prev.lock()->_next;// 由于shared需要赋值/拷贝才能触发同一引用计数，单凭裸指针初始化会造成一块空间被多个shared不同引用计数的后果，所以这里先取出初始化新节点next指针的shared类型指针std::shared_ptr<Node>pposp=pos._it->_prev.lock()->_prev.lock()->_next;// 这里同理，通过节点a的上个节点中的next成员变量，得到指向节点a的shared，用于初始化weakiteratorprev(pos._it->_prev.lock().get());prev._it->_next=std::make_shared<Node>(std::move(value));prev._it->_next->_next=posp;pos._it->_prev=prev._it->_next;prev._it->_next->_prev=pposp;returniterator(prev._it->_next.get());}voidpush_back(constT&value){insert(end(),value);}voidpush_back(T&&value){insert(end(),value);}voidpush_front(constT&value){insert(begin(),value);}voidpush_front(T&&value){insert(begin(),value);}iteratorerase(iterator pos){assert(pos!=end()&&_size>0);// 有效节点数必须大于0时，才可删除，同时，也不能删除哨兵位--_size;iteratorit(pos._it->_next.get());// 在删除之前，先找到作为返回值的迭代器pos._it->_next->_prev=pos._it->_prev;pos._it->_prev.lock()->_next=pos._it->_next;// 这里是重点，这一步是将pos节点的上个节点的_next修改，而这个_next是唯一的指向pos节点的shared指针，因此，在进行该更改之前，要确保后续不会再用到pos，也就是说，这一步要放到修改节点指针的最后一步，而这步执行后，pos节点会被自动析构，后面无需手动deletereturnit;}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}voidswap(MyList&other){std::swap(_head,other._head);std::swap(_size,other._size);}T&front(){assert(_size);return*begin();}constT&front()const{assert(_size);return*begin();}T&back(){assert(_size);return*(--end());}constT&back()const{assert(_size);return*(--end());}size_tsize()const{return_size;}boolempty()const{return_size==0;}private:std::shared_ptr<Node>_head=nullptr;size_t _size=0;// 构造函数的私有哨兵位创建辅助函数，作用是降低代码冗余性void_init(){_head=std::make_shared<Node>(T());// make系列模板参数为一个类名时，函数参数为该类的其中一个构造函数的参数_size=0;_head->_next=_head;_head->_prev=_head;}};template<classT>std::ostream&operator<<(std::ostream&os,constMyList<T>&list){ListNode<T>*ptr=list._head->_next.get();while(ptr!=list._head.get()){std::cout<<ptr->_value<<" ";ptr=ptr->_next.get();}returnos;}}

经验总结

1. 想要正确增加shared的引用计数，就必须使用shared的拷贝构造/赋值重载；想要正确为weak赋值，就必须使用shared/weak的拷贝构造/赋值重载
2. weak不具备get函数，想要获取weak指向的数据的原始指针，就必须先通过lock将weak转换为shared指针，然后再使用shared.get()才能获得原始裸指针
3. 裸指针与shared指针不能直接比较，需通过shared.get()获取裸指针再比较，以及上述提到的，为weak与shared重新赋值时，若需要pos的shared，就需要通过pos->_prev.lock()->_next;即通过当前节点的上一个节点中的shared类型的next来得到（且该流程基本固定，因为若通过下个节点找，那得到的只能是weak类型的指针，虽然可以为weak赋值，但却无法为shared赋值
4. 实现双链表时往往非常推荐使用哨兵位，可以减少特殊情况的判断，降低项目的复杂程度
5. 注意，构造函数不可以使用const修饰this，移动语义往往推荐使用noexcept进行修饰
6. 在组合创建栈的<<重载时出现了错误，原因是list成员变量在进行拷贝构造时发生了段错误（野指针），最后发现是拷贝构造中没有提前初始化哨兵位，而后想到那么移动构造仅仅是交换操作，无需插入等需求，至少可以不初始化哨兵位了吧，但事实并非如此，在测试移动构造时仍旧发生了段错误，原因是list的析构函数中需要进行解环操作，只要析构一个对象（无论是否匿名）都需要进行解环，因此，若一个对象没有初始化哨兵位，就会发生野指针，也就是说，此写法中，所有构造函数都需要初始化哨兵位，而为了避免代码冗余，采取了使用私有初始化辅助函数进行哨兵位创建的办法
7. 关于类模板的<<重载究竟使用函数模板还是普通函数，其实稍加思考就能想明白，若仅仅写成一个函数，那就不能随着T的变化生成对应的 << 重载，并且，仅仅写成函数，进行友元声明时，friend ostream& operator<<(ostream& os, const MyClass& myclass);其中的MyClass其实是类中才允许的MyClass<T>的缩写，这样等到定义<<时，如何才能表达出这个T模板参数呢？答案只有将<<重载写成函数模板(注，除了上面的通用模板友元，其实还可以声明为特定实例友元：friend ostream& operator<< (ostream&, const MyClass&); ）
8. 注意，C++标准规定,构造函数不能在后面添加const，即禁止设置为常量成员函数，原因是，这会与构造函数本身“更改成员变量，以对其初始化”的操作产生冲突，那么，这里其实会产生一个疑问，为什么const 自定义类型在初始化时可以调用构造函数呢，构造函数明明没有被设置为常量成员函数，不是说只有常量成员函数才能被const对象调用吗？其实想到这点，答案也就呼之欲出了，可以理解成，该对象的const关键字是在调用完构造函数才添加的，就类似const int i = 1,你不会疑惑为什么i明明是const类型，却还能赋值为1，底层大体也是先为int i赋值，然后再将i修饰为const