C++ STL list 双向链表实现与迭代器详解

注意： 使用 erase 后，如果不接收返回值，原迭代器会失效。

排序（升序）

List 的 sort 属于稳定排序（n log n）：

v.sort();

排序（降序）

v.sort(std::greater<int>());

拼接

splice 支持整体拼接、单个元素拼接、范围拼接。 整体拼接： V2 拼接到 V1 末尾

v1.splice(v1.end(), v2);

单个元素拼接： 将 V2 中 it2 指向的元素拼接到 V1 的 it1 前面

v1.splice(it1, v2, it2);

去重

前提：元素已有序。

v2.unique();

反转

v2.reverse();

注意： reverse 翻转的是闭区间到开区间的元素。

模拟实现

list 的结构

List 属于不连续存储，通过指针连接。需要节点结构：包含 prev、next、val。

template<class T>
struct list_node {
public:
    list_node(const T& date = T()) : next(nullptr), prev(nullptr), val(date) {}
    list_node<T>* next;
    list_node<T>* prev;
    T val;
};

头节点设计：

template<class T>
class list {
    typedef list_node<T> Node;
public:
    list() : Head(nullptr) {
        Head = new Node;
        Head->next = Head;
        Head->prev = Head;
    }
private:
    Node* Head;
};

尾插

void push_back(const T& date) {
    Node* tmp = new Node(date);
    Node* pc = Head->prev;
    pc->next = tmp;
    tmp->prev = pc;
    tmp->next = Head;
    Head->prev = tmp;
}

尾删

void pop_back() {
    assert(Head->next != Head); // 至少有一个数据节点
    Node* cur = Head->prev;
    Node* pc = cur->prev;
    pc->next = Head;
    Head->prev = pc;
    delete cur;
    cur = nullptr;
}

头插

iterator push_front(iterator it, const T& val) {
    Node* pc = Head->next;
    Node* cur = new Node(val);
    Head->next = cur;
    cur->prev = Head;
    cur->next = pc;
    pc->prev = cur;
    return it._node = cur;
}

头删

iterator pop_front(iterator it) {
    assert(Head->next != Head);
    Node* cur = Head->next;
    Node* pc = cur->next;
    Head->next = pc;
    pc->prev = Head;
    delete cur;
    cur = nullptr;
    return it._node = pc;
}

拷贝构造

list(const list<T>& V) {
    Head = new Node;
    Head->next = Head;
    Head->prev = Head;
    typename list<T>::const_iterator it = V.begin();
    while (it != V.end()) {
        push_back(*it);
        it++;
    }
}

begin/end 实现：

iterator begin() { return Head->next; }
iterator end() { return Head; }
const_iterator begin() const { return Head->next; }
const_iterator end() const { return Head; }

赋值运算符重载

采用交换法：

void swap(const list<T>& Vt) {
    list<T> Vs(Vt);
    std::swap(Vs.Head, Head);
}

list<T>& operator=(const list<T>& V) {
    swap(V);
    return *this;
}

迭代器

迭代器封装为类，重载运算符。

迭代器结构

template<class T>
struct __list_iterator {
    typedef __list_iterator<T> iterator;
    typedef list_node<T> Node;
    Node* _node;

    __list_iterator(Node* node) : _node(node) {}

    T& operator*() { return _node->val; }
    iterator& operator++(int) {
        iterator tmp(*this);
        _node = _node->next;
        return tmp;
    }
    bool operator!=(const iterator& it) {
        return _node != it._node;
    }
};

无法修改的迭代器

方法 1：返回值加 const 修饰。 方法 2：通过类模板参数区分。

typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;

通过控制类模板第二个参数返回引用类型，达到'可修改'和'不可修改'的效果。

总结

迭代器 const 与非 const 的转化通过构造函数完成。节点类型转化为迭代器类型，非 const 迭代器转化为 const 类型，均涉及构造函数重载及参数区分。