Is there a container similar to `std::deque` but with custom block size and better performance?

Question

The cons of std::deque are slower performance compared to std::vector when accessing elements in random positions, and the fact that the memory blocks where data are stored have a predefined fixed size.

Are there alternative (even out of the STL) container classes that allow to:

• Set the block size for all blocks in the constructor, or
• Set different block sizes for each block.
• Prevent most indexed accesses from having to perform two pointer dereferences; e.g. once I access an element in a certain memory block, the following accesses in the same memory block should have a std::vector like performance.

Note: I am interested in the performance related to the access to the elements, not their insertion/removal.

Answer 1

The block size in boost::container::deque can be configured at the compile time. See the example in the official documentation:

#include <boost/container/deque.hpp>

using namespace boost::container;

constexpr unsigned n_bytes = 1024u;
using my_block_size = deque_options<block_bytes<n_bytes>>::type;
using my_deque = deque<int, void, my_block_size>;
static_assert(my_deque::get_block_size() == n_bytes/sizeof(int));

Answer 2

Please check my library at GitHub: https://github.com/slavenf/sfl-library

This library offers container sfl::segmented_vector. This container is similar to std::deque. The size of blocks (I call them segments) is specified at the compile time as a template parameter.