C++11 STL container that supports move-only types and has O(1) write-access to beginning and end

Question

I am developing an application where I need to queue up some move-only types and I need fast write-access to the beginning and the end of the container (mainly adding elements fast).

At first glance I wanted to use std::deque<T> but it requires that T is copy-constructible, so it won't do the job.

I am now considering std::vector, but I'm worried that adding elements to the beginning of the vector would be really slow because of reallocating all the stuff.

Any suggestions on such container?

Note on operations I need (on std::deque):

• emplace_back
• emplace_front
• pop_front
• empty
• front

These are the operations used currently (my implementation now uses std::shared_ptr to make move-only types copyable)

The exact type I need to queue is the move-only version of std::function<void()>. If I try the move-only version with std::deque I get the following compiler errors (clang++):

error: use of deleted function ‘std::packaged_task<_Res(_ArgTypes ...)>::packaged_task(const std::packaged_task<_Res(_ArgTypes ...)>&) [with _Res = void; _ArgTypes = {}]’ In file included from /home/superuser/Desktop/thread_pool/thread_pool.hpp:32:0, from /home/superuser/Desktop/thread_pool/test.cpp:1: /usr/include/c++/6/future:1513:7: note: declared here packaged_task(const packaged_task&) = delete;

Note that you see std::packaged_task, because it is moved into a lambda wrapped by std::function<void()>.

Answer 1

This is a classic example of why a [MCVE] is so useful.

std::function<void()> fun = std::move(queue.front());

The above won't compile with a non-copyable content in the queue. But the queue works fine. std::deque solves your problem.

std::function requires its contents to be copyable. Even if you never move it, it requires it be copyable. std::function uses type erasure, so "how to copy" the contents is stored when you store something in it.

Here is a move-only std::function that does not do the small buffer optimization I wrote on SO two years ago.

Today I would write it differently. I would split the type erasure from the storage, and write a separate SBO storage type, then join them together to write task<Sig>.

Amusingly, packaged_task<void(Args...)> is a type erased SBO move-only wrapper for packaged_task<R(Args...)>. But it does much more, so I would avoid using it.

Now, the rules for std containers with regards to the requirements for their content have varied, with the standard regularly getting more liberal. At one point a bunch of requirements where placed on types even if it wasn't used; the current standard states that these requirements are on a per-method basis. Many compilers enforced those more liberal requirements before the standard moved (because there was little need to be strict, the standard did not demand it), so even in compilers prior to the liberalization it wasn't a problem. I am uncertain if this liberalization occurred in std::deque by C++11 or not; this is, however, an example of "if it works in your compiler, use it, because future compilers are going to support it".