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

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

1. list 的介绍及使用

1.1 list 的介绍

list 是 C++ STL 中的一个重要容器，它是一个带头结点的双向循环链表。与 vector 不同，list 在任意位置插入和删除元素的时间复杂度都是 O(1)，但不支持随机访问（即不能通过下标直接访问元素）。

1.2 list 的使用

list 提供了丰富的接口，下面我们介绍其中一些常见且重要的接口。

1.2.1 list 的构造

构造函数	接口说明
list(size_type n, const value_type& val)	构造包含 n 个值为 val 的元素的 list
list()	构造空的 list
list(const list& x)	拷贝构造函数
list(InputIterator first, InputIterator last)	用区间 [first, last) 中的元素构造 list

1.2.2 list 迭代器的使用

迭代器可以暂时理解为指向 list 中某个节点的指针。

• begin()：返回指向第一个元素的迭代器
• end()：返回指向最后一个元素下一个位置的迭代器
• rbegin()：返回指向最后一个元素的反向迭代器（即 end() 位置）
• rend()：返回指向第一个元素前一个位置的反向迭代器（即 begin() 位置）

注意：

1. begin 和 end 是正向迭代器，++ 向后移动。

rbegin 和 rend 是反向迭代器，++ 向前移动。

1.2.3 list capacity

函数声明	接口说明
empty()	检测 list 是否为空
size()	返回 list 中有效节点的个数

1.2.4 list element access

函数声明	接口说明
front()	返回第一个节点中值的引用
back()	返回最后一个节点中值的引用

1.2.5 list modifiers

函数声明	接口说明
push_front	在 list 首元素前插入值为 val 的元素
pop_front	删除 list 中第一个元素
push_back	在 list 尾部插入值为 val 的元素
pop_back	删除 list 中最后一个元素
insert	在 position 位置插入值为 val 的元素
erase	删除 position 位置的元素
swap	交换两个 list 中的元素
clear	清空 list 中的有效元素

1.2.6 list 的迭代器失效

由于 list 的底层是双向循环链表，插入操作不会导致迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器不受影响。

错误的删除写法：

while (it != l.end()) { 
    l.erase(it); // it 失效 
    ++it; // 错误，it 已无效 
}

2. list 的模拟实现

2.1 基本结构

2.1.1 节点类 (list_node)

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

这是 list 的基础节点结构，采用双向链表设计，每个节点包含：

• _data: 存储实际数据
• _next: 指向下一个节点
• _prev: 指向上一个节点

2.1.2 迭代器类 (list_iterator)

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

关键特性：

• 通过模板参数 Ref 和 Ptr 实现 const 和非 const 迭代器的统一
• 支持前后遍历操作
• 支持箭头操作符访问成员

2.2 list 容器类

2.2.1 类型定义和迭代器

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 _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }

迭代器转换机制：

• Node* 可以隐式转换为 iterator，因为 list_iterator 有单参数构造函数
• begin() 返回第一个有效元素位置
• end() 返回头节点位置，符合 STL 左闭右开原则

2.2.2 构造函数和初始化

void empty_init() {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}
list() { empty_init(); }
// 拷贝构造
list(list<T>& lt) {
    empty_init();
    for (auto& e : lt) { push_back(e); }
}
// 初始化列表构造
list(initializer_list<int> il) {
    empty_init();
    for (auto& e : il) { push_back(e); }
}

2.2.3 插入操作

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; // 返回新插入节点的迭代器
}
void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }

2.2.4 删除操作

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; // 返回下一个有效位置的迭代器
}
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }

迭代器失效处理：

• erase 返回下一个有效位置的迭代器
• 正确处理删除操作后的迭代器续接

2.2.5 容量操作

size_t size() const { return _size; }
bool empty() const { return _size == 0; }
void clear() {
    auto it = begin();
    while (it != end()) {
        it = erase(it);
    }
}

2.2.6 赋值操作

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

2.3 迭代器模板技巧

// 使用模板参数实现 const 和非 const 迭代器的统一
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

这种设计避免了重复代码，只需要一个模板类就能同时支持普通迭代器和 const 迭代器。

2.4 测试示例

// 测试基本功能
void test_list01() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    // 遍历输出
    list<int>::iterator it = lt.begin();
    while (it != lt.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
// 测试迭代器失效
void test_list02() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    // insert 不会导致迭代器失效
    list<int>::iterator it = lt.begin();
    lt.insert(it, 10);
    *it += 100;
    // erase 会导致当前迭代器失效
    it = lt.begin();
    while (it != lt.end()) {
        if (*it % 2 == 0) {
            it = lt.erase(it); // 必须接收返回值
        } else {
            ++it;
        }
    }
}

源代码

#pragma once
#include<assert.h>
namespace bit {
template<class T> class list_node {
public:
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;
    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) { }
};
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--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }
    Self& operator--() { _node = _node->_prev; return *this; }
    bool operator!=(const Self& s) { return _node != s._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 _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }
    void empty_init() {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        _size = 0;
    }
    list() { empty_init(); }
    ~list() { clear(); delete _head; _head = nullptr; }
    void clear() {
        auto it = begin();
        while (it != end()) {
            it = erase(it);
        }
    }
    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(list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } }
    list(initializer_list<int> il) { empty_init(); for (auto& e : il) { push_back(e); } }
    void push_back(const T&x) { insert(end(), x); }
    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;
    }
    void push_front(const T& x) { insert(begin(), x); }
    void pop_back() { erase(--end()); }
    void pop_front() { erase(begin()); }
    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;
        return next;
    }
    size_t size() const { return _size; }
    bool empty() const { return _size == 0; }
private:
    Node* _head;
    size_t _size;
};
struct AA {
    int _a1;
    int _a2;
};
template<class Container> void print_container(const Container& con) {
    auto it = con.begin();
    while (it != con.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
void test_list01() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator it = lt.begin();
    while (it != lt.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    list<AA> lta;
    lta.push_back(AA());
    lta.push_back(AA());
    lta.push_back(AA());
    lta.push_back(AA());
    list<AA>::iterator ita = lta.begin();
    while (ita != lta.end()) {
        cout << ita->_a1 << ":" << ita->_a2 << endl;
        ++ita;
    }
    cout << endl;
    print_container(lt);
}
void test_list02() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator it = lt.begin();
    lt.insert(it, 10);
    *it += 100;
    print_container(lt);
    it = lt.begin();
    while (it != lt.end()) {
        if (*it % 2 == 0) {
            it=lt.erase(it);
        } else {
            ++it;
        }
    }
    print_container(lt);
}
void test_list03() {
    list<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    list<int> lt2(lt1);
    print_container(lt1);
    print_container(lt2);
    list<int> lt3;
    lt3.push_back(10);
    lt3.push_back(20);
    lt3.push_back(30);
    lt3.push_back(40);
    lt1 = lt3;
    print_container(lt1);
    print_container(lt3);
}
void func(const list<int>& lt) { print_container(lt); }
void test_list04() {
    list<int> lt0 ( { 1,3,5 });
    list<int> lt1= {1, 2, 3, 4, 5};
    print_container(lt1);
    auto il = { 1,2,3,4 };
    cout << typeid(il).name() << endl;
    func(lt1);
    func({ 1,3,6,7 });
}
};

2.5 设计要点总结

1. 双向循环链表：头节点连接首尾，简化边界处理
2. 迭代器封装：隐藏底层指针，提供统一接口
3. 模板复用：通过模板参数减少代码重复
4. 异常安全：正确管理资源，避免内存泄漏
5. STL 兼容：遵循 STL 接口规范

这个实现展示了 list 容器的核心机制，包括节点管理、迭代器设计、插入删除操作等关键技术点。

3. list 与 vector 的对比

对比维度	vector	list
底层结构	动态顺序表，连续空间	带头结点的双向循环链表
随机访问	支持 O(1)	不支持，访问元素 O(N)
插入删除	任意位置效率低 O(N)，可能增容	任意位置效率高 O(1)
空间利用率	连续空间，内存碎片少，缓存友好	节点动态开辟，易产生内存碎片
迭代器类型	原生态指针	对节点指针进行封装
迭代器失效	插入删除可能导致全部或部分失效	删除时仅当前迭代器失效