namespace bittersweet { //list的优点和缺点 //优点1.按需申请释放空间不需要扩容 //2.任意位置插入删除 //缺点1.不支持下标的随机访问 templateclass T class list_node { //list_node 本身不是一个完整类型它只是一个模板template只有加上 T 才能实例化为具体类型。 T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T data T()) //“定义一个构造函数它接收一个类型为 T 的常量引用作为参数。如果调用时没有提供参数则自动使用 T 类型的默认值例如 int 为 0自定义对象则调用其默认构造函数 //这行代码把“必须给数据才能造节点”的规则打破了。它允许你创建一个数据域为零或空对象的空节点 //这在链表操作中非常有用比如创建哨兵位/头节点时往往不需要存有效数据。 :_data(data) , _next(nullptr) , _prev(nullptr) {} //这个函数不是默认构造函数不是因为T类型不固定而且因为传入了参数默认构造函数的定义是无参调用 //这个明显不符合要求但是如果进行无参构造的话_data容易变成垃圾值或者空有未知风险 }; //每一个独立的模板类都需要自己的 template... 头标。 templateclass T struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT Self; Node* _node; list_iterator(Node* node) :_node(node) { } T operator*() { return _node-_data; } Self operator() { _node _node-_next; return *this } Self operator--() { _node _node-_prev; return *this } bool operator!(const Self s) { return _node ! s._node; } bool operator(const Self s) { return _node s._node; } }; templateclass T class list { typedef list_nodeT Node; public: typedef list_iteratorT iterator; iterator begin() { iterator it(_head-_next); return it; } iterator end() { return _head; } void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } list() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } list(const listT lt) { empty_init(); for (auto e lt) { push_back(e); } } void swap(list) ~list() { clear(); delete _head; _head nullptr; } void clear() { auto it begin(); while (it ! end()) { it erase(it); } } void push_back(const T x) { Node* newnode new Node(x); Node* tail _head-_prev; tail-_next newnode; newnode-_prev tail; newnode-_next _head; _head-prev newnode; _size; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void 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; --_size; return next; } void push_front(const T x) { insert(begin(), x); } void push_back(const T x) { insert(end(), x); } void insert(iterator pos, const T x) { Node* cur pos.node; Node* prev cur-prev; Node* newnode new Node(x); newnode-_next cur; cur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; } size_t size()const { return _size; } bool empty()const { return _size 0; } private: Node* _head; size_t _size; }; }一些值得注意的知识点在C11之后auto作为一个自动类型推导的关键字本身不代表任何具体类型而是让编译器根据变量的初始化表达式自动推断出该变量的实际类型C20之后可以作为函数普通函数参数使用还有一点auto必须在声明时初始化否则编译器无法推导类型而且auto在自动初始化时会默认失去引用和const属性这一点值得注意其次迭代器是C类型中的一种却并不简单是一个begin()或者end()返回的指针的重命名是一个复杂的类里面封装了当前节点指针以及遍历所需要的逻辑而且begin和end()的返回值不能使用该类型指针来接收迭代器是一个类对象而指针是一个原生地址这是两个完全不同的数据类型特性原生指针 (int*)迭代器 (iterator)本质内存地址整数类对象Class Object包含内容仅包含位置信息包含位置 移动逻辑 边界检查自增 ()简单的内存地址加法调用重载函数可能涉及复杂的树/链表跳转通用性只能用于连续内存可用于所有 STL 容器赋值给指针✅ 可以❌ 通常不行除非是 vector尽管能逃过但是还是建议使用迭代器这其中的封装包括运算符重载关于运算符重载值得注意的是一段如下的代码重载前面的迭代器代表了返回值类型而绑定的对象就是其所在的类名我的意思是除了这个类的对象在使用重载后的运算符会有特殊效果其他的类型使用这个运算符并不会有特殊效果运算符重载是一种私密并非公开的iterator operator() { current current-next; return *this; }关于为什么模板同时需要T,RefPtr三个模板在我们定义迭代器的时候会很容易注意到我们除了T的标准模板外我们还定义了RefPtr分别为返回值和引用的模板为什么要这么做我们明明可以定义返回值为TT*的运算符重载但是偏偏就是多定义两个模板原因很简单当我们需要常量迭代器的时候此时的返回值就不能是T*,T代码就会产生报错,,我们此时传入Ref,Ptr的好处就来了当我们需要常量迭代器的时候只需要传入const T,const T*就能解决我们的问题