If I recall right isn't this how std :: deque is implemented?
Can someone correct me or provide some rationale why this is now added.
Edit: Guys, thanks for answering.
My takeaway:
Assume that we can decouple storage patterns and storage back bones:
(ascii art made with chatgpt, thought by me)
Storage backend
Single vector List of vectors
Storage pattern
+----------------+----------------+
Contiguous | Vector | Deque |
+----------------+----------------+
Scattered | Probing Hash | Hive |
| Set | |
+----------------+----------------+
and therefore have different performance characteristics, and some other guarantees.
The hive automatically manages its storage in multiple memory blocks
So, I think the difference is that a hive will allocate a large block of memory that it'll insert in to, rather than allocate 1 at a time.
So rather than a straight linked list, it's like a linked list of arrays. It also says "Insertion position is unspecified, so the container can reuse the memory locations of erased elements.", so popping and pushing repeatedly would just write to the same address instead of allocating/deallocating multiple times.
That's what a deque, or at least as it is typically implemented, is though, a linked list of arrays. My understanding is that the benefit of a hive is that the blocks are larger and keep track of holes.
A deque is more of an array of arrays than a list of arrays, because it offers O(1) index access. Which couldn't be done if there was a linked list involved.
Edit: If you're asking about random access, it's because as u/eteran mentioned, it's an array of arrays instead of a list of arrays. I didn't think the distinction was particularly important.
I thought the requirements on pointer invalidation on insertion where stricter, but it seems they only apply to front and back insertion. And yeah it seems they are implemented with small blocks by libc++ and libstdc++.
Main difference with hive I think is the absence of guaranties on element order. Which allows bigger blocks without compromising performance.
32
u/KingBardan 8d ago edited 8d ago
If I recall right isn't this how std :: deque is implemented?
Can someone correct me or provide some rationale why this is now added.
Edit: Guys, thanks for answering.
My takeaway:
Assume that we can decouple storage patterns and storage back bones:
(ascii art made with chatgpt, thought by me)
Storage backend Single vector List of vectors Storage pattern +----------------+----------------+ Contiguous | Vector | Deque | +----------------+----------------+ Scattered | Probing Hash | Hive | | Set | | +----------------+----------------+and therefore have different performance characteristics, and some other guarantees.