Почему 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 adapter.

Служебные расходы, связанные с обслуживанием итератора before_end, по-видимому, являются причиной, по которой это средство (back и push_back) уже не включено в forward_list.