3 ms·
std::deque is odd in that there's no std size of the blocks used. We have libstdc++ that is about 512bytes, libc++ at 4096bytes, and MS STL at around 64bytes.
by beached_whale 5y ago
std::deque is odd in that there's no std size of the blocks used. We have libstdc++ that is about 512bytes, libc++ at 4096bytes, and MS STL at around 64bytes. This leaves a bunch of room for optimizing for certain cases. Smaller is more insert friendly, larger more op[] reading friendly. But push_front after a pop_front should be O(1) on all of them. Otherwise it is moving/copying data to make room. Another nice/similar data structure is something like Boosts devector that adds a pointer to vector for the front capacity.
- nly 5y agoBoosts deque let's you decide the the block size.
- brandmeyer 5y ago> MS STL at around 64bytes. Citation? Are you sure it isn't 64 size-independent elements?
- MauranKilom 5y agoIt's worse actually. The MSVC STL uses 16 byte (or however large your element is, if greater) chunks. Source: https://github.com/microsoft/STL/blob/main/stl/inc/deque#L561 https://github.com/microsoft/STL/blob/main/stl/inc/deque#L56... They have made clear that this won't be changed, for ABI stability reasons. That makes std::dequeue basically unusable in a portable context. In virtually any situation, "allocate each element separately" and "allocate elements in 4k chunks" are on opposite ends of the performance spectrum.
- brandmeyer 5y agoThat is quite unfortunate, and I freely admit that I'm unfamiliar with MSVC's current quirks. > They have made clear that this won't be changed, for ABI stability reasons. Also unfortunate. Once upon a time, users had to be extra careful to control which version of the runtime DLL their program transitively linked to since MS would issue a new ABI-breaking version with every major compiler release. Sounds like they got ABI stability religion just in time to lock in some unfortunate decisions.
- beached_whale 5y agoThanks, I remembered incorrectly.