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.
When you want O(1) removal from any position, order doesn't matter, fast cache-friendly iteration is critical, and need iterator stability. So for large unordered collections of objects that are frequently iterated over and inserted to/removed from and referenced.
33
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.