C++ STL list 容器详解：使用与模拟实现

template<class T> 
struct list_node {
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;
    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) {}
};

这里采用双向链表设计，便于双向遍历和插入删除时的指针重连。

迭代器封装

通过模板参数 Ref 和 Ptr 统一处理 const 与非 const 迭代器，避免代码重复。

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->_data; }
    Ptr operator->() { return &_node->_data; }
    
    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& s) { return _node != s._node; }
};

关键点在于解引用操作符重载，以及利用隐式转换将 Node* 转为迭代器对象。

容器核心逻辑

容器内部维护一个头节点 _head，形成闭环。begin() 返回 _head->_next，end() 返回 _head。

插入操作的核心在于指针重连。以 insert 为例，我们需要找到目标位置的前驱节点，调整前后指针指向新节点。

iterator insert(iterator pos, const T& x) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    
    ++_size;
    return newnode; // 返回新插入节点的迭代器
}

删除操作同理，断开节点连接并释放内存，同时返回下一个有效位置的迭代器，方便调用者继续遍历。

iterator erase(iterator pos) {
    assert(pos != end());
    Node* prev = pos._node->_prev;
    Node* next = pos._node->_next;
    
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;
    --_size;
    
    return next; // 返回下一个有效位置
}

赋值与交换

利用拷贝交换语义实现赋值运算符，既高效又安全。

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

list 与 vector 的对比

在实际开发中，选择哪种容器取决于具体需求。

总结来说，如果主要涉及尾部操作且需要随机访问，vector 是首选；若需要在中间频繁插入删除且不关心索引访问，list 更为合适。