一般接口2、list

是可以在常数范围内在任意位置进行插入和删除的序列式容器其底层是带头双向循环链表list

string、vector

系列容器的接口使用一样这里我就不再详细介绍具体使用细节可以查看

list

函数声明-接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list

position

position位置的元素swap交换两个list中的元素clear清空list中的有效元素

注意事项

中的指定元素unique链表去重merge合并两个链表sort链表排序reverse链表逆置

注意事项

提供了这些具有特殊功能的接口它们也确实有一定的作用但是实际上这些特殊接口使用频率非常低包括

sort

接口但是其使用频率仍然非常低这是由于链表排序的效率太低了我们可以通过对比两组测试数据来直观的感受链表排序的效率。

测试一vector

rand();v.push_back(e);lt.push_back(e);}//vector

sortint

rand();lt1.push_back(e);lt2.push_back(e);}//list

sort

//拷贝{v.push_back(e);}sort(v.begin(),

v.end());

每个节点的物理地址是不相关的所以插入的新节点并不会影响原来其他节点的地址

list

删除节点会直接将该节点释放掉此时我们再访问该节点就会造成越界访问。

3、list

我们知道迭代器是类似于指针一样的东西即迭代器要能够实现指针相关的全部或部分操作

、–、*、、-对我们之前

等操作的所以我们需要用结构体/类来对迭代器进行封装再配合运算符重载等操作让迭代器能够实现解引用、、--

SGI

//类成员变量__list_iterator(link_type

node(x)

类然后在类内配合运算符重载、模板等操作使得迭代器支持指针的各种行为

(至于这里为什么

会有三个模板参数我们会在下面模拟实现中具体解释当前我们只需要理解其第一个模板参数

4、list

//节点指针作为类的唯一成员变量__list_iterator(node*

//默认构造:_pnode(p){}T

//节点指针作为类的唯一成员变量__list_iterator(node*

//默认构造:_pnode(p){}T

//节点指针作为类的唯一成员变量__list_const_iterator(node*

operator*()

_pnode-_data;}__list_const_iteratorT

operator()

函数的返回值不同以外其他地方完全相同这就会造成严重的代码冗余。

const

const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题

templateclass

//这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node*

_pnode;

//节点指针作为类的唯一成员变量__list_iterator(node*

p):_pnode(p){}Ref

。

(注意在类内不管是否存在模板类名都等于类型不过为了混淆我们不建议这样使用)

所以我们可以通过传递不同的模板参数来让编译器实例化出两个不同的类对于上面的类来说表现如下

//库使用者

从最初的迭代器源码中我们可以看到源码中迭代器类有三个模板参数下面我们来引出这第三个参数。

list

的方式来获取结构体成员但是这样用非常别扭因为迭代器是模拟指针的行为而结构体指针访问数据的方式是

类名-变量名那么我们能否像下面这样用呢

类的对象)而只有结构体指针才能像上面那样访问成员所以我们需要利用运算符重载让

操作如下

it.operator-()-_row:it.operator-()-_colendl;如上由于

__list_iterator

//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题

templateclass

//这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node*

_pnode;

//节点指针作为类的唯一成员变量__list_iterator(node*

//构造:_pnode(p){}Ref

迭代器类的模拟实现至于其他的一些成员函数比如构造、赋值重载、析构等都比较简单这里我就直接给出最终代码了大家可以对照着自己模拟实现的代码看一看。

list.h

_next;//不加T也没错但是写上好一些list_nodeT*

_prev;T

const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题templateclass

class

//这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node*

_pnode;

//节点指针作为类的唯一成员变量__list_iterator(node*

p):_pnode(p){}Ref

iterator(_head-_next);}iterator

end()

iterator(_head);}const_iterator

begin()

const_iterator(_head-_next);}const_iterator

end()

//构造不是listT的原因构造函数函数名和类名相同而listT是类型empty_initialize();}//迭代器区间构造template

class

InputIteratorlist(InputIterator

first,

last){push_back(*first);first;//first;}}//拷贝构造传统写法//list(const

listT

官方库是这样写的这是由于在类内类名等价于类型但不建议自己这样写list(const

listT

//初始化头结点防止交换后tmp野指针不能正常的调用析构listT

tmp(lt.begin(),

lt.end());swap(tmp);}//赋值重载传统写法//listT

operator(const

//不能加引用lt是调用拷贝构造生成的swap(lt);return

*this;}~list()

//交换两个链表本质上是交换两个链表的头结点std::swap(_head,

lt._size);}size_t

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(lt.begin(),

10);//iterator

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

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for

(auto

lt1(lt);//默认是浅拷贝,指向同一块lt.pop_back();lt.pop_back();for

(auto

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator

lt.begin();while

1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2,

lt.begin();while

//编译器为了可读性做了特殊处理省略了一个-,//那么省略之前应该是it--_row//cout

it.operator-()-_col

{//test_list1();//test_list2();//test_list3();//test_list4();test_list5();return

}四、vector

的区别其实就是顺序表和链表的区别但是由于相较于数据结构初阶我们又增添了

--vector-list底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率

O(1)不支持随机访问访问某个元素效率

O(N)插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为

O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为

O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针

(节点指针)

进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问