4 ms·
I much prefer deques to linked lists when I need O(1) push/pop but still want to keep some semblance of cache locality. Although you can't splice two deques tog
by elteto 4y ago
I much prefer deques to linked lists when I need O(1) push/pop but still want to keep some semblance of cache locality. Although you can't splice two deques together as easily as two linked lists.
Sadly, you can't really control the block size in C++'s std::deque so you can't communicate useful information to the library about your use case. I think MSVC allocates such a small block that it is effectively a linked list.
- intrepidhero 4y agoHow does a dequeue improve the situation with cache locality versus a linked list?
- blibble 4y agoit's typically implemented as an array (e.g. circular buffer)
- zwkrt 4y agoMosty dequeues are implemented under the hood with arrays. A linked list usually requires a heap allocation for each element. This is speaking in generalities though, since you could have an “alternatively implemented dequeue or a linked list entirely on the stack.
- klyrs 4y agoIt depends on the implementation. Python's deque, for example, is implemented as a two-level data structure; a circularly linked list of blocks. If you've got page-sized blocks, then your deque can be sufficiently local for most cases. It introduces a little extra logic, and you'll want to keep around a spare block to prevent thrashing memory if you repeatedly push/pop at the block boundary, but it's often worth the pain if the data structure is anywhere near a hot loop.
- Shorel 4y agoIt is usually implemented as linked arrays. For example, arrays of 16 or 64 elements, if it grows over that size, new arrays or vectors are used underneath. Two consecutive elements are probably in the same array, and that helps with cache locality.
- layer8 4y agoNote that a deque in general is an ADT that isn’t necessarily implemented in the way std::deque commonly is. A deque can be implemented as a linked list.
- woojoo666 4y agoI feel like to compare linked lists and dequeues, you would have to give a specific implementation of a dequeue
- Jtsummers 4y agoCorrect, deques are abstract data types and you can implement them multiple ways, including using linked lists or growable arrays/vectors. So they aren't directly comparable to linked lists since under the hood they can be implemented with linked lists (or doubly linked lists at least). You could compare the performance of different deque implementations, though.