STL list 容器模拟实现与核心原理

list 是一个带头的双向循环链表，因此，构造时创建一个带头的节点。

3. insert

void insert(const iterator& pos, const T& x) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    newnode->_prev = prev;
    prev->_next = newnode;
    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
}

list 容器与数据结构中带头双向循环链表的原理是一样的，只不过进行了封装而已。看不懂细节的，可以移步相关数据结构文章。list 容器，重点讲解迭代器部分。

4. push_back

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;
}

其实，push_back就是尾插，可以复用 insert 函数。这样去实现。

void push_back(const T& x) {
    insert(end(), x);
}

这样是不是简单多了，end返回的就是 list 容器中的末尾后的一个位置（即头结点），而插入节点是在该位置之前插入的。

5. 拷贝构造

// lt2(lt1)
list(list<T>& lt) {
    empty_init();
    for (const auto& e : lt) {
        push_back(e);
    }
}

拷贝构造也需要先初始化 list 对象，在调用 push_back 逐个插入元素。

6. 初始化列表构造

list(initializer_list<T> lt) {
    empty_init();
    for (const auto& e : lt) {
        push_back(e);
    }
}

逐个访问初始化列表中的元素，进行插入。

7. operator=

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

// lt3=lt2
// 拷贝构造 + 交换
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

通过拷贝构造出一个局部对象，在进行资源的交换就完成赋值重载了。

8. erase

iterator erase(iterator pos) {
    assert(pos != end());
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    --_size;
    // 隐式类型转换
    return iterator(next);
}

请参考相关数据结构文档了解具体实现。

9. pop_back, push_front, pop_front

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

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

void pop_front() {
    erase(begin());
}

直接复用 insert,erase 函数即可。

10. clear

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

清空 list 中的所有元素，从 list 中的 begin 位置的节点开始删除。

11. 析构函数

~list() {
    clear();
    delete _head;
    _head = nullptr;
    _size = 0;
}

清空 list 容器中的所有节点，再删除头结点，更新_size。

12. size

size_t size() const {
    return _size;
}

13. 迭代器

iterator begin() {
    // _head->_next 是一个指向 list_node 节点的指针
    // iterator 是一个 list_iterator 的类
    // 隐式类型转换，借助构造函数
    // 返回的是 iterator 的临时对象
    // return _head->_next;
    return iterator(_head->_next);
}

iterator end() {
    // 隐式类型转换
    // return _head;
    return iterator(_head);
}

const_iterator begin() const {
    return const_iterator(_head->_next);
}

const_iterator end() const {
    // 隐式类型转换
    // return _head;
    return const_iterator(_head);
}

以前使用库里面的迭代器，都是直接获取迭代器，该迭代器指向某个元素的这块空间，通过解引用就可以访问到该元素。那么，在 list 这里，可以直接用原生指针 Node*（list_node<T>*）作为迭代器吗？答案是不可以的。

**因为如果用原生指针 Node*(内置类型) 作为迭代器，那么解引用能访问到元素，但是使用迭代器的方式就会与平时不一样，需要手动访问数据，而且原生指针是一个内置类型，要如何通过++操作访问下一个节点呢**？基于以上原因，因此，不能用原生指针作为迭代器。

那要如何处理呢？

我们可以对原生指针进行封装，使之成为一个自定义类型，这样不就可以通过解引用操作，调用运算符重载函数了，访问到数据了吗！其次，自定义类型在++操作的时候，也可以通过运算符重载指向下一个 Node 节点。

具体实现如下。

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->val;
    }
    
    Ptr operator->() {
        return &_node->val;
    }
    
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    Self operator++(int) {
        // 浅拷贝，默认拷贝构造函数就可以用
        list_iterator<T> tmp(*this);
        _node = _node->_next;
        // 局部变量，不能用引用返回
        return tmp;
    }
    
    Self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    
    Self operator--(int) {
        list_iterator<T> 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;
    }
};

可以看到，这里不仅有模板参数 T，还多了两个模板参数 Ref 和 Ptr。实现迭代器的时候，不仅实现了普通迭代器，还实现了 const 版本的迭代器，如果不增加这两个模板参数，我们就还需要写一个类来封装 Node*指针，而且，这两个类的代码基本是一样的，在返回值，参数类型上会有所区别，代码会非常的冗余。所以，添加两个模板参数就可以很好的解决这个问题了。

三、完整代码实现

list.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace LC {
    template <class T>
    struct list_node {
        list_node<T>* _prev;
        list_node<T>* _next;
        T val;
        // 默认构造函数
        list_node(const T& x = T()) : _prev(nullptr), _next(nullptr), val(x) {}
    };

    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->val; }
        Ptr operator->() { return &_node->val; }
        Self& operator++() { _node = _node->_next; return *this; }
        Self operator++(int) {
            list_iterator<T> tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        Self& operator--() { _node = _node->_prev; return *this; }
        Self operator--(int) {
            list_iterator<T> 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; }
    };

    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);
        }

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

        // 默认构造函数
        list() { empty_init(); }

        // lt2(lt1)
        list(list<T>& lt) {
            empty_init();
            for (const auto& e : lt) {
                push_back(e);
            }
        }

        list(initializer_list<T> lt) {
            empty_init();
            for (const auto& e : lt) {
                push_back(e);
            }
        }

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

        // lt3=lt2
        // 拷贝构造 + 交换
        list<T>& operator=(list<T> lt) {
            swap(lt);
            return *this;
        }

        size_t size() const { return _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;
        }

        // 在 pos 位置之前插入
        void insert(const iterator& pos, const T& x) {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);
            newnode->_prev = prev;
            prev->_next = newnode;
            newnode->_next = cur;
            cur->_prev = newnode;
            ++_size;
        }

        iterator erase(iterator pos) {
            assert(pos != end());
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;
            delete cur;
            --_size;
            return iterator(next);
        }

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

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

        void pop_front() {
            erase(begin());
        }

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

        ~list() {
            clear();
            delete _head;
            _head = nullptr;
            _size = 0;
        }

    private:
        Node* _head;
        size_t _size;
    };
}

test.cc

#define _CRT_SECURE_NO_WARNINGS
#include "list.h"

struct A {
    int _a1;
    int _a2;
    A(int a1 = 1, int a2 = 2) : _a1(a1), _a2(a2) {}
};

void testlist1() {
    LC::list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    LC::list<int>::iterator it = l1.begin();
    // l1.end() 返回的是临时变量，形参必须是 const&
    while (it != l1.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    l1.insert(l1.begin(), 5);
    l1.insert(l1.end(), 6);
    it = l1.begin();
    while (it != l1.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    l1.erase(l1.begin());
    it = l1.begin();
    while (it != l1.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void testlist2() {
    LC::list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    LC::list<int> l2(l1);
    LC::list<int>::iterator it = l2.begin();
    while (it != l2.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    cout << l2.size() << endl;
    LC::list<int> l3;
    l3.push_back(10);
    l3.push_back(20);
    l3.push_back(30);
    l3.push_back(40);
    l3.push_back(50);
    l2 = l3;
    LC::list<int>::iterator it1 = l2.begin();
    while (it1 != l2.end()) {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;
    cout << l2.size() << endl;
    // LC::list<double> l4 = { 100,200,300,400 };
    LC::list<double> l4 = { 1.1, 2.2, 3.3, 4.4 };
    LC::list<double>::iterator it2 = l4.begin();
    while (it2 != l4.end()) {
        cout << *it2 << " ";
        ++it2;
    }
    cout << endl;
    cout << l4.size() << endl;
    LC::list<A> l5;
    l5.push_back({ 1, 1 });
    l5.push_back({ 2, 2 });
    l5.push_back({ 3, 3 });
    l5.push_back({ 4, 4 });
    LC::list<A>::iterator it3 = l5.begin();
    while (it3 != l5.end()) {
        cout << it3->_a1 << " " << it3->_a2 << endl;
        ++it3;
    }
    cout << endl;
    cout << l5.size() << endl;
}

int main() {
    testlist2();
    return 0;
}