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

Question

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

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

为什么 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。