【C++】list容器功能模拟实现

介绍

        上一次介绍了list队容器的迭代器模拟，这次模拟实现list的简单功能，尤其要注意构造函数、析构函数、以及赋值运算符重载的实现。

        list容器需要接纳所有类型的数据，因此，结构设置与迭代器设置同理，需要引入结点，数据。

    //结点结构

    template<class T>     struct ListNode     {         ListNode<T>* _next;         ListNode<T>* _last;         T _data;         ListNode(const T& x = T())             :_next(nullptr)             , _last(nullptr)             , _data(x)         { }     };

    //list容器基本元素

    template<class T>     class list     {     public:         typedef ListNode<T> Node;           typedef _list_iterator<T> iterator;

    private:         Node* _node;  //此结点为哨兵结点，前指头结点，后指尾结点，里面没有数据     };

---

一，构造函数

        构造函数只需构造“ 哨兵结点 ”即可，因为这里使用链式结构存储，因此构造函数没有顺序结构那样的逻辑。代码如下：

list() {     _node = new Node;     _node->_last = _node;     _node->_next = _node; }

        拷贝构造的实现可直接运用赋值运算符，这里要注意，由于这里的设计设计到动态空间的申请，所以实现时需进行深拷贝。

        这里，我们先实现push_back尾插功能，代码如下：

//尾插功能

void push_back(const T& x = T())  {     Node* node = new Node;     node->_data = x;     node->_next = _node;     node->_last = _node->_last;     _node->_last->_next = node;     _node->_last = node; }

        下面是赋值运算符和拷贝构造的实现，唯一要注意的是在使用赋值运算符前，要先确定“ 哨兵结点 ”，即普通的构造函数。

//赋值运算符重载 list<T>& operator=(list<T>& L) {     Node* node = (L._node)->_next;     while (node != L._node)     {         push_back(node->_data);         node = node->_next;     }     return *this; }

//拷贝构造函数

list(list<T>& L) {

    //哨兵结点的构造     _node = new Node;     _node->_last = _node;     _node->_next = _node;

    //赋值运算符的使用     *this = L; }

        下面进行样例代码测试：

void test1() {     list<int> v1;     v1.push_back(1);     v1.push_back(2);     v1.push_back(3);     v1.push_back(4);     list<int> v2;     v2 = v1;     list<int> v3(v1);     std::cout << "List v2: ";     for (auto e : v2)     {         std::cout << e << "  ";     }     std::cout << std::endl;     std::cout << "List v3: ";     for (auto e : v3)     {         std::cout << e << "  ";     }     std::cout << std::endl; }

 测试数据结果：

---

二，析构函数

        析构函数的设计只需诼渐释放所有结点即可，包括“ 哨兵结点 ”。代码如下：

~list() {     Node* t = _node->_next;     while (t != _node)     {         Node* next = t->_next;         delete t;         t = next;     }     delete t;    //最后释放哨兵结点     t = nullptr; }

---

三，list容器接口

        这里实现begin()、end()、push_back(这个接口上面已实现，这里不做演示)、pop_back、push_front、pop_front。代码如下：

iterator begin()  //获取头结点 {     return _node->_next; } iterator end()  //获取尾结点 {     return _node; } void pop_back()  //尾删 {     assert(_node->_next != _node);     Node* node = _node->_last->_last;     delete _node->_last;     _node->_last = node;     node->_next = _node; } void push_front(const T& x = T())  //头插 {     Node* node = new Node;     node->_data = x;     node->_next = _node->_next;     node->_last = _node;     _node->_next->_last = node;     _node->_next = node; } void pop_front()  //头删 {     assert(_node->_next != _node);     Node* node = _node->_next->_next;     delete _node->_next;     _node->_next = node;     node->_last = _node; }

        list容器常用功能有clear()、swap()、erase、insert。接口参数与实现如下：

void clear() {     Node* t = _node->_next;     while (t != _node)     {         Node* next = t->_next;         delete t;         t = next;     }     t = nullptr; } void swap(list<T>& L) {     std::swap(_node, L._node); } iterator insert(iterator pos, const T& x = T()) {     Node* node = new Node;     node->_data = x;     node->_next = pos.node;     node->_last = (pos.node)->_last;     node->_next->_last = node;     node->_last->_next = node;     return node; } iterator erase(iterator pos) {     assert(pos.node != _node);     Node* next = (pos.node)->_next;     Node* last = (pos.node)->_last;     delete pos.node;     next->_last = last;     last->_next = next;     return next; }

        下面进行样例代码测试：

void test2() {     list<int> v;     v.push_back(1);     v.push_back(2);     v.push_back(3);     v.push_back(4);     v.push_back(5);     list<int>::iterator it = ++v.begin();     v.insert(it, 9);     v.erase(v.begin());     for (auto e : v)     {         std::cout << e << "  ";     }     std::cout << std::endl; }

测试数据结果如下：

        其它细节逻辑可自行测试，这里不再一一演示。

        总：list容器的模拟实现跟部分容器可能有些难度，这里注重要注意类型使用和转换，迭代器的模拟以及构造赋值与析构。功能实现的逻辑基本与链式逻辑一样。