3 ms·
I believe a std::deque is an rb-tree (radix binary tree), which suffers from insertions in the middle. An rrb-tree solves this problem by being relaxed, which
by proverbialbunny 7y ago
I believe a std::deque is an rb-tree (radix binary tree), which suffers from insertions in the middle.
An rrb-tree solves this problem by being relaxed, which means allowing for having random empty places in the cache line sized arrays within the structure. This way insertion is effectively O(1).
Modern languages implement these, like Scala, but C++ has been around for a while, so it's the stl is not the fastest in a few ways. std::deque is one of them. Another example, std::sort isn't the fastest, I believe.
- kadoban 7y agoI think the typical implementation of a std::deque is actually something like a vector of pointers to vector of pointers to T. (except they can't be std::vector exactly, because then you'd only get amortized bounds on pushes).