Created by potrace 1.15, written by Peter Selinger 2001-2017 Bo's Blog

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

 
  • Nov 18, 2023

动手实现C++ STL容器。本节介绍std::list的常见用法和实现。

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的一些常用用法如下：

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

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

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模板来实现：

#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来表示一个携带数据的链表节点：

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>类型的内存分配器，这可以方便我们处理节点。

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的元信息：

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()进行处理：

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的前后指针都指向自身。

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()：

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

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

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()进行初始化：

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()：

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()完成初始化：

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()：

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

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类：

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--、解引用*、以及比较==!=等操作：

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的迭代器行为：

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处理常量迭代的情况：

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()函数会依次访问链表的每个节点，然后清除节点数据并释放节点自身的内存：

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()函数实现的：

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

assign()

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

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中的实现，这里同样使用了变长参数模板：

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()基本一致，唯一的区别在于它会把新构造的节点插入到链表头：

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()两个函数：

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的位置清除指定的节点：

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

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

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()：

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的节点：

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()会将该节点删除：

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()同样使用了变长参数模板来实现：

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位置上：

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

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

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插入到指定位置上：

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中有一些获取链表信息的函数，这里简单汇总一下：

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对象之间的比较我们则可以利用标准库的相关函数来实现：

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的代码可以参考如下：

#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

Search