4 ms·
> std::deque has O(n) insertion/deletion in the middle I'm curious to know from approximately which n this is a problem though. It can be easy to make somethin
by temac 7y ago
> std::deque has O(n) insertion/deletion in the middle
I'm curious to know from approximately which n this is a problem though. It can be easy to make something with a better O complexity that is actually slower for what computers can actually handle.
edit: nevermind, I thought deque was more "smart" than it is but it needs to move all elements when inserting / deleting in the middle, so it won't have a great constant factor.
- proverbialbunny 7y agoI 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).