Design Rationale


devector is a hybrid of the standard vector and deque containers, as well as the small_vector of Boost.Container. It offers cheap (amortized constant time) insertion at both the front and back ends, while also providing the regular features of std::vector, in particular the contiguous underlying memory. In contrast to the standard vector, however, devector offers greater control over its internals. Like small_vector, it can store elements internally without dynamically allocating memory.

Through a policy template argument, it's possible to add small buffer optimization to devector: The specified number of elements will be stored inline with the internals, without requiring additional heap allocation. If the size of the devector exceeds the small buffer size, it automatically switches to an allocated storage.

Furthermore, through another policy template argument, it's also possible to change how the devector grows its storage, providing explicit control over the reallocation strategy and consistent behavior across different platforms.

To accommodate high performance requirements, devector offers (potentially) unsafe, less encapsulating methods: such methods can avoid unnecessary checks or initialization, but can trigger undefined behavior if their contract is broken.

The devector class template intends to be a drop in replacement of std::vector. However, to keep its size slim (16 bytes on 32 bit, 24 bytes on a typical 64 bit architecture), its size_type is defined as unsigned int which reduces max_size() to UINT_MAX.

In general, devector uses move_if_noexcept whenever necessary, offering strong exception guarantees. devector implements the NAD (Not A Defect) resolution of LWG Issue 526 (Is it undefined if a function in the standard changes in parameters?).

batch_deque is very similar to the standard deque, with a slight twist. It lets you specify its segment size: The size of the contiguous memory segments it uses to store its elements. This provides a consistent layout across platforms, and lets you iterate over the segments with batch operations.

batch_deque makes a good candidate for a container of cached or reusable elements, because it provides reference stability while inserting at either end with amortized constant complexity. Reference stability also makes it possible to store the elements of an intrusive container.