c++-list

C++-list

std::list是C++标准模板库(STL)提供的双向链表容器，它提供了高效的插入和删除操作，特别适合频繁修改的序列。定义在 <list> 头文件中，属于 std 命名空间。该类的接口与常规容器接口基本一致。

模板原型：

template < class T, class Alloc = allocator<T> > class list;

allocator<T>：STL空间配置器（内存池）。

基本特性：

• 实现方式：双向链表结构，每个元素包含指向前驱和后继的指针。

• 内存分配：元素在内存中非连续存储的，通过指针链接。

• 泛型容器：通过模板实现，可以存储任何类型的元素。

• 迭代器：双向迭代器（支持++和–操作）。

1. 底层理解

list 底层是 带头双向循环链表。

template<typename T>
struct list_node{
    T val;
    list_node* prev;
    list_node* next;
    list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}
};
template<typename T>
class list {
    private:
        list_node<T>* node;
}

2. 成员函数

2.1 成员类型

2.2 构造函数

2.3 赋值重载

2.4 迭代器

2.5 容量相关的接口

2.6 元素的访问

2.7 修改相关的接口

2.8 其他操作

1. reverse

2. sort

3. merge

4. unique

5. remove

6.splice

3. list迭代器失效

C++中，list 与 vector 迭代器失效有所不同，list迭代器失效主要发生在 元素被删除时

迭代器失效的情况：

• erase 时被删除位置元素迭代器失效。

  • 解决方式：通过 erase 返回值重新获取迭代器（erase返回删除元素的下一个位置迭代器）

• 整个 list 被销毁或赋值时，所有迭代器都会失效。

4. list模拟实现

// list.hpp
#pragma once

#include <iostream>
#include <cassert>

namespace simulate_list {
    template<typename T>
    struct list_node{
        T val;
        list_node* prev;
        list_node* next;
        list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}
    };

    template<typename T , typename Ref , typename Ptr>
    struct __list_iterator {
        typedef list_node<T> node;
        typedef __list_iterator<T , Ref , Ptr> self;

        __list_iterator(node* nodeptr) :cur(nodeptr) {}

        self& operator++() {
            cur = cur->next;
            return *this;
        }

        self operator++(int) {
            self temp(cur);
            cur = cur->next;
            return temp;
        }

        self& operator--() {
            cur = cur->prev;
            return *this;
        }

        self operator--(int) {
            self temp(cur);
            cur = cur->prev;
            return temp;
        }

        Ref operator*() {
            return cur->val;
        }

        Ptr operator->() {
            return &(operator*());
        }

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

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

        node* cur;
    };

    template<typename 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); }
            bool empty() const { return head->next == head; }
            T& front() { assert(!empty()); return head->next->val; }
            T& back() { assert(!empty()); return head->prev->val; }
            const T& front() const { assert(!empty()); return head->next->val; }
            const T& back() const { assert(!empty()); return head->prev->val; }
            size_t size() const {
                size_t count = 0;
                for (auto& a : *this) count++;
                return count; 
            }
            void clear() {
                auto it = begin();
                while (it != end())
                    it = erase(it);
            }

            void initializer_list() {
                head = new node;
                head->prev = head;
                head->next = head;
            }
            list<T>() {
                initializer_list();
            }
            list<T>(const list<T>& l) {
                initializer_list();
                for (auto& node : l)
                    push_back(node);
            }
            list<T>& operator=(list<T> l) {
                std::swap(head , l.head);
                return *this;
            }
            ~list<T>() {
                clear();
                delete head;
                head = nullptr;
            }

            iterator insert(iterator position , const T& val);
            iterator erase(iterator position);
            void push_front(const T& val) { insert(begin() , val); }
            void pop_front() { assert(!empty()); erase(begin()); }
            void push_back(const T& val) { insert(end() , val); }
            void pop_back() { assert(!empty()); erase(--end()); }  

        private:
            node* head = nullptr;
    }; 
    
    template<typename T>
    typename list<T>::iterator list<T>::insert(list<T>::iterator position , const T& val) {
        node* prev = position.cur->prev;
        node* newnode = new node(val);
        prev->next = newnode;
        newnode->prev = prev;
        newnode->next = position.cur;
        position.cur->prev = newnode;
        return iterator(newnode);   // 返回新插入节点的迭代器
    }

    template<typename T>
    typename list<T>::iterator list<T>::erase(list<T>::iterator position) {
        node* prev = position.cur->prev;
        node* next = position.cur->next;
        prev->next = next;
        next->prev = prev;
        delete position.cur;
        return iterator(next);  // 返回删除元素的下一个元素
    }
    
} // namespace simulate_list end