为什么C++不提供先进先出的单向链表？

Question

在C++标准库中，list是双向链表； forward_list是单链表，但只支持后进先出。

然而，先进先出单链表因其比其他类列表容器（forward_list除外）低space开销而被广泛使用。所以我想知道：

为什么C++不提供先进先出单向链表？

Answer 1

您可以轻松地自己创建一个，方法是在 forward_list 的基础上增加一个前端迭代器来实现 back() 和 push_back():

template<class T>
struct fifo_list {
    std::forward_list<T> base;
    std::forward_list<T>::iterator before_end = base.before_begin();
    fifo_list(fifo_list const& other) { for (auto t : other.base) push_back(t); }
    fifo_list(fifo_list&&) = default;
    auto front() { return base.front(); }
    void pop_front() { base.pop_front(); }
    auto back() { return *before_end; }
    void push_back(T t) { before_end = base.insert_after(before_end, t); }
};

这可以与 std::queue 适配器一起使用。

与维护 before_end 迭代器相关的开销可能是此工具（back 和 push_back）尚未包含在 forward_list 中的原因。

为什么C++不提供先进先出的单向链表？

Why does C++ not provide a First-In-First-Out singly-linked list?

c++

standards

containers

stl

c++20