C++ STL list 容器深度剖析与模拟实现

2. ->运算符的使用场景

假设某个场景下存在一个坐标类：

struct Pos {
    int _row;
    int _col;
    Pos(int row = 0, int col = 0) : _row(row), _col(col) {}
};

如果我们插入坐标，并且想要打印出坐标，该如何遍历？

错误示范：

void test_list2() {
    list<Pos> lt1;
    lt1.push_back(Pos(100, 100)); // 使用匿名对象
    lt1.push_back(Pos(200, 200));
    lt1.push_back(Pos(300, 300));
    // 这里的 it 是 Pos*, 是结构体指针
    list<Pos>::iterator it = lt1.begin();
    while (it != lt1.end()) {
        cout << *it << " "; // err
        ++it;
    }
    cout << endl;
}

原因：因为这里的 *it 返回的是 Pos 自定义类型，而访问自定义类型需要需要在类中自己重载流插入 (<<)，这里并没有重载，所以报错。

正确操作遍历的两种方式：

方式 1：通过 . 操作符直接访问结构体的成员变量 (一般不这样访问数据)。

cout << (*it)._row << ":" << (*it)._col << endl; // ok

方式 2：通过重载->运算符，对结构体指针进行解引用。

cout << it.operator->()->_row << ":" << it.operator->()->_col << endl; // ok

注意：其实这里严格来说是有两个箭头，第一个运算符重载的调用 it.operator->() 返回的是 Pos*，第二个箭头才是原生指针，Pos*再用箭头访问。为了可读性，省略了一个->。

void test_list2() {
    list<Pos> lt1;
    lt1.push_back(Pos(100, 100));
    lt1.push_back(Pos(200, 200));
    lt1.push_back(Pos(300, 300));
    list<Pos>::iterator it = lt1.begin();
    while (it != lt1.end()) {
        // 方式 1：
        // cout << (*it)._row << ":" << (*it)._col << endl; // ok
        //*it 就是 Pos 结构体，再用 . 操作符访问成员
        // 方式 2：
        cout << it->_row << ":" << it->_col << endl; // ok
        // cout << it.operator->()->_row << ":" << it.operator->()->_col << endl; // ok
        ++it;
    }
    cout << endl;
}

3. const 迭代器类的实现

在我们遍历数据时，有时会写一个打印函数，引用传参，一般建议加 const，这就出现了一个 const 链表：

void Func(const list<int>& lt1) {
    list<int>::const_iterator it = lt1.begin();
    while (it != lt1.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

const 迭代器不是在普通迭代器前面加 const，即不是 const iterator。

// err 这样使 it 本身也不能++ 了
const list<int>::iterator it = it.begin();

const 迭代器目的：本身可以修改，指向的内容不能修改，类似 const T* p。

所以我们要再定义一个类，控制 * 和 -> 的返回值就可以了。

template <class T>
class ListConstIterator {
    typedef ListNode<T> Node;
    typedef ListConstIterator<T> Self; // 名字变得简短
public:
    Node* _node; // 定义一个节点指针
    ListConstIterator(Node* node) : _node(node) {}

    // 前置：返回之后的值
    // ++it;
    // 返回与自己一样的类型
    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;
    }

    // 所以我们要再定义一个类，使用 const 控制 * 和 -> 的返回值就可以
    const T& operator*() { return _node->_data; }
    const T* operator->() { return &_node->_data; }

    bool operator!=(const Self& it) { return _node != it._node; }
    bool operator==(const Self& it) { return _node == it._node; }
};

4. 通过模板参数，把两个类型的迭代器类结合

可以发现，其实普通迭代器和 const 迭代器的本质区别是 * 和 ->，这两个运算符的返回类型的变化。两个类冗余，所以可以通过模板，给不同的模板参数，让编译器自己实例化两个类。

template <class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self; // 名字变得简短
    Node* _node; // 定义一个节点指针
    ListIterator(Node* node) : _node(node) {}

    // 前置：返回之后的值
    // ++it;
    // 返回与自己一样的类型
    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;
    }

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

    bool operator!=(const Self& it) { return _node != it._node; }
    bool operator==(const Self& it) { return _node == it._node; }
};

5. 迭代器类的一些问题的思考

(1) 类中是否需要写析构函数？ 这个迭代器类不要写析构函数，因为这里的节点不是迭代器的，是链表的，不用把它释放。我们使用 begin，end 返回节点给迭代器，是借助迭代器修改，访问数据，所以我们不需要释放。

(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝？ 这里也不需要写拷贝构造进行深拷贝，因为这里要的就是浅拷贝。begin 返回了第一个节点的迭代器给 it，这里就是用默认生成的拷贝构造，浅拷贝给 it，那这两个迭代器就指向同一个节点，所以这里用默认的拷贝构造和赋值拷贝就可以了。

三、list 类

1. list 类的结构

template <class T>
class list {
    typedef ListNode<T> Node;
public:
    // 物理空间不是连续的，不符合迭代器的行为，无法遍历
    // typedef Node* iterator;
    // 规范命名
    // typedef ListIterator<T> iterator;
    // typedef ListConstIterator<T> const_iterator;
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;
    // ………………
private:
    Node* _head;
};

2. 迭代器的实现

包含普通迭代器和 const 迭代器。

iterator begin() {
    // iterator it(_head->_next);
    // return it;
    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);
}

3. 插入数据 insert

iterator insert(iterator pos, const T& x) {
    Node* cur = pos._node; // 找到当前节点
    Node* newnode = new Node(x); // 申请节点
    Node* prev = cur->_prev; // 找到前一个节点
    // prev newnode cur 进行链接
    newnode->_next = cur;
    cur->_prev = newnode;
    prev->_next = newnode;
    newnode->_prev = prev;
    return iterator(newnode);
}

注意：链表的 insert 没有迭代器失效问题，因为没有扩容的概念，pos 位置的节点不会改变。但是 STL 库里 insert 也给了返回值，返回的是新插入位置的迭代器。

4. 删除数据 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;
    return iterator(next);
}

注意：链表的 erase 后有迭代器失效问题，pos 失效了，因为 pos 指向的节点被释放了。所以也要返回值，返回的是删除节点的下一个节点的迭代器。

5. 头插，头删，尾插，尾删

可以复用前面的 insert 和 erase。

// 尾插：end() 的下一个位置
void push_back(const T& x) {
    // Node* newnode = new Node(x); // 申请节点并且初始化
    // Node* tail = _head->_prev;
    // // 链接节点
    // tail->_next = newnode;
    // newnode->_prev = tail;
    // _head->_prev = newnode;
    // newnode->_next = _head;
    insert(end(), x);
}

// 尾删
void pop_back() {
    erase(--end()); // 注意：前置--
}

// 头插：在 begin 前面插入
void push_front(const T& x) {
    insert(begin(), x);
}

// 头删
void pop_front() {
    erase(begin());
}

6. 常见构造函数的实现

主要包含：构造函数，拷贝构造，initializer_list 构造 (列表构造)。

注意：由于这些都是在有哨兵位节点的前提下实现的，所以可以把申请哨兵位头节点这一步骤提取出来。

// 空初始化，申请哨兵位头节点
void empty_init() {
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}

list() {
    empty_init();
}

// 拷贝构造：直接复用尾插，前提要有哨兵位头节点
// lt2(lt1)
list(const list<T>& lt) {
    empty_init(); // 注意：使用范围 for 时加上 const 和&
    for (const auto& e : lt) {
        push_back(e);
    }
}

// initializer_list 构造，前提要有哨兵位头节点
list(initializer_list<T> il) {
    empty_init();
    for (const auto& e : il) {
        push_back(e);
    }
}

7. 析构函数

析构函数的作用是：删除整个链表结构，包括哨兵位节点。

// 清空当前数据 留头节点，其余节点释放
void clear() {
    auto it = begin();
    while (it != end()) {
        // 返回删除节点的下一个节点的迭代器
        it = erase(it);
    }
}

// 析构：销毁整个链表
~list() {
    clear();
    delete _head;
    _head = nullptr;
}