目录
一、List框架搭建
1. List简介
- list是可以在
常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 - list的底层是带头双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。而forward_list是单链表，只能朝前迭代
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率高。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，如访问中间的某个元素需要从头部或者未卜迭代到该位置，时间复杂度是O(N)，list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
2. List的使用
3. List构造
3.1 构造一个空的list
list(){
//带头双向循环
_head = new Node(T()); //这里的构造不能传0，因此这里不一定是int类型的,这里T可能是vector，也可能是string对象
_head->_next = _head;
_head->_prev = _head;
}
3.2 拷贝构造
list(const list<T>& lt){
//深拷贝
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for(const auto& e : lt){
push_back(e);
}
}
3.3 用区间元素构造list
template<class InputIterator>
list(InputIterator first,InputIterator last){ //这里不仅仅支持链表的初始化，而且还支持string或者vector的迭代器
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
while(first != last){
push_back(*first);
++first;
}
}
4. List节点
template<class T>
struct __list_node{
__list_node<T>* _next;
__list_node<T>* _prev;
T _data;
__list_node(const T& x = T()) //给个匿名对象去初始化
:_next(nullptr)
, _prev(nullptr)
,_data(x)
{}
};
5. 迭代器框架实现
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
- 原生态指针，比如：vector
- 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下
方法：
- 指针可以解引用，迭代器的类中必须重载operator*()
- 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
- 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前 移动，所以需要重载，如果是forward_list就不需要重载– - 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
这里typdef的__list_iterator里带了三个参，其中第二和第三个类模版分别用于决定operator*()返回什么样类型的的对象 和 用于operator->()返回当前节点的数据
template<class T>
class list
{
typedef __list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator begin(){
return iterator(_head->_next);
}
iterator end(){
return iterator(_head);
}
const_iterator begin() const{
return const_iterator(_head->_next);
}
const_iterator end() const {
return const_iterator(_head);
}
private:
Node* _head;
};
6. 赋值重载
//解引用
Ref operator*(){
return _node->_data;
}
Ptr operator->(){
return &_node->_data;
}
// ++it
self& operator++(){
_node = _node->_next;
return *this;
}
// it++
self operator++(int){ //后置++
self tmp(*this);
_node = _node->_next;
return tmp;
}
// --it
self& operator--(){
_node = _node->_prev;
return *this;
}
// it--
self operator--(int){ //后置--
self tmp(*this);
_node = _node->_prev;
return tmp;
}
//比较是否相等
bool operator!=(const self& it){
return _node != it._node;
}
bool operator==(const self& it){
return _node == it._node;
}
7. 关于List的容量
遍历一遍，直到遇到带头后结束
size_t size(){
size_t n = 0;
iterator it = begin();
while(it != end()){
++it;
++n;
}
return n;
}
bool empty(){
return begin() == end();
}
8. List添加新节点
iterator insert(iterator pos, const T& x){
Node* cur = pos._node; //当前节点
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode); //反回新插入节点
}
void push_back(const T& x){
insert(end(), x)
}
void push_front(const T& x){
insert(begin(), x);
}
9. 删除一个节点
由于list数据结构的特点决定了不能像数组一样实现O(1)访问任意节点，所以标准库里只提供了头删和尾删
iterator erase(iterator pos){
assert(pos != end());
Node* cur = pos._node;
Node* pre = cur->_prev;
Node* next = cur->_next;
delete cur;
pre->_next = next;
next->_prev = prev;
return iterator(next);
}
void pop_back(){
erase(--end());
}
void pop_front(){
erase(begin());
}
10. 清空链表和析构
这里需要注意的是只有当实例化对象开辟了空间后才析构，否则进入clear函数后会报错
void clear(){
iterator it = begin();
while(it != end()){
it = erase(it);
}
~list(){
clear();
delete _head;
_head = nullptr;
}
二、完整代码
Gitee链接