3 ms·
There are weasel words in the standard that let implementations still be pretty inefficient. The problem is that memory reallocation is a leaky abstraction, and
by kabdib 12y ago
There are weasel words in the standard that let implementations still be pretty inefficient. The problem is that memory reallocation is a leaky abstraction, and an interface that doesn't make guarantees about memory behavior can't be relied upon at scale.
The implementation of std::deque I just read uses a circular queue, resized to a power of two upon growth. It would exhibit the same bad performance as std::vector.
- yoklov 12y agoAre you sure? You're not allowed to invalidate iterators or pointers to elements in a deque, so it shouldn't be reallocating memory (aside from its underlying map of nodes, which will need to grow very rarely). Libstdc++ describes how it's implemented here: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h#L650-L733 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Libc++ doesn't have as descriptive a comment but it's impemented basically the same way here https://github.com/llvm-mirror/libcxx/blob/master/include/deque https://github.com/llvm-mirror/libcxx/blob/master/include/de...
- nly 12y agoYou might not want to use deque because of how much memory it can use while still small, e.g. libc++s implementation uses a 4KiB page: http://rextester.com/VIB96468 http://rextester.com/VIB96468 In the GNU stdlibc++ implementation the object itself is pretty large (and they use a page size of 512 bytes): http://rextester.com/RHYKB83240 http://rextester.com/RHYKB83240