STL-list的使用及其模拟实现

      在C++标准库中，list 是一个双向链表容器，用于存储一系列元素。与 vector 和 deque 等容器不同，list 使用带头双向循环链表的数据结构来组织元素，因此list插入删除的效率非常高。

list的使用

list的构造函数

list迭代器

list的成员函数

list的模拟实现

template
struct list_node {
    list_node* _next;
    list_node* _prev;
    T _data;

    list_node(const T& x=T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(x)
    {}
};
template
struct _list_iterator {
    typedef list_node node;
    typedef _list_iterator self;
    node* _node;
    _list_iterator(node* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};

/*template
struct _list_const_iterator {
    typedef list_node node;
    typedef _list_const_iterator self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};*/
template
class list {
    typedef list_node node;
public:
    typedef _list_iterator iterator;
    typedef _list_iterator const_iterator;
    //typedef _list_const_iterator const_iterator;
    typedef ReverseIterator reverse_iterator;
    typedef ReverseIterator const_reverse_iterator;
    /*reverse_iterator rbegin()
    {
        return reverse_iterator(_head->_prev);
    }

    reverse_iterator rend()
    {
        return reverse_iterator(_head);
    }*/
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    iterator begin() {
        //iterator it(_head->next);
        //return it;
        return iterator(_head->_next);
    }
    const_iterator begin() const{
        return const_iterator(_head->_next);
    }
    iterator end() {
        //iterator it(_head);
        //return it;
        return iterator(_head);
    }
    const_iterator end() const{
        return const_iterator(_head);
    }
    void empty_init() {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    list() {
        empty_init();
    }

    template
    list(Iterator first, Iterator last)
    {
        empty_init();
        while (first != last) 
        {
            push_back(*first);
            ++first;
        }
    }
    // lt2(lt1)
    /*list(const list& lt) {
        empty_init();
        for (auto e : lt) {
            push_back(e);
        }
    }*/
    void swap(list& tmp) {
        std::swap(_head, tmp._head);
    }
    list(const list& lt) {
        empty_init();

        list tmp(lt.begin(), lt.end());
        swap(tmp);
    }
    //lt1=lt3
    list& operator=(list lt) {
        swap(lt);
        return *this;
    }
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }
    void clear() {
        iterator it = begin();
        while (it != end()) {
            //it = erase(it);
            erase(it++);
        }
    }
    void push_back(const T& x) {
        /*node* tail = _head->_prev;
        node* new_node = new node(x);

        tail->_next = new_node;
        new_node->_prev = tail;
        new_node->_next = _head;
        _head->_prev = new_node;*/
        insert(end(), x);

    }
    void push_front(const T& x) {
        insert(begin(), x);
    }
    void pop_back() {
        erase(--end());
    }
    void pop_front() {
        erase(begin());
    }
    void insert(iterator pos,const T& x) {
        node* cur = pos._node;
        node* prev = cur->_prev;

        node* new_node = new node(x);
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;
    }
    //会导致迭代器失效 pos
    iterator erase(iterator pos, const T& x=0) {
        assert(pos != end());
        node* prev = pos._node->_prev;
        node* next = pos._node->_next;
        prev->_next = next;
        next->_prev = prev;
        delete pos._node;

        return iterator(next);
    }
private:
    node* _head;
};

迭代器和成员函数的模拟实现

template
struct _list_iterator {
    typedef list_node node;
    typedef _list_iterator self;
    node* _node;
    _list_iterator(node* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};

/*template
struct _list_const_iterator {
    typedef list_node node;
    typedef _list_const_iterator self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};*/

迭代器共有两种：

1.迭代器要么就是原生指针
2.迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。这样就不用专门写两种不同类型的迭代器，泛型编程减少了代码的复用，提高了效率。

list的构造函数

void empty_init() {
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
}
list() {
    empty_init();
}

list的拷贝构造

template
list(Iterator first, Iterator last)
{
    empty_init();
    while (first != last) 
    {
        push_back(*first);
        ++first;
    }
}

void swap(list& tmp) {
    std::swap(_head, tmp._head);
}
list(const list& lt) {
    empty_init();

    list tmp(lt.begin(), lt.end());
    swap(tmp);
}

list的析构函数

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

赋值运算符重载

//lt1=lt3
list& operator=(list lt) {
    swap(lt);
    return *this;
}

list的插入和删除

void push_back(const T& x) {
    /*node* tail = _head->_prev;
    node* new_node = new node(x);

    tail->_next = new_node;
    new_node->_prev = tail;
    new_node->_next = _head;
    _head->_prev = new_node;*/
    insert(end(), x);

}
void push_front(const T& x) {
    insert(begin(), x);
}
void pop_back() {
    erase(--end());
}
void pop_front() {
    erase(begin());
}
void insert(iterator pos,const T& x) {
    node* cur = pos._node;
    node* prev = cur->_prev;

    node* new_node = new node(x);
    prev->_next = new_node;
    new_node->_prev = prev;
    new_node->_next = cur;
    cur->_prev = new_node;
}
//会导致迭代器失效 pos
iterator erase(iterator pos, const T& x=0) {
    assert(pos != end());
    node* prev = pos._node->_prev;
    node* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;

    return iterator(next);
}

清空list中所有元素

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

list迭代器失效

      迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

      解决方法：可以使用 erase 函数的返回值，它会返回一个指向下一个有效元素的迭代器。

list和vector区别

底层实现：

      list 通常是一个双向链表，每个节点都包含了数据和指向前一个和后一个节点的指针。这使得在任何位置进行插入和删除操作都是高效的，但随机访问和内存占用可能相对较差。
     vector 是一个动态数组，元素在内存中是连续存储的。这使得随机访问非常高效，但插入和删除操作可能需要移动大量的元素，效率较低。

插入和删除：

     在 list 中，插入和删除操作是高效的，无论是在容器的任何位置还是在开头和结尾。这使得 list 在需要频繁插入和删除操作时非常适用。
     在 vector 中，插入和删除操作可能需要移动元素，特别是在容器的中间或开头。因此，当涉及大量插入和删除操作时，vector 可能不如 list 效率高。

随机访问：

list 不支持随机访问，即不能通过索引直接访问元素，必须通过迭代器逐个遍历。
vector 支持随机访问，可以通过索引快速访问元素，具有良好的随机访问性能。

迭代器失效：

在 list 中，插入和删除操作不会导致迭代器失效，因为节点之间的关系不会改变。
在 vector 中，插入和删除操作可能导致内存重新分配，从而使原来的迭代器失效。

综上所述，如果你需要频繁进行(头部和中间)插入和删除操作，而对于随机访问性能没有特别高的要求，可以选择list；如果想要随机访问以及尾插和尾删vector是更好的选择。