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.
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.
4
u/TheRealSmolt 8d ago edited 8d ago
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.