目录
list先容
list模拟实现
list 节点类
list 的迭代器
定义
构造函数
解引用
operator前置++和--与后置++和--
operator==与operator!=
list 类
构造函数
begin()和end()
拷贝构造
erase()
clear()
析构函数
insert
push_back 和 push_front
pop_back 和 pop_front
完备代码
⭐list先容
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，而且该容器可以前后双向迭代。
- list的底层是双向链表布局，双向链表中每个元素存储在互不相干的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部大概尾部)迭代到该位置，在这段位置上迭代须要线性的时间开销；list还须要一些额外的空间，以保存每个节点的相干联信息(对于存储范例较小元素的大list来说这大概是一个告急的因素)。
⭐list模拟实现
- list的底层是双向链表布局，包含有一个哨兵节点。
- 模拟实现list，要实现下列三个类：
- ①list节点类
- ②迭代器的类
- ③list主要功能的类(size()，empty()...)
模拟实现list的类的基本功能（增删等操作）要创建在迭代器类和节点类均已实现好的情况下才得以完成。
✨list 节点类
- 定义list中的节点ListNode，包含前驱指针，后驱指针和数据变量；
- 使用struct而不使用class定义类，是为了方便访问每个一个节点 ，struct默认是pbulic，而class中成员变量要定义为private，不方便访问。
- template<class T>
- struct ListNode
- {
- ListNode<T>* _next;
- ListNode<T>* _prev;
- T _data;
- ListNode(const T& x = T())
- :_next(nullptr)
- ,_prev(nullptr)
- ,_data(x)
- {}
- };
迭代器有两种实现方式，具体应根据容器底层数据布局实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全雷同，因此在自定义的类中必须实现以下方法：
- 指针可以解引用，迭代器的类中必须重载operator*()
- 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
- 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
- 至于operator--()/operator--(int)释放须要重载，根据具体的布局来决议，双向链表可以向前移动，以是须要重载，如果是forward_list就不须要重载--
- 迭代器须要进行是否相等的比力，因此还须要重载operator==()与operator!=()
|
