网站 404 错误页面是否自动跳转,网站提高收录和访问量,天津做网站找哪家公司,北京手机网站设计费用相较于vector的连续性空间#xff0c;list相对比较复杂#xff1b;list内部使用了双向环形链表的方式对数据进行存储#xff1b;list在增加元素时#xff0c;采用了精准的方式分配一片空间对数据及附加指针等信息进行存储#xff1b;
list节点定义如下
templateclas…相较于vector的连续性空间list相对比较复杂list内部使用了双向环形链表的方式对数据进行存储list在增加元素时采用了精准的方式分配一片空间对数据及附加指针等信息进行存储
list节点定义如下
templateclass T
struct __list_node{__list_nodeT* pre; // 此处采用了书中建议的写法与实际定义略有差异__list_nodeT* next;T data;
};
因为list存储节点不是T所以其迭代器不能使用T*所以定义了其迭代器
templateclass T, class Ref, class Ptr
struct __list_iterator {// ...typedef __list_nodeT * link_type;// ...link_type node;// ...
};
__list_iterator迭代器的操作符*-操作符比较明显为node-data, node-data;
对于操作符和--分别对应于nodenode-next,及nodenode-pre; list采用双向环形链表list成员只包含一个节点node
template class T, class Alloc alloc
class list {protected:typedef __list_nodeT list_node;public :typedef list_node* link_type;protected:link_type node;...
};
因为是环形结构node本身即为list的endnode-next即为list的起始节点
iterator begin() {return node-next;}
iterator end() {return node;}
bool empty() const {return node-next node;}
reference front() {return *begin();}
reference back() {return *(end()--);}
list的insert操作比较简明
iterator insert(iterator position, const Tx) {link_type tmp create_node(x);tmp-next position.node;tmp-pre position.node-pre;position.node-pre-next tmp;position.node-pre tmp;return tmp; }
指针插入前后指向情况如下
此外lsit还提供了splice及merge操作splice用于拼接merge是两个有序list的合并看上去很适合归并排序当中的合并操作 此外在书中提到了sort函数用的快排的代码用到了swap及merge没能理解可能是前面漏掉了部分函数的定义没有理解算法的含义等看到了后再补充这块的学习内容 参考文档《STL源码剖析--侯捷》
