C++ ——STL容器【list】模拟实现

代码仓库：

list模拟实现

list源码

数据结构——双向链表

🍇1. 节点结构体

源码的list是双向带头循环链表，所以我们定义两个节点，一个指向下一个，一个指向前一个

template<class T>
struct list_node
{list_node<T>* _next;	//指向下一个节点list_node<T>* _prev;	//指向前一个T _val;	//数据list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}
};

🍈2. list成员

list类包含一个_head头节点，然后为了方便查出当前有多少个节点，还能多定义一个_size

template<class T>
class list
{typedef list_node<T> Node;
public:// 各类操作方法//...
private:Node* _head;size_t _size;
}

🍉3. 迭代器模板

源码的迭代器设置了三个模板参数：

• T：表示指向list节点的数据类型
• Ref：迭代器的引用类型，通常情况为T&，但也可表示const
• Ptr：表示指向节点的指针类型，通常情况下为T*，但也可表示const迭代器，避免代码的冗余

对于string或者是vector的迭代器，对其解引用就可以表示当前的数据；而list是链表，解引用之后表示的一个节点，所以相对会麻烦一点

//Ref T& / const T&
//Ptr T* / const T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}//前置++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& lt){return _node != lt._node;}bool operator==(const self& lt){return _node == lt._node;}};

Tips:

迭代器并没有写拷贝构造，那么就是默认浅拷贝。这无关影响，因为我们就是希望通过这个迭代器找到这个节点

void test1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);//浅拷贝list<int>::iterator it = lt.begin();while(it!=lt.end()){cout<< *it << " ";++it;}cout<<endl;
}

这里没有奔溃也是因为迭代器没有写析构函数，迭代器只是负责访问，并不负责管理

🍊4. 迭代器

const const_iterator begin() const
{//单参数构造函数 隐式类型转换return _head->_next;
}
const const_iterator end() const
{return _head;
}iterator begin()
{//单参数构造函数 隐式类型转换return _head->_next;
}
iterator end()
{return _head;
}

🍋5. 插入删除操作

🍌5.1 insert & erase

这里插入删除操作之后，也会存在当前迭代器失效，所以传修改完毕之后的迭代器位置

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* tmp = new Node(x);Node* prev = cur->_prev;prev->_next = tmp;tmp->_next = cur;cur->_prev = tmp;tmp->_prev = prev;++_size;return tmp;
}
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}

🍌5.2 push_back & push_front & pop_back & pop_front

写了指定位置插入删除之后，直接复用即可

void push_back(const T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}void pop_back()
{Node* tail = _head->_prev;erase(tail);
}
void pop_front()
{erase(begin());
}

🍍6. 构造 & 析构 & 拷贝构造

查看源码发现list的构造和析构都采用了复用

清空链表

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}//_size = 0;
}

复用

void empty_init()
{_head = new Node;_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()
{clear();delete _head;_head = nullptr;
}

🥭7. 赋值重载

这里还是采用现代的写法，交换完毕之后，自动调用析构函数

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

🍓8. 获取元素个数

size_t size()
{return _size;
}

---

以上就是list的基本功能实现，实质上就是双向带头循环链表，迭代器这块有点复杂。

那本期分享就到这里咯，我们下期再见，如果还有下期的话。