东莞营销网站建设费用网站备案名称重复

当前位置： 首页 > news >正文

东莞营销网站建设费用,网站备案名称重复,内江企业网站建设公司,wordpress导入演示数据文章目录一、list 的常用接口及其使用1、list 一般接口2、list 特殊接口3、list 排序的性能分析二、list 迭代器的实现1、迭代器的分类2、list 迭代器失效问题3、list 迭代器源码分析4、list 迭代器模拟实现4.1 普通迭代器4.2 const 迭代器4.3 完整版迭代器三、list 的模拟实现… 文章目录一、list 的常用接口及其使用1、list 一般接口2、list 特殊接口3、list 排序的性能分析二、list 迭代器的实现1、迭代器的分类2、list 迭代器失效问题3、list 迭代器源码分析4、list 迭代器模拟实现4.1 普通迭代器4.2 const 迭代器4.3 完整版迭代器三、list 的模拟实现四、vector 和 list 的区别一、list 的常用接口及其使用 1、list 一般接口 list 是可以在常数范围内在任意位置进行插入和删除的序列式容器其底层是带头双向循环链表list 常用接口的使用和 string、vector 系列容器的接口使用一样这里我就不再详细介绍具体使用细节可以查看 list 使用文档 – cplusplus.com。 构造函数 -构造函数 constructor-接口说明list (size_type n, const value_type val value_type())构造的 list 中包含n个值为val的元素list()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用 [first, last) 区间中的元素构造 list 增删查改 函数声明-接口说明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中的有效元素 注意事项 1、由于 list 的物理结构是非连续的 – 前一个节点地址和后一个节点地址的位置关系是随机的所以 list 不支持随机访问自然也就不支持 [] 操作 2、list 不支持 reserve 操作因为 list 的节点是使用时开辟使用完销毁不能预留空间 2、list 特殊接口 除了上述 STL 容器基本都有的一般接口外list 还提供一些独有的特殊操作接口如下 -函数声明-接口说明splice将 list1 中的元素转移到 list2 中remove移除 list 中的指定元素unique链表去重merge合并两个链表sort链表排序reverse链表逆置 注意事项 1、链表排序只能使用 list 提供的 sort 接口而不能使用 algorithm 提供的 sort 接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的 sort 函数需要支持 - 的随机迭代器 2、链表去重之前必须保证链表有序否则去重不完全 3、两个有序链表合并之后仍然保存有序 最后虽然 list 提供了这些具有特殊功能的接口它们也确实有一定的作用但是实际上这些特殊接口使用频率非常低包括 sort 接口 (链表排序的效率太低)。 3、list 排序的性能分析 虽然链表排序只能使用 list 提供的 sort 接口而不能使用 algorithm 提供的 sort 接口但是其使用频率仍然非常低这是由于链表排序的效率太低了我们可以通过对比两组测试数据来直观的感受链表排序的效率。 测试一vector 排序与 list 排序性能对比 //vector sort 和 list sort 性能对比 – release 版本下 void test_op1() {srand((size_t)time(0));const int N 1000000; //100万个数据vectorint v;v.reserve(N);listint lt;for (int i 0; i N; i){auto e rand();v.push_back(e);lt.push_back(e);}//vector sortint begin1 clock();sort(v.begin(), v.end());int end1 clock();//list sortint begin2 clock();lt.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2); }测试二list 直接进行排序与将数据拷贝到 vector 中使用 vector 排序后再将数据拷回 list 中性能对比 //list sort 与 将数据转移到 vector 中进行排序后拷贝回来性能对比 – release 版本下 void test_op2() {srand(time(0));const int N 1000000; //100万个数据listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt1.push_back(e);lt2.push_back(e);}//list sort – lt1int begin1 clock();lt1.sort();int end1 clock();// 将数据拷贝到vector中排序排完以后再拷贝回来 – lt2int begin2 clock();vectorint v;v.reserve(N);for (auto e : lt2) //拷贝{v.push_back(e);}sort(v.begin(), v.end()); //排序lt2.assign(v.begin(), v.end()); //拷贝int end2 clock();printf(list1 sort:%d\n, end1 - begin1);printf(list2 sort:%d\n, end2 - begin2); }可以看到list sort 的效率远低于 vector sort甚至于说直接使用 list sort 的效率都不如先将数据拷贝到 vector 中然后使用 vector sort排序之后再将数据拷贝回 list 中快至此我们也能明白为什么 list sort 接口使用的非常少了。 注在工程中在 release 版本下测试软件或算法性能得到的结果要比在 debug 版本下得到的结果具有参考意义。 二、list 迭代器的实现 1、迭代器的分类 按照迭代器的功能迭代器一共可以分为以下三类 单向迭代器 – 迭代器仅仅支持 和解引用操作单链表的迭代器是典型的单向迭代器双向迭代器 – 迭代器支持 、– 和解引用操作但不支持 、- 操作list (双向带头循环链表) 是典型的双向迭代器随机迭代器 – 迭代器不仅支持 、– 和解引用操作还支持 、- 操作即迭代器能够随机访问我们前面学习的 string 和 vector 的迭代器是典型的随机迭代器。 2、list 迭代器失效问题 和 vector 不同list 进行 insert 操作后并不会产生迭代器失效问题因为 list 插入的新节点是动态开辟的同时由于 list 每个节点的物理地址是不相关的所以插入的新节点并不会影响原来其他节点的地址 但是 list erase 之后会发生迭代器失效因为 list 删除节点会直接将该节点释放掉此时我们再访问该节点就会造成越界访问。 3、list 迭代器源码分析 我们知道迭代器是类似于指针一样的东西即迭代器要能够实现指针相关的全部或部分操作 – 、–、、、-对我们之前 string 和 vector 的迭代器来说迭代器就是原生指针所以它天然的就支持上述操作 但是对于 list 来说list 的节点是一个结构体同时 list 每个节点的物理地址是不连续的如果此时我们还简单将节点的指针 typedef 为迭代器的话那么显然它是不能够实现解引用、 等操作的所以我们需要用结构体/类来对迭代器进行封装再配合运算符重载等操作让迭代器能够实现解引用、、– 等操作。 SGI 版本 C 源码中对 list 迭代器实现框架如下 //节点定义 template class T struct __list_node {typedef void void_pointer;void_pointer next;void_pointer prev;T data; };//迭代器定义 typedef __list_iteratorT, T, T* iterator; typedef __list_iteratorT, const T, const T* const_iterator;//迭代器类 templateclass T, class Ref, class Ptr struct __list_iterator {typedef __list_iteratorT, Ref, Ptr self;typedef list_nodeT* link_type; //节点的指针link_type node; //类成员变量list_iterator(link_type x) : node(x) {} //将节点指针构造为类对象//… 使用运算符重载支持迭代器的各种行为self operator() {…}self operator–() {…}Ref operator() const {…} };如上我们为迭代器专门设计了一个 __list_iterator 类然后在类内配合运算符重载、模板等操作使得迭代器支持指针的各种行为 (至于这里为什么 __list_iterator 会有三个模板参数我们会在下面模拟实现中具体解释当前我们只需要理解其第一个模板参数 T 即可)。 4、list 迭代器模拟实现 4.1 普通迭代器 list 普通迭代器的实现比较简单只需要一个模板参数 T 来代表数据类型然后通过运算符重载来实现迭代器的各种操作即可 //typedef __list_iteratorT iterator – 迭代器templateclass T struct __list_iterator {typedef list_nodeT node; //将list节点重命名为nodenode _pnode; //节点指针作为类的唯一成员变量list_iterator(node* p) //默认构造:_pnode(p){}T operator*() //解引用{return _pnode-_data;}list_iteratorT operator() //前置{_pnode _pnode-_next;return *this;}list_iteratorT operator(int) //后置{list_iteratorT it(*this);_pnode _pnode-_next;return it;}list_iteratorT operator–() //前置–{_pnode _pnode-_prev;return *this;}list_iteratorT operator–(int) //后置–{__list_iteratorT it(this);_pnode _pnode-_prev;return it;}bool operator!(const __list_iteratorT it) //!{return _pnode ! it._pnode;} };4.2 const 迭代器 我们上面的迭代器是普通迭代器那么如何实现 const 迭代器呢const 迭代器与普通迭代器的区别在于 – const 迭代器不能修改节点中的数据即 operator() 函数的返回值应该是 const T 那么部分同学可能会这样来实现 const 迭代器即在 __list_iterator 类中重载一个返回值为 const T 的 operator() 函数如下 //typedef __list_iteratorT iterator – 迭代器 //typedef const __list_iteratorT const_iterator – const 迭代器 templateclass T struct __list_iterator {T operator() //解引用{return _pnode-_data;}const T operator() const{return _pnode-_data;} };但是这样显然是不行的因为 const __list_iteratorT const_iterator 中 const 修饰的是 const_iterator 本身即限制 const_iterator 不能改变这样会导致 const_iterator 不能进行 等操作而并不会限制迭代器解引用后对节点数据的改变。 所以我们应该为 const 迭代器设计一个单独的类 __list_const_iterator //typedef __list_iteratorT iterator – 迭代器 templateclass T struct __list_iterator {typedef list_nodeT node; //将list节点重命名为nodenode _pnode; //节点指针作为类的唯一成员变量list_iterator(node* p) //默认构造:_pnode(p){}T operator*() //解引用{return _pnode-_data;}list_iteratorT operator() //前置{_pnode _pnode-_next;return *this;}list_iteratorT operator(int) //后置{list_iteratorT it(*this);_pnode _pnode-_next;return it;}list_iteratorT operator–() //前置–{_pnode _pnode-_prev;return *this;}list_iteratorT operator–(int) //后置–{__list_iteratorT it(this);_pnode _pnode-_prev;return it;}bool operator!(const __list_iteratorT it) //!{return _pnode ! it._pnode;} };//typedef __list_const_iteratorT const_iterator – 迭代器 templateclass T struct __list_const_iterator {typedef list_nodeT node; //将list节点重命名为nodenode _pnode; //节点指针作为类的唯一成员变量list_const_iterator(node* p) //默认构造:_pnode(p){}const T operator*() //解引用{return _pnode-_data;}list_const_iteratorT operator() //前置{_pnode _pnode-_next;return *this;}list_const_iteratorT operator(int) //后置{list_iteratorT it(*this);_pnode _pnode-_next;return it;}list_const_iteratorT operator–() //前置–{_pnode _pnode-_prev;return *this;}list_const_iteratorT operator–(int) //后置–{__list_const_iteratorT it(this);_pnode _pnode-_prev;return it;}bool operator!(const list_const_iteratorT it) //!{return _pnode ! it._pnode;} };可以看到list_iterator 类和 __list_const_iterator 类除了类名和 operator() 函数的返回值不同以外其他地方完全相同这就会造成严重的代码冗余。 大佬显然是不会运行这种冗余存在的所以想到了另一种办法来解决 const 迭代器的问题那就是向 __list_iterator 中增加一个模板参数如下 //const 迭代器 – 增加模板参数解决 operator()返回值问题 //typedef __list_iteratorT, T iterator; //typedef __list_iteratorT, const T const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题 templateclass T, class Ref
struct __list_iterator //迭代器类 {typedef list_nodeT node; //重命名list节点typedef __list_iteratorT, Ref Self; //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node _pnode; //节点指针作为类的唯一成员变量__list_iterator(node* p):_pnode(p){}Ref operator*() //const迭代器看这个{return _pnode-_data;}Self operator() //前置{_pnode _pnode-_next;return *this;}Self operator–() //前置{_pnode _pnode-_prev;return this;}bool operator!(const Self it){return _pnode ! it._pnode;} };注意事项对于普通类来说类名 类型对于模板类来说类名 ! 类型类型 类名 模板参数 。(注意在类内不管是否存在模板类名都等于类型不过为了混淆我们不建议这样使用) 所以我们可以通过传递不同的模板参数来让编译器实例化出两个不同的类对于上面的类来说表现如下 //库使用者 listint, T::iterator it; //普通迭代器 listint, const T::iterator cit; //const 迭代器//templateclass T, class Ref //通过编译器实例化出的两个不同的 __list_iterator 类 //类1、T:int Ref:T struct __list_iterato {T operator() { return _pnode-_data } };//类2、T:int Ref:const T struct list_iterato {const T operator() { return _pnode-_data } };总结 const 迭代器实现的两种方法 为 const 迭代器单独写一个类此类与原来的类只有类名和 operator() 函数返回值不同造成代码冗余给迭代器类增加一个模板参数 Ref让编译器根据传入的 Ref 的不同来自动示例化出 const 迭代器类。 4.3 完整版迭代器 从最初的迭代器源码中我们可以看到源码中迭代器类有三个模板参数下面我们来引出这第三个参数。 假设 list 第一个模板参数 T 是一个自定义类型的类 Pos其类的定义如下 struct Pos {int _row;int _col;Pos(int row 0, int col 0) //构造:_row(row),_col(col){} };那么我们可以通过 list 迭代器以这样的方式来访问 Pos 中的成员变量 listPos lt(1,2); listPos::iterator it lt.begin(); while(it ! lt.end()) {cout (*it)._row:(*it)._colendl;it; }可以看到我们需要先解引用得到 list 的节点但由于此节点 Pos 是结构体类型所以我们还需要通过 . 的方式来获取结构体成员但是这样用非常别扭因为迭代器是模拟指针的行为而结构体指针访问数据的方式是 类名-变量名那么我们能否像下面这样用呢 cout it-_row:it-_colendl;显然这样是不行的因为 it 是一个自定义类型的对象 (list_iterator 类的对象)而只有结构体指针才能像上面那样访问成员所以我们需要利用运算符重载让 it 支持 - 操作如下 templateclass T, class Ref struct __list_iterator {T* operator-() { return _pnode-_data; }
};cout it-_row:it-_colendl;相信绝大部分同学看到 _pnode-_data 和 it-_row 的组合是懵逼的这其实是因为 C 为了代码的可读性省略了一个 -而原本的调用方式应该是这样的 cout it–_row:it–_colendl;
//编译器编译时转化为cout it.operator-()-_row:it.operator-()-_colendl;如上由于 __list_iterator 对 - 运算符进行了重载所以编译器会将 it- 转化为 it.operator-()它得到的是节点数据的地址也就是 Pos所以实际上 Pos 还需要通过 - 操作符来得到 _row 和 _col但是 it–_row 可读性太差所以 C 省略了一个 -而让编译器对其进行处理 – it.operator-()-_row。 但是此时这里又会和前面一样的问题const 迭代器需要 operator-() 的返回值为 const T所以这里我们采取和前面一样的做法 – 再增加一个模板参数把第三个模板参数作为 operator-() 函数的返回值使得编译器可以根据传入的参数的不同实例化出不同的 __list_iterator 类。 //库使用者 listint, T, T::iterator it; //普通迭代器 listint, const T, const T::iterator cit; //const 迭代器//templateclass T, class Ref, class Ptr //通过编译器实例化出的两个不同的 __list_iterator 类 //类1、T:int Ref:T Ptr struct __list_iterato {T operator-() { return _pnode-_data } };//类2、T:int Ref:const T Ptr:const T* struct __list_iterato {const T* operator-() { return _pnode-_data } };至此完整的迭代器模拟实现如下 //const 迭代器 – 增加模板参数解决 operator() 返回值与 operator-() 返回值问题 //typedef __list_iteratorT, T, T iterator; //typedef __list_iteratorT, const T, const T* const_iterator; //STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题 templateclass T, class Ref, class Ptr
struct __list_iterator //迭代器类 {typedef list_nodeT node; //重命名list节点typedef list_iteratorT, Ref, Ptr Self; //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node* _pnode; //节点指针作为类的唯一成员变量list_iterator(node* p) //构造:_pnode(p){}Ref operator*() //解引用{return _pnode-_data;}Ptr operator-() //-{return _pnode-_data;}Self operator() //前置{_pnode _pnode-_next;return *this;}Self operator(int) //后置{Self it(*this);_pnode _pnode-_next;return it;}Self operator–() //前置–{_pnode _pnode-_prev;return *this;}Self operator–(int) //后置–{Self it(this);_pnode _pnode-_prev;return it;}bool operator!(const Self it) const //!{return _pnode ! it._pnode;}bool operator(const Self it) const //{return _pnode it._pnode;} };三、list 的模拟实现 list 模拟实现的最大难点在于 list 迭代器类的模拟实现至于其他的一些成员函数比如构造、赋值重载、析构等都比较简单这里我就直接给出最终代码了大家可以对照着自己模拟实现的代码看一看。 list.h #pragma once#include iostream #include assert.h #include algorithmnamespace thj {templateclass Tstruct list_node //list 节点结构定义{list_nodeT _next;//不加T也没错但是写上好一些list_nodeT* _prev;T _data;list_node(const T x)//构造:_next(nullptr), _prev(nullptr), _data(x){}};//迭代器最终版//const 迭代器 – 增加模板参数解决 operator() 返回值与 operator-() 返回值问题//typedef __list_iteratorT, T, T iterator;//typedef __list_iteratorT, const T, const T* const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题templateclass T, class Ref, class Ptrstruct __list_iterator //迭代器类{typedef list_nodeT node; //重命名list节点typedef list_iteratorT, Ref, Ptr Self; //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node* _pnode; //节点指针作为类的唯一成员变量list_iterator(node* p):_pnode(p){}Ref operator*() //解引用{return _pnode-_data;}Ptr operator-() //-{return _pnode-_data;}Self operator() //前置{_pnode _pnode-_next;return *this;}Self operator(int) //后置{Self it(*this);_pnode _pnode-_next;return it;}Self operator–() //前置–{_pnode _pnode-_prev;return *this;}Self operator–(int) //后置–{Self it(this);_pnode _pnode-_prev;return it;}bool operator!(const Self it) const //!{return _pnode ! it._pnode;}bool operator(const Self it) const //{return _pnode it._pnode;}};//list 类templateclass Tclass list{typedef list_nodeT node; //list 的节点public:typedef __list_iteratorT, T, T iterator; //迭代器typedef __list_iteratorT, const T, const T* const_iterator; //const 迭代器//迭代器iterator begin() {return iterator(_head-_next);}iterator end() {//iterator it(_head);//return it;//直接利用匿名对象更为便捷return iterator(_head);}const_iterator begin() const {return const_iterator(_head-_next);}const_iterator end() const {return const_iterator(_head);}void empty_initialize() { //初始化 – 哨兵位头结点_head new node(T());_head-_next _head;_head-_prev _head;_size 0; //空间换时间用于标记节点个数}list() { //构造不是listT的原因构造函数函数名和类名相同而listT是类型empty_initialize();}//迭代器区间构造template class InputIteratorlist(InputIterator first, InputIterator last) {empty_initialize();while (first ! last){push_back(*first);first;//first;}}//拷贝构造传统写法//list(const listT lt) {// empty_initialize();// for (const auto e : lt)// {// push_back(e);// }//}// 拷贝构造的现代写法//list(const list lt) 官方库是这样写的这是由于在类内类名等价于类型但不建议自己这样写list(const listT lt) {empty_initialize(); //初始化头结点防止交换后tmp野指针不能正常的调用析构listT tmp(lt.begin(), lt.end());swap(tmp);}//赋值重载传统写法//listT operator(const listT lt) {// if (this ! lt)// {// clear();// for (const auto e : lt)// {// push_back(e);// }// }// return *this;//}//赋值重载现代写法//list operator(list lt)listT operator(listT lt) { //不能加引用lt是调用拷贝构造生成的swap(lt);return this;}~list() { //析构clear();delete _head;_head nullptr;}void swap(listT lt) { //交换两个链表本质上是交换两个链表的头结点std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size() const { //增加一个计数的成员以空间换时间return _size;}bool empty() { //判空return _size 0;}void clear() {iterator it begin();while (it ! end()) {it erase(it);}_size 0;}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;insert(end(), x); //复用}void push_front(const T x) {insert(begin(), x); //复用}void pop_front() {erase(begin());}void pop_back() {erase(–end());}iterator insert(iterator pos, const T x) {node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;cur-_prev newnode;newnode-_next cur;_size;return iterator(pos);}iterator erase(iterator pos) {assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;–_size;return iterator(next);}private:node* _head;size_t _size;}; }test.cpp #include list.husing namespace thj; using std::cout; using std::endl;void test_list1() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(lt.begin(), 10);//iterator 1、内嵌类型 2、像指针一样listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl; }void test_list2() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);lt.push_front(30);lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout e ;}cout endl; }void test_list3() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;listint lt1(lt);//默认是浅拷贝,指向同一块lt.pop_back();lt.pop_back();for (auto e : lt1){cout e ;}cout endl;listint lt3 lt1;for (auto e : lt3){cout e ;} }void test_list4() {listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){(*it) 2;cout *it ;it;//it;}cout endl;//print_list(lt);listint lt1(lt);for (auto e : lt1){cout e ;}cout endl;listint lt2 lt;for (auto e : lt2){cout e ;}cout endl;cout lt.size() endl; }struct Pos {int _row;int _col;Pos(int row 0, int col 0):_row(row), _col(col){} };void print_list(const listPos lt) {listPos::const_iterator it lt.begin(); //重载了找的另一个类的迭代器while (it ! lt.end()) {//it-_row; 增加第三个模板参数cout it-_row : it-_col endl;it;}cout endl; }void test_list5() {listPos lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 3));lt.push_back(Pos(2, 3));listPos::iterator it lt.begin();while (it ! lt.end()) {//cout (*it)._row : (*it)._col endl;cout it-_row : it-_col endl; //编译器为了可读性做了特殊处理省略了一个-,//那么省略之前应该是it–_row//cout it.operator-()-_col : it.operator-()-_row endl;it;}cout endl;print_list(lt); }int main() {//test_list1();//test_list2();//test_list3();//test_list4();test_list5();return 0; }四、vector 和 list 的区别 vector 和 list 的区别其实就是顺序表和链表的区别但是由于相较于数据结构初阶我们又增添了 C 的相关知识所以这里我还是重新列举一下二者的异同与优缺 –vector-list底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率 O(1)不支持随机访问访问某个元素效率 O(N)插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为 O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为 O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针 (节点指针) 进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问