4 ms·
Is there any benefit to using virtual_vec as opposed to a std::deque then? It guarantees constant time pushes to the back and constant time random element acces
by nanidin 5y ago
Is there any benefit to using virtual_vec as opposed to a std::deque then? It guarantees constant time pushes to the back and constant time random element access via operator[][0].
I think the case for std::vector::reserve() is when you know you are about to add N elements via push_back(), you call reserve() with the appropriate size to ensure there is only one reallocation caused by that addition of N elements.
[0] https://www.cplusplus.com/reference/deque/deque/operator[]/ https://www.cplusplus.com/reference/deque/deque/operator[]/
- MauranKilom 5y agostd::dequeue is useless from a practical/portability perspective. MSVC allocates items in 16 byte chunks (as in, one allocation per item if sizeof(T) > 8). This will not change due to binary compatibility. From a theoretical perspective I agree with you though - having chunked allocations is going to be significantly better, and using iterators instead of raw pointers you can also avoid any trouble that might result from non-contiguity (e.g. trying to subtract two pointers - it will work just fine using the iterators).
- beached_whale 5y agolibc++ uses 4kb
- _4r6j 5y agoiterating over vectors (of trivial types that aren't pointers) is generally going to be faster since the memory is contiguous. deque is implemented with chunks i believe? loading in new chunk could be cache eviction.
- nanidin 5y agoAha, so the contiguity of the actual memory pages must not be what is used for prefetching by the MMU, instead it is the contiguity of the virtual address space? I was thrown for a bit of a loop working through virtual vs actual memory addresses and how this works under the hood, but it makes more sense now. In that case then virtual_vec would be better than std::deque in terms of iterating over the contained data in order.