C++ STL专题 list的底层实现

---

目录

1.模拟实现list

2.节点模板讲解

3.迭代器模板讲解

3.1为什么template 有三个类型参数

(1).class T

(2).class ref

(3).class ptr

3.2  *重载

3.3 ->重载

3.4 前置++和++后置的重载

3.5 前置--和--后置的重载

3.6 ==和!=的重载

4. list模板讲解

4.1 begin()函数

4.2 end()函数

4.3 空初始化函数

4.4 深拷贝函数

4.5 交换函数

4.6 赋值运算符operator=的实现

4.7 析构函数和clear()函数

4.8 push_back函数

4.9 插入函数

4.10 push_front函数

4.11 erase函数

4.12 头删和尾删

4.13 size函数

3.14 empty函数

---

1.模拟实现list

分别定义了三个类模板

分别是节点模板，迭代器模板，list模板

template <class T>
class list_node
{
public:T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr){}
};

template <class T, class ref, class ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, ref, ptr> self;Node* _node;
};

template <class T>
class list
{typedef list_node<T> Node;public:private:Node* _head;size_t _size;
};

2.节点模板讲解

源码：
 

template <class T>
class list_node
{
public:T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr){}
};

(1).定义值域_data，用于存放数值，在定义指向下一个节点和上一个节点的指针。

(2).默认构造函数，可用于初始化，赋值等等。

3.迭代器模板讲解

源码：

template <class T, class ref, class ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, ref, ptr> self;Node* _node;list_iterator(Node* node): _node(node){}ref& operator*(){return _node->_data;}ptr* operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;}
};

3.1为什么template <class T, class ref, class ptr>有三个类型参数

(1).class T

T通常用于表示迭代器所指的数据类型。在list中，T是链表节点中存储的数据类型。例如：如果此链表用于存储整数，那么T就是int；如果链表用于存储字符串，则T就是string。

(2).class ref

ref用于定义解引用迭代器时返回的类型，这允许迭代器解引用时的行为。

在这个代码中，ref被用作operator*()的返回类型，他返回_node->_data的一个引用。这意味着ref应该是对T类型的引用类型，通常是T&。

(3).class ptr

ptr用于定义迭代器箭头操作符operator->()的返回类型。他返回_node->_data的地址，这意味着ptr应该是一个指针类型，，通常是T*。

这三个类型参数T，ref，ptr提供了对迭代器行为的精细度控制，使得迭代器模板能够更加灵活和通用地应对不同场景和数据类型。

3.2  *重载

ref& operator*()
{return _node->_data;
}

(1).*为解引用，要获取值，则返回这个值的引用即可。(ref被用作operator*()的返回类型)

3.3 ->重载

ptr* operator->()
{return &_node->_data;
}

(1). ->为获取地址，获取地址，就返回地址即可。(ref被用作operator*()的返回类型)

3.4 前置++和++后置的重载

self& operator++()
{_node = _node->_next;return *this;
}self& operator++(int)
{self tmp(*this);_node = _node->_next;return tmp;
}

(1).前置++中，由于是先自加再赋值，所以直接将_node=_node->_next即可，然后返回*this。

(1).++后置中，由于是先赋值再自加，所以要先把改变之前的值保持在tmp中，再对_node作改变，最后返回的是tmp。

3.5 前置--和--后置的重载

self& operator--()
{_node = _node->_prev;return *this;
}
self& operator--(int)
{self tmp(*this);_node = _node->_prev;return tmp;
}

(1).前置--中，由于是先自减再赋值，所以直接将_node=_node->_prev即可，然后返回*this。

(2).--后置中，由于是先赋值再自减，所以要先把改变之前的值保持在tmp中，再对_node作改变，最后返回的是tmp。

3.6 ==和!=的重载

bool operator!=(const self& s) const
{return _node != s._node;
}
bool operator==(const self& s) const
{return _node == s._node;
}

(1) ==和!=中，直接判断s与_node 是否相等即可。

(2)注意：
        这两个运算符通常应该一起被重载，以保持它们之间的一致性。

        它们被声明为const成员函数，因为它们不修改_node成员。

        

4. list模板讲解

源码：

template <class T>
class list
{typedef list_node<T> Node;public:// typedef list_iterator<T> iterator;// typedef list_const_iterator<T> const_iterator;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){iterator it(_head->_next);return it;}iterator end(){iterator it(_head);return it;}const_iterator begin() const{iterator it(_head->_next);return it;}const_iterator end() const{iterator it(_head);return it;}void empty_init(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(const list<T>& lt) // 深拷贝{empty_init(); // 初始化for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it); // 返回下一个的迭代器}}void swap(list<int>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}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;_size++;// insert(end(),x);}void push_front(const T& x){insert(begin(), x);}// 在pos之前插入void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;_size++;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;_size--;return next;}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;
};

重命名：

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

4.1 begin()函数

iterator begin()
{iterator it(_head->_next);return it;
}

(1).begin()是一个迭代器，其作用是返回第一个有效数值的地址。

(2)._head是一个指向链表头节点的指针，这里的头节点并不存储有效数据，而是作为一个哨兵节点的存在。

(3)._head=_next是头节点的下一个节点，即链表中第一个存储有效数据的节点。

(4).iterator it(_head=_next) 创建了一个迭代器it，他初始化为指向链表的第一个有效元素。

4.2 end()函数

iterator end()
{iterator it(_head);return it;
}

(1).end()是一个迭代器，其作用是返回最后一个有效节点的下一个位置，也就是哨兵节点。

4.3 空初始化函数

void empty_init()
{_head = new Node(T());_head->_next = _head;_head->_prev = _head;_size = 0;
}

void empty_init()函数在list类中有着重要作用，其作用为初始化链表为空状态的作用，这个函数的主要目的是创建一个哑节点(哨兵节点)，并设置链表的初始状态，使链表在逻辑上是空的。

4.4 深拷贝函数

list(const list<T>& lt) // 深拷贝
{empty_init(); // 初始化for (auto& e : lt){push_back(e);}
}

list(const list<T>& lt)是一个拷贝构造函数，它用于创建一个新的list对象，该对象是另一个已存在list对象的深拷贝。这个拷贝构造函数通过遍历it并使用其元素来填充新创建的list，从而实现了深拷贝。

4.5 交换函数

void swap(list<int>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}

实现了交换两个list的功能

4.6 赋值运算符operator=的实现

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

注意是传值传参，只是一个拷贝，在调用operator=时会创建一个list<T>的副本，这个副本是通过调用list的拷贝构造函数实现的。

在swap调用后，*this获得了it的原始资源，而it获得了*this的原始资源。

4.7 析构函数和clear()函数

void clear()
{auto it = begin();while (it != end()){it = erase(it); // 返回下一个的迭代器}
}~list()
{clear();delete _head;_head = nullptr;
}

void clear()函数中,通过遍历整个list，再通过erase来销毁list。

析构函数中，直接调用了clear()函数。

4.8 push_back函数

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;//尾节点tail->_next = newnode;//更新尾节点的_next指针newnode->_prev = tail;//更新新节点的_prev指针newnode->_next = _head;//新节点的_next指向哨兵节点_head->_prev = newnode;//哨兵节点的_prev指向新节点_size++;//更新链表大小// insert(end(),x);
}

这个函数接受一个类型为constT&的参数x，即要插入的新元素的一个常量引用。使用常量引用是为了避免不必要的元素复制，同时保证传递给函数的对象不会被修改。

4.9 插入函数

void insert(iterator pos, const T& x)
{Node* cur = pos._node;//cur指向迭代器pos当前指向的节点Node* prev = cur->_prev;//prev指向cur的前一个节点Node* newnode = new Node(x);//创建一个新的节点newnode，并初始化为xnewnode->_next = cur;//将新结点的_next指针指向cur。cur->_prev = newnode;//将当前位置的_prev指针更新为指向新节点，以保持双向链接newnode->_prev = prev;//将新节点_prev指针指向prev，即前一个节点prev->_next = newnode;//将前一个结点的_next指针更新为新结点，完成插入。_size++;//链表大小加一，因为插入了新数据
}

用于在链表的指定位置pos之前插入一个新的元素x。这个函数展示了如何在双向链表中高效的插入元素。

4.10 push_front函数

void push_front(const T& x)
{insert(begin(), x);
}

直接利用insert函数即可，将插入位置定为begin()。

4.11 erase函数

iterator erase(iterator pos)
{assert(pos != end());Node* prev = pos._node->_prev;//获得删除结点的前驱Node* next = pos._node->_next;//获得删除结点的后继prev->_next = next;//将前驱结点的_next指针指向后继结点next->_prev = prev;//将后继节点的_prev指针指向前驱结点delete pos._node;//删除pos位置的节点的内存_size--;//将链表大小减一return next;//返回被删除元素之后元素的迭代器
}

用于从双向链表中删除指定位置的元素，并返回指向被删除元素之后元素的迭代器。

4.12 头删和尾删

void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}

直接调用erase即可

4.13 size函数

size_t size() const
{return _size;
}

直接返回_size的大小即可

3.14 empty函数

 bool empty(){return _size == 0;}

直接返回_size是否等于0即可。

---

本篇完