C++ STL笔记05-std::list双向链表

Created in November 18, 2023

2023   ·   code   C++   ·   STL

std::list用法

std::list是C++标准库中的一个容器，它有如下特点：

  • 双向链表结构：std::list使用双向链表实现，每个元素都包含指向前一个和后一个元素的指针，这使得在列表中间快速插入和删除元素的时间复杂度为O(1)。

  • 非连续内存：与数组不同，std::list的元素在内存中不是连续存储的，因为每个元素包含指向前后元素的指针。这意味着在插入和删除操作时，不需要移动大量的元素，这有助于提高性能。

  • 无随机访问：由于元素不是在连续内存中存储的，因此不能像数组一样通过索引进行O(1)的随机访问。在 std::list中，访问元素需要遍历链表，因此时间复杂度为O(n)。

  • 动态大小：std::list的大小可以动态地增长或减小，不需要提前指定容器的大小。

  • 高效的插入和删除操作：由于 std::list是双向链表，它对于在列表的任意位置执行插入和删除操作非常高效。这使得它在需要频繁插入和删除操作的场景中比较有优势。

  • 相对较大的存储开销：由于每个元素都需要额外的指针来指向前一个和后一个元素，相较于数组，std::list在存储上会有一些额外的开销。

  • 不支持随机访问迭代器：std::list提供双向迭代器，不支持随机访问迭代器。这与支持随机访问的容器(如 std::vector)不同。

std::list的一些常用用法如下：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

 
#include <iostream>
#include <list>

template <typename T>
void printList(std::list<T> &list) {
    // 遍历列表并输出元素
    for (T &x : list) {
        std::cout << x << " ";
    }
    
    std::cout << std::endl;
}

int main()
{
    // 创建一个存储整数的列表
    std::list<int> myList;

    // 在列表末尾插入元素
    std::cout << "Add to the back: ";
    
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);
    
    printList(myList);
    
    // 在列表开头插入元素
    std::cout << "Add to the front: ";
    
    myList.push_front(0);
    
    printList(myList);
    
    // 删除列表末尾的元素
    std::cout << "Remove the last element: ";
    
    myList.pop_back();
    
    printList(myList);
    
    // 删除列表开头的元素
    std::cout << "Remove the first element: ";
    
    myList.pop_front();
    
    printList(myList);
    
    // 在指定位置插入元素
    std::cout << "Insert to the 2nd position: ";
    
    auto it = myList.begin();
    ++it; // 移动到列表的第二个元素位置
    myList.insert(it, 4);
    
    printList(myList);

    // 在指定位置删除元素
    std::cout << "Remove the 2nd element: ";
    
    it = myList.begin();
    ++it; // 移动到列表的第二个元素位置
    myList.erase(it);
    
    printList(myList);
    
    // 获取列表大小
    std::cout << "Size of the list: " << myList.size() << std::endl;
    
    // 检查列表是否为空
    if (myList.empty()) {
        std::cout << "The list is empty." << std::endl;
    } else {
        std::cout << "The list is not empty." << std::endl;
    }
    
    // 清空列表
    std::cout << "Clear the list. " ;
    myList.clear();

    // 再次检查列表是否为空
    if (myList.empty()) {
        std::cout << "The list is empty." << std::endl;
    } else {
        std::cout << "The list is not empty." << std::endl;
    }

    return 0;
}

运行上面的代码可以得到如下结果：



1
2
3
4
5
6
7
8
9

 
Add to the back: 1 2 3 
Add to the front: 0 1 2 3 
Remove the last element: 0 1 2 
Remove the first element: 1 2 
Insert to the 2nd position: 1 4 2 
Remove the 2nd element: 1 2 
Size of the list: 2
The list is not empty.
Clear the list. The list is empty.

List实现

接下来我们从零开始实现一个类似于标准库中std::list的双向链表List。

链表节点

在开始实现List之前我们需要先实现一下链表的节点，它通过ListBaseNode模板来实现：



1
2
3
4
5
6
7
8
9
10
11
12
13
14

 
#ifdef NDEBUG
#define DEBUG_INIT_DEADBEAF(T)
#else
#define DEBUG_INIT_DEADBEAF(T) {(T *)0xdeadbeaf}
#endif

template <class T>
struct ListBaseNode {
    ListBaseNode *m_next DEBUG_INIT_DEADBEAF(ListBaseNode);
    ListBaseNode *m_prev DEBUG_INIT_DEADBEAF(ListBaseNode);

    inline T &value();
    inline T const &value() const;
};

ListBaseNode内部包含m_next以及m_prev两个指针，分别指向当前节点的前一个和后一个节点。这里引入了一个调试宏DEBUG_INIT_DEADBEAF：如果NDEBUG未被定义(即处于调试模式)，DEBUG_INIT_DEADBEAF会把指针成员初始化为一个特殊的值0xdeadbeaf以便发现和追踪可能出现的问题。

还需要注意的是这里定义的ListBaseNode本身是不包含任何数据的，我们通过一个继承自ListBaseNode的新类ListValueNode来表示一个携带数据的链表节点：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 
template <class T>
struct ListValueNode : ListBaseNode<T> {
    union {
        T m_value;
    };
};

template <class T>
inline T &ListBaseNode<T>::value() {
    return static_cast<ListValueNode<T> &>(*this).m_value;
}

template <class T>
inline T const &ListBaseNode<T>::value() const {
    return static_cast<ListValueNode<T> const &>(*this).m_value;
}

当我们需要获取节点的数据时可以通过value()函数访问实际值所存储的ListValueNode类。此时函数会先把当前的ListBaseNode<T>转换为ListValueNode<T>类型的指针，然后访问m_value成员变量并返回所需的数据。

模板定义

List的模板定义类似于Vector，都包含模板参数T和Alloc分别用来指定元素类型和管理内存。List本身则包含三个成员变量：

  • m_dummy为链表的虚拟头节点
  • m_size用来记录链表的大小
  • m_alloc用来保存内存分配器

同时，这里还引入了两个类型别名ListNode和AllocNode。其中AllocNode将原本T类型的内存分配器重新绑定为ListValueNode<T>类型的内存分配器，这可以方便我们处理节点。



1
2
3
4
5
6
7
8
9
10

 
template <class T, class Alloc = std::allocator<T>>
struct List {
private:
    using ListNode  = ListBaseNode<T>;
    using AllocNode = std::allocator_traits<Alloc>::template rebind_alloc<ListValueNode<T>>;

    ListNode m_dummy;
    size_t m_size;
    [[no_unique_address]] Alloc m_alloc;
}

同时，我们还需要引入一些类型别名作为List的元信息：



1
2
3
4
5
6
7
8
9
10
11
12

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    using value_type      = T;
    using allocator_type  = Alloc;
    using size_type       = size_t;
    using difference_type = ptrdiff_t;
    using pointer         =  T *;
    using const_pointer   = T const *;
    using reference       = T &;
    using const_reference = T const &;
...
}

为了方便添加和删除节点，这里还定义了两个辅助函数newNode()和deleteNode()进行处理：



1
2
3
4
5
6
7
8
9
10
11
12

 
template <class T, class Alloc = std::allocator<T>>
struct List {
...
private:
    ListNode *newNode() {
        return AllocNode{m_alloc}.allocate(1);
    }

    void deleteNode(ListNode *node) noexcept {
        AllocNode{m_alloc}.deallocate(static_cast<ListValueNode<T> *>(node), 1);
    }
}

构造函数

默认构造函数

List的默认构造函数用来处理无参数构造的情况。此时整个链表为空，我们需要把m_size设置为0并让虚拟头节点m_dummy的前后指针都指向自身。



1
2
3
4
5
6
7
8
9
10
11
12
13
14

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    List() noexcept {
        m_size = 0;
        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
    }

    explicit List(Alloc const &alloc) noexcept : m_alloc(alloc) {
        m_size = 0;
        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
    }
}

参数化构造函数

另一种常见情况是初始化一个大小为n、每个节点包含数据val的链表。为此我们先来实现一个辅助函数_uninit_assign()：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
private:
    void _uninit_assign(size_t n) {
        m_size = n;
        ListNode *prev = &m_dummy;

        while (n) {
            ListNode *node = newNode();
            prev->m_next = node;
            node->m_prev = prev;
            std::construct_at(&node->value());
            prev = node;
            --n;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }

    void _uninit_assign(size_t n, T const &val) {
        m_size = n;
        ListNode *prev = &m_dummy;

        while (n) {
            ListNode *node = newNode();
            prev->m_next = node;
            node->m_prev = prev;
            std::construct_at(&node->value(), val);
            prev = node;
            --n;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }
}

此外，我们再实现一个针对迭代器作为输入参数的版本：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
private:
    template <std::input_iterator InputIt>
    void _uninit_assign(InputIt first, InputIt last) {
        m_size = 0;
        ListNode *prev = &m_dummy;

        while (first != last) {
            ListNode *node = newNode();
            prev->m_next = node;
            node->m_prev = prev;
            std::construct_at(&node->value(), *first);
            prev = node;
            ++first;
            ++m_size;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }
}

完成辅助函数_uninit_assign()后，我们就可以在参数构造函数中把参数转发给_uninit_assign()进行初始化：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    explicit List(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        _uninit_assign(n);
    }

    List(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        _uninit_assign(n, val);
    }

    template <std::input_iterator InputIt>
    List(InputIt first, InputIt last, Alloc const &alloc = Alloc()) {
        _uninit_assign(first, last);
    }

    List(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
    : List(ilist.begin(), ilist.end(), alloc) {}
}

移动构造函数

对于移动构造的情况，我们同样需要先实现一个辅助函数_uninit_move_assign()：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
private:
    void _uninit_move_assign(List &&that) {
        auto prev = that.m_dummy.m_prev;
        auto next = that.m_dummy.m_next;

        prev->m_next = &m_dummy;
        next->m_prev = &m_dummy;

        m_dummy = that.m_dummy;
        that.m_dummy.m_prev = that.m_dummy.m_next = &that.m_dummy;

        m_size = that.m_size;
        that.m_size = 0;
    }
}

这样就可以在移动构造中将参数转发给_uninit_move_assign()完成初始化：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    List(List &&that) : m_alloc(std::move(that.m_alloc)) {
        _uninit_move_assign(std::move(that));
    }

    List(List &&that, Alloc const &alloc) : m_alloc(alloc) {
        _uninit_move_assign(std::move(that));
    }

    List &operator=(List &&that) {
        m_alloc = std::move(that.m_alloc);
        clear();
        _uninit_move_assign(std::move(that));

        return *this;
    }
}

拷贝构造函数

List的拷贝构造函数比较简单，我们可以直接调用前面实现的_uninit_assign()：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    List(List const &that) : m_alloc(that.m_alloc) {
        _uninit_assign(that.cbegin(), that.cend());
    }

    List(List const &that, Alloc const &alloc) : m_alloc(alloc) {
        _uninit_assign(that.cbegin(), that.cend());
    }

    List &operator=(List const &that) {
        assign(that.cbegin(), that.cend());
        return *this;
    }

    List &operator=(std::initializer_list<T> ilist) {
        assign(ilist);
        return *this;
    }
}

实际上这里定义的拷贝构造函数是通过迭代器以及assign()函数来实现的。关于迭代器和assign()函数相关的代码我们会稍后再介绍。

访问元素

List不允许随机访问，我们只能通过对链表进行遍历的方式来访问其中的元素。这里只需要实现访问链表首尾节点的相关函数即可：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    T &front() noexcept {
        return m_dummy.m_next->value();
    }

    T &back() noexcept {
        return m_dummy.m_prev->value();
    }

    T const &front() const noexcept {
        return m_dummy.m_next->value();
    }

    T const &back() const noexcept {
        return m_dummy.m_prev->value();
    }
}

迭代器

List需要实现双向迭代器，为此我们在List内部定义一个iterator类：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    struct iterator {
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T *;
        using reference         = T &;

    private:
        ListNode *m_curr;

        friend List;

        explicit iterator(ListNode *curr) noexcept
        : m_curr(curr) {}
    }
}

对于双向迭代器，iterator需要实现前缀递增++iterator、后缀递增iterator++、前缀递减--iterator、后缀递减iterator--、解引用*、以及比较==!=等操作：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    struct iterator {
        ...
    public:
        iterator() = default;

        iterator &operator++() noexcept { // ++iterator
            m_curr = m_curr->m_next;
            return *this;
        }

        iterator operator++(int) noexcept { // iterator++
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        iterator &operator--() noexcept { // --iterator
            m_curr = m_curr->m_prev;
            return *this;
        }

        iterator operator--(int) noexcept { // iterator--
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        T &operator*() const noexcept {
            return m_curr->value();
        }

        bool operator!=(iterator const &that) const noexcept {
            return m_curr != that.m_curr;
        }

        bool operator==(iterator const &that) const noexcept {
            return !(*this != that);
        }
    };
}

有了iterator的实现后就可以实现List的迭代器行为：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    iterator begin() noexcept {
        return iterator{m_dummy.m_next};
    }

    iterator end() noexcept {
        return iterator{&m_dummy};
    }

    using reverse_iterator = std::reverse_iterator<iterator>;

    reverse_iterator rbegin() noexcept {
        return std::make_reverse_iterator(end());
    }

    reverse_iterator rend() noexcept {
        return std::make_reverse_iterator(begin());
    }
}

类似地，我们还可以实现常量迭代器const_iterator处理常量迭代的情况：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    struct const_iterator {
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T const *;
        using reference         = T const &;

    private:
        ListNode const *m_curr;

        friend List;

        explicit const_iterator(ListNode const *curr) noexcept
        : m_curr(curr) {}

    public:
        const_iterator() = default;

        const_iterator(iterator that) noexcept : m_curr(that.m_curr) {
        }

        explicit operator iterator() noexcept {
            return iterator{const_cast<ListNode *>(m_curr)};
        }

        const_iterator &operator++() noexcept { // ++iterator
            m_curr = m_curr->m_next;
            return *this;
        }

        const_iterator operator++(int) noexcept { // iterator++
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        const_iterator &operator--() noexcept { // --iterator
            m_curr = m_curr->m_prev;
            return *this;
        }

        const_iterator operator--(int) noexcept { // iterator--
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        T const &operator*() const noexcept {
            return m_curr->value();
        }

        bool operator!=(const_iterator const &that) const noexcept {
            return m_curr != that.m_curr;
        }

        bool operator==(const_iterator const &that) const noexcept {
            return !(*this != that);
        }
    };

    const_iterator cbegin() const noexcept {
        return const_iterator{m_dummy.m_next};
    }

    const_iterator cend() const noexcept {
        return const_iterator{&m_dummy};
    }

    const_iterator begin() const noexcept {
        return cbegin();
    }

    const_iterator end() const noexcept {
        return cend();
    }

    using reverse_const_iterator = std::reverse_iterator<const_iterator>;

    reverse_const_iterator crbegin() const noexcept {
        return std::make_reverse_iterator(cend());
    }

    reverse_const_iterator crend() const noexcept {
        return std::make_reverse_iterator(cbegin());
    }

    reverse_const_iterator rbegin() const noexcept {
        return crbegin();
    }

    reverse_const_iterator rend() const noexcept {
        return crend();
    }
}

修改链表

clear()

clear()函数的作用是清空当前链表。在调用时clear()函数会依次访问链表的每个节点，然后清除节点数据并释放节点自身的内存：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    void clear() noexcept {
        ListNode *curr = m_dummy.m_next;

        while (curr != &m_dummy) {
            std::destroy_at(&curr->value());
            auto next = curr->m_next;
            deleteNode(curr);
            curr = next;
        }

        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
        m_size = 0;
    }
}

List的析构函数就是基于clear()函数实现的：



1
2
3
4
5
6
7
8

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    ~List() noexcept {
        clear();
    }
}

assign()

assign()函数的作用类似于参数化构造函数中的_uninit_assign()。实际上assign()函数也是基于_uninit_assign()来实现的，不过要在调用_uninit_assign()前先清空链表：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <std::input_iterator InputIt>
    void assign(InputIt first, InputIt last) {
        clear();
        _uninit_assign(first, last);
    }

    void assign(std::initializer_list<T> ilist) {
        clear();
        _uninit_assign(ilist.begin(), ilist.end());
    }

    void assign(size_t n, T const &val) {
        clear();
        _uninit_assign(n, val);
    }
}

emplace_back()和emplace_front()

emplace_back()函数的作用是构造一个新的链表节点并将它插入到链表的末尾。类似于Vector中的实现，这里同样使用了变长参数模板：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <class ...Args>
    T &emplace_back(Args &&...args) {
        ListNode *node = newNode();
        ListNode *prev = m_dummy.m_prev;

        prev->m_next = node;
        node->m_prev = prev;
        node->m_next = &m_dummy;

        std::construct_at(&node->value(), std::forward<Args>(args)...);
        m_dummy.m_prev = node;

        ++m_size;

        return node->value();
    }
}

emplace_front()函数的实现与emplace_back()基本一致，唯一的区别在于它会把新构造的节点插入到链表头：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <class ...Args>
    T &emplace_front(Args &&...args) {
        ListNode *node = newNode();
        ListNode *next = m_dummy.m_next;

        next->m_prev = node;
        node->m_next = next;
        node->m_prev = &m_dummy;

        std::construct_at(&node->value(), std::forward<Args>(args)...);
        m_dummy.m_next = node;

        ++m_size;

        return node->value();
    }
}

push_back()和push_front()

在emplace_back()和emplace_front()的基础上就可以很容易地实现push_back()和push_front()两个函数：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    void push_back(T const &val) {
        emplace_back(val);
    }

    void push_back(T &&val) {
        emplace_back(std::move(val));
    }

    void push_front(T const &val) {
        emplace_front(val);
    }

    void push_front(T &&val) { // don't repeat yourself (DRY)
        emplace_front(std::move(val));
    }
}

erase()

erase()函数的作用是根据迭代器pos的位置清除指定的节点：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    iterator erase(const_iterator pos) noexcept {
        ListNode *node = const_cast<ListNode *>(pos.m_curr);

        auto next = node->m_next;
        auto prev = node->m_prev;

        prev->m_next = next;
        next->m_prev = prev;

        std::destroy_at(&node->value());
        deleteNode(node);

        --m_size;

        return iterator{next};
    }
}

除此之外，我们再实现一个针对迭代范围的版本，它会清除指定范围内的所有节点：



1
2
3
4
5
6
7
8
9
10
11
12

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    iterator erase(const_iterator first, const_iterator last) noexcept {
        while (first != last) {
            first = erase(first);
        }

        return iterator(first);
    }
}

pop_front()和pop_back()

在erase()函数的基础上我们只需要把begin()和end()作为输入参数就可以实现pop_front()和pop_back()：



1
2
3
4
5
6
7
8
9
10
11
12

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    void pop_front() noexcept {
        erase(begin());
    }

    void pop_back() noexcept {
        erase(std::prev(end()));
    }
}

remove()

remove()函数的作用类似于erase()，不过它是根据值val来判断是否需要删除节点。remove()函数会删除链表中所有值为val的节点：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    size_t remove(T const &val) noexcept {
        auto first = begin();
        auto last = begin();

        size_t count = 0;
        while (first != last) {
            if (*first == val) {
                first = erase(first);
                ++count;
            } else {
                ++first;
            }
        }

        return count;
    }
}

与之类似的还有remove_if()，它接收一个函数对象pred作为参数。当pred在某个节点处进行调用并返回true时，remove_if()会将该节点删除：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <class Pred>
    size_t remove_if(Pred &&pred) noexcept {
        auto first = begin();
        auto last = begin();

        size_t count = 0;
        while (first != last) {
            if (pred(*first)) {
                first = erase(first);
                ++count;
            } else {
                ++first;
            }
        }

        return count;
    }
}

emplace()

emplace()函数有着和erase()相反的作用，它可以在迭代器pos位置创建一个新的节点。类似于emplace_back()和emplace_front()，emplace()同样使用了变长参数模板来实现：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <class ...Args>
    iterator emplace(const_iterator pos, Args &&...args) {
        ListNode *curr = newNode();

        ListNode *next = const_cast<ListNode *>(pos.m_curr);
        ListNode *prev = next->m_prev;

        curr->m_prev = prev;
        prev->m_next = curr;
        curr->m_next = next;
        next->m_prev = curr;

        std::construct_at(&curr->value(), std::forward<Args>(args)...);

        ++m_size;

        return iterator{curr};
    }
}

insert()

在emplace()函数的基础上我们可以实现insert()函数，它用来将值val插入到pos位置上：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    iterator insert(const_iterator pos, const T &val) {
        return emplace(pos, val);
    }

    iterator insert(const_iterator pos, T &&val) {
        return emplace(pos, std::move(val));
    }

    iterator insert(const_iterator pos, size_t n, T const &val) {
        auto orig = pos;
        bool had_orig = false;

        while (n) {
            pos = emplace(pos, val);
            if (!had_orig) {
                had_orig = true;
                orig = pos;
            }

            ++pos;
            --n;
        }

        return iterator(orig);
    }
}

除了上面三种标准用法外，我们还可以针对迭代器输入进行单独处理：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    template <std::input_iterator InputIt>
    iterator insert(const_iterator pos, InputIt first, InputIt last) {
        auto orig = pos;
        bool had_orig = false;

        while (first != last) {
            pos = emplace(pos, *first);
            if (!had_orig) {
                had_orig = true;
                orig = pos;
            }

            ++pos;
            ++first;
        }
        return iterator(orig);
    }

    iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
        return insert(pos, ilist.begin(), ilist.end());
    }
}

splice()

splice()函数可以把另一个List插入到指定位置上：



1
2
3
4
5
6
7
8

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    void splice(const_iterator pos, List &&that) {
        insert(pos, std::make_move_iterator(that.begin()), std::make_move_iterator(that.end()));
    }
}

其它函数

List中有一些获取链表信息的函数，这里简单汇总一下：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    size_t size() const noexcept {
        return m_size;
    }

    static constexpr size_t max_size() noexcept {
        return std::numeric_limits<size_t>::max();
    }

    Alloc get_allocator() const {
        return m_alloc;
    }
}

不同List对象之间的比较我们则可以利用标准库的相关函数来实现：



1
2
3
4
5
6
7
8
9
10
11
12

 
template <class T, class Alloc = std::allocator<T>>
struct List {
    ...
public:
    bool operator==(List const &that) noexcept {
        return std::equal(begin(), end(), that.begin(), that.end());
    }

    auto operator<=>(List const &that) noexcept {
        return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
    }
}

完整实现

总结一下，整个List的代码可以参考如下：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639

 
#pragma once

#include <cstddef>
#include <iterator>
#include <memory>
#include <limits>
#include <stdexcept>
#include <utility>
#include <compare>
#include <initializer_list>

#ifdef NDEBUG
#define DEBUG_INIT_DEADBEAF(T)
#else
#define DEBUG_INIT_DEADBEAF(T) {(T *)0xdeadbeaf}
#endif

template <class T>
struct ListBaseNode {
    ListBaseNode *m_next DEBUG_INIT_DEADBEAF(ListBaseNode);
    ListBaseNode *m_prev DEBUG_INIT_DEADBEAF(ListBaseNode);

    inline T &value();
    inline T const &value() const;
};

template <class T>
struct ListValueNode : ListBaseNode<T> {
    union {
        T m_value;
    };
};

template <class T>
inline T &ListBaseNode<T>::value() {
    return static_cast<ListValueNode<T> &>(*this).m_value;
}

template <class T>
inline T const &ListBaseNode<T>::value() const {
    return static_cast<ListValueNode<T> const &>(*this).m_value;
}

template <class T, class Alloc = std::allocator<T>>
struct List {
    using value_type        = T;
    using allocator_type    = Alloc;
    using size_type         = size_t;
    using difference_type   = ptrdiff_t;
    using pointer           = T *;
    using const_pointer     = T const *;
    using reference         = T &;
    using const_reference   = T const &;

private:
    using ListNode  = ListBaseNode<T>;
    using AllocNode = std::allocator_traits<Alloc>::template rebind_alloc<ListValueNode<T>>;

    ListNode m_dummy;
    size_t m_size;
    [[no_unique_address]] Alloc m_alloc;

    ListNode *newNode() {
        return AllocNode{m_alloc}.allocate(1);
    }

    void deleteNode(ListNode *node) noexcept {
        AllocNode{m_alloc}.deallocate(static_cast<ListValueNode<T> *>(node), 1);
    }

public:
    List() noexcept {
        m_size = 0;
        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
    }

    explicit List(Alloc const &alloc) noexcept : m_alloc(alloc) {
        m_size = 0;
        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
    }

    List(List &&that) : m_alloc(std::move(that.m_alloc)) {
        _uninit_move_assign(std::move(that));
    }

    List(List &&that, Alloc const &alloc) : m_alloc(alloc) {
        _uninit_move_assign(std::move(that));
    }

    List &operator=(List &&that) {
        m_alloc = std::move(that.m_alloc);
        clear();
        _uninit_move_assign(std::move(that));

        return *this;
    }

private:
    void _uninit_move_assign(List &&that) {
        auto prev = that.m_dummy.m_prev;
        auto next = that.m_dummy.m_next;

        prev->m_next = &m_dummy;
        next->m_prev = &m_dummy;

        m_dummy = that.m_dummy;
        that.m_dummy.m_prev = that.m_dummy.m_next = &that.m_dummy;

        m_size = that.m_size;
        that.m_size = 0;
    }

public:
    List(List const &that) : m_alloc(that.m_alloc) {
        _uninit_assign(that.cbegin(), that.cend());
    }

    List(List const &that, Alloc const &alloc) : m_alloc(alloc) {
        _uninit_assign(that.cbegin(), that.cend());
    }

    List &operator=(List const &that) {
        assign(that.cbegin(), that.cend());

        return *this;
    }

    bool empty() noexcept {
        return m_dummy.m_prev == m_dummy.m_next;
    }

    T &front() noexcept {
        return m_dummy.m_next->value();
    }

    T &back() noexcept {
        return m_dummy.m_prev->value();
    }

    T const &front() const noexcept {
        return m_dummy.m_next->value();
    }

    T const &back() const noexcept {
        return m_dummy.m_prev->value();
    }

    explicit List(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        _uninit_assign(n);
    }

    List(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        _uninit_assign(n, val);
    }

    template <std::input_iterator InputIt>
    List(InputIt first, InputIt last, Alloc const &alloc = Alloc()) {
        _uninit_assign(first, last);
    }

    List(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
    : List(ilist.begin(), ilist.end(), alloc) {}

    List &operator=(std::initializer_list<T> ilist) {
        assign(ilist);
        return *this;
    }

private:
    template <std::input_iterator InputIt>
    void _uninit_assign(InputIt first, InputIt last) {
        m_size = 0;
        ListNode *prev = &m_dummy;

        while (first != last) {
            ListNode *node = newNode();

            prev->m_next = node;
            node->m_prev = prev;

            std::construct_at(&node->value(), *first);
            prev = node;

            ++first;
            ++m_size;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }

    void _uninit_assign(size_t n, T const &val) {
        m_size = n;
        ListNode *prev = &m_dummy;

        while (n) {
            ListNode *node = newNode();

            prev->m_next = node;
            node->m_prev = prev;

            std::construct_at(&node->value(), val);
            prev = node;

            --n;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }

    void _uninit_assign(size_t n) {
        m_size = n;
        ListNode *prev = &m_dummy;

        while (n) {
            ListNode *node = newNode();

            prev->m_next = node;
            node->m_prev = prev;

            std::construct_at(&node->value());
            prev = node;

            --n;
        }

        m_dummy.m_prev = prev;
        prev->m_next = &m_dummy;
    }

public:
    size_t size() const noexcept {
        return m_size;
    }

    static constexpr size_t max_size() noexcept {
        return std::numeric_limits<size_t>::max();
    }

    template <std::input_iterator InputIt>
    void assign(InputIt first, InputIt last) {
        clear();
        _uninit_assign(first, last);
    }

    void assign(std::initializer_list<T> ilist) {
        clear();
        _uninit_assign(ilist.begin(), ilist.end());
    }

    void assign(size_t n, T const &val) {
        clear();
        _uninit_assign(n, val);
    }

    void push_back(T const &val) {
        emplace_back(val);
    }

    void push_back(T &&val) {
        emplace_back(std::move(val));
    }

    void push_front(T const &val) {
        emplace_front(val);
    }

    void push_front(T &&val) { // don't repeat yourself (DRY)
        emplace_front(std::move(val));
    }

    template <class ...Args>
    T &emplace_back(Args &&...args) {
        ListNode *node = newNode();
        ListNode *prev = m_dummy.m_prev;

        prev->m_next = node;
        node->m_prev = prev;
        node->m_next = &m_dummy;

        std::construct_at(&node->value(), std::forward<Args>(args)...);
        m_dummy.m_prev = node;

        ++m_size;

        return node->value();
    }

    template <class ...Args>
    T &emplace_front(Args &&...args) {
        ListNode *node = newNode();
        ListNode *next = m_dummy.m_next;

        next->m_prev = node;
        node->m_next = next;
        node->m_prev = &m_dummy;

        std::construct_at(&node->value(), std::forward<Args>(args)...);
        m_dummy.m_next = node;

        ++m_size;

        return node->value();
    }

    ~List() noexcept {
        clear();
    }

    void clear() noexcept {
        ListNode *curr = m_dummy.m_next;

        while (curr != &m_dummy) {
            std::destroy_at(&curr->value());
            auto next = curr->m_next;
            deleteNode(curr);
            curr = next;
        }

        m_dummy.m_prev = m_dummy.m_next = &m_dummy;
        m_size = 0;
    }

    struct iterator {
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T *;
        using reference         = T &;

    private:
        ListNode *m_curr;

        friend List;

        explicit iterator(ListNode *curr) noexcept
        : m_curr(curr) {}

    public:
        iterator() = default;

        iterator &operator++() noexcept { // ++iterator
            m_curr = m_curr->m_next;
            return *this;
        }

        iterator operator++(int) noexcept { // iterator++
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        iterator &operator--() noexcept { // --iterator
            m_curr = m_curr->m_prev;
            return *this;
        }

        iterator operator--(int) noexcept { // iterator--
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        T &operator*() const noexcept {
            return m_curr->value();
        }

        bool operator!=(iterator const &that) const noexcept {
            return m_curr != that.m_curr;
        }

        bool operator==(iterator const &that) const noexcept {
            return !(*this != that);
        }
    };

    struct const_iterator {
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T const *;
        using reference         = T const &;

    private:
        ListNode const *m_curr;

        friend List;

        explicit const_iterator(ListNode const *curr) noexcept
        : m_curr(curr) {}

    public:
        const_iterator() = default;

        const_iterator(iterator that) noexcept : m_curr(that.m_curr) {
        }

        explicit operator iterator() noexcept {
            return iterator{const_cast<ListNode *>(m_curr)};
        }

        const_iterator &operator++() noexcept { // ++iterator
            m_curr = m_curr->m_next;
            return *this;
        }

        const_iterator operator++(int) noexcept { // iterator++
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        const_iterator &operator--() noexcept { // --iterator
            m_curr = m_curr->m_prev;
            return *this;
        }

        const_iterator operator--(int) noexcept { // iterator--
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        T const &operator*() const noexcept {
            return m_curr->value();
        }

        bool operator!=(const_iterator const &that) const noexcept {
            return m_curr != that.m_curr;
        }

        bool operator==(const_iterator const &that) const noexcept {
            return !(*this != that);
        }
    };

    iterator begin() noexcept {
        return iterator{m_dummy.m_next};
    }

    iterator end() noexcept {
        return iterator{&m_dummy};
    }

    const_iterator cbegin() const noexcept {
        return const_iterator{m_dummy.m_next};
    }

    const_iterator cend() const noexcept {
        return const_iterator{&m_dummy};
    }

    const_iterator begin() const noexcept {
        return cbegin();
    }

    const_iterator end() const noexcept {
        return cend();
    }

    using reverse_iterator = std::reverse_iterator<iterator>;
    using reverse_const_iterator = std::reverse_iterator<const_iterator>;

    reverse_iterator rbegin() noexcept {
        return std::make_reverse_iterator(end());
    }

    reverse_iterator rend() noexcept {
        return std::make_reverse_iterator(begin());
    }

    reverse_const_iterator crbegin() const noexcept {
        return std::make_reverse_iterator(cend());
    }

    reverse_const_iterator crend() const noexcept {
        return std::make_reverse_iterator(cbegin());
    }

    reverse_const_iterator rbegin() const noexcept {
        return crbegin();
    }

    reverse_const_iterator rend() const noexcept {
        return crend();
    }

    iterator erase(const_iterator pos) noexcept {
        ListNode *node = const_cast<ListNode *>(pos.m_curr);

        auto next = node->m_next;
        auto prev = node->m_prev;

        prev->m_next = next;
        next->m_prev = prev;

        std::destroy_at(&node->value());
        deleteNode(node);

        --m_size;

        return iterator{next};
    }

    iterator erase(const_iterator first, const_iterator last) noexcept {
        while (first != last) {
            first = erase(first);
        }

        return iterator(first);
    }

    void pop_front() noexcept {
        erase(begin());
    }

    void pop_back() noexcept {
        erase(std::prev(end()));
    }

    size_t remove(T const &val) noexcept {
        auto first = begin();
        auto last = begin();

        size_t count = 0;
        while (first != last) {
            if (*first == val) {
                first = erase(first);
                ++count;
            } else {
                ++first;
            }
        }

        return count;
    }

    template <class Pred>
    size_t remove_if(Pred &&pred) noexcept {
        auto first = begin();
        auto last = begin();

        size_t count = 0;

        while (first != last) {
            if (pred(*first)) {
                first = erase(first);
                ++count;
            } else {
                ++first;
            }
        }

        return count;
    }

    template <class ...Args>
    iterator emplace(const_iterator pos, Args &&...args) {
        ListNode *curr = newNode();

        ListNode *next = const_cast<ListNode *>(pos.m_curr);
        ListNode *prev = next->m_prev;

        curr->m_prev = prev;
        prev->m_next = curr;
        curr->m_next = next;
        next->m_prev = curr;

        std::construct_at(&curr->value(), std::forward<Args>(args)...);

        ++m_size;

        return iterator{curr};
    }

    iterator insert(const_iterator pos, const T &val) {
        return emplace(pos, val);
    }

    iterator insert(const_iterator pos, T &&val) {
        return emplace(pos, std::move(val));
    }

    iterator insert(const_iterator pos, size_t n, T const &val) {
        auto orig = pos;
        bool had_orig = false;

        while (n) {
            pos = emplace(pos, val);
            if (!had_orig) {
                had_orig = true;
                orig = pos;
            }
            ++pos;
            --n;
        }

        return iterator(orig);
    }

    template <std::input_iterator InputIt>
    iterator insert(const_iterator pos, InputIt first, InputIt last) {
        auto orig = pos;
        bool had_orig = false;

        while (first != last) {
            pos = emplace(pos, *first);
            if (!had_orig) {
                had_orig = true;
                orig = pos;
            }
            ++pos;
            ++first;
        }

        return iterator(orig);
    }

    iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
        return insert(pos, ilist.begin(), ilist.end());
    }

    void splice(const_iterator pos, List &&that) {
        insert(pos, std::make_move_iterator(that.begin()), std::make_move_iterator(that.end()));
    }

    Alloc get_allocator() const {
        return m_alloc;
    }

    bool operator==(List const &that) noexcept {
        return std::equal(begin(), end(), that.begin(), that.end());
    }

    auto operator<=>(List const &that) noexcept {
        return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
    }
};

Reference