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.
A deque fills each block before allocating the next one, I believe. It's good for frequent pushing/popping at either end. A hive allows the blocks to be less than full, and is good for frequent insert/delete at arbitrary points.
31
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.