Sidetrack
It has been two years since I wrote an educational blog. I've been inactive in the CP community recently as I've shifted my focus to internships. Recently, I observed some interesting behaviour with std::queue while profiling an application during my internship, which led me to writing this blog.
Most of the images below are taken from the C++ standard https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf
Queues and stacks
Queues and stacks do not actually provide any new implementations... They are just wrappers around a container (which is std::deque) by default.
This means that if you use the default Container template of std::stack and std::queue, it will be as slow as a std::deque. Now, let us see why std::deque is slow.
Deque
Below is a brief implementation of deque. (You may refer to the section below for exact implementations)
template<typename T>
struct SimpleDeque {
static constexpr size_t BLOCK_BYTES = 512;
static constexpr size_t BLOCK_SIZE = BLOCK_BYTES / sizeof(T);
T** map = nullptr;
size_t map_size = 0;
size_t n = 0;
void grow_map() {
size_t new_size = map_size ? map_size * 2 : 2;
T** new_map = new T*[new_size]{};
for (size_t i = 0; i < map_size; i++)
new_map[i] = map[i];
delete[] map;
map = new_map;
map_size = new_size;
}
SimpleDeque() : map(new T*[2]{}), map_size(2), n(0) {}
void push_back(const T& value) {
size_t block = n / BLOCK_SIZE;
size_t offset = n % BLOCK_SIZE;
if (block >= map_size)
grow_map();
if (offset == 0)
map[block] = new T[BLOCK_SIZE];
map[block][offset] = value;
++n;
}
T& operator[](size_t i) {
return map[i / BLOCK_SIZE]
[i % BLOCK_SIZE];
}
};
Essentially, the deque stores an array of tiny blocks. In GCC, each tiny block is $$$512$$$ bytes, but it can be different in other compilers (see https://codeforces.me/blog/entry/135332?#comment-1210774).
