C++26 adds a new container to the standard library: std::hive. It is meant to occupy the ground between std::vector and std::list. Like a vector, it keeps its elements in contiguous blocks of memory, so scanning it does not require you to chase a pointer for every element. Like a list, it never moves an element once it has been inserted: your pointers, references and iterators stay valid, and you may erase any element in constant time without disturbing the others.
Internally, a hive is a linked list of blocks. Each block carries a skipfield: a small integer per slot that tells the iterator how many erased slots to jump over.
No standard library ships std::hive yet to my knowledge. Fortunately there is an implementation (plf::hive by Matt Bentley) as a single header file that you can use today.
I use elements of type uint64_t, GCC 16.1 with -O3 -march=native, on an Intel Xeon Gold 6548N (Emerald Rapids), pinned to one core. Numbers are nanoseconds per element, along with the cycles and instructions retired per element.
We start from an empty container and append a million values. The container is then destroyed.
A std::list needs one allocation per element, and glibc’s malloc and free together cost over 200 instructions per element. It is an order of magnitude behind everyone else. That is not news.
The interesting comparison is vector against hive. A hive is about twice the cost of a vector, and it needs twice the instructions. This is the price of the skipfield: every insertion writes an element and a skipfield entry, and maintains the block bookkeeping. Note that calling reserve on a hive does not help in my experiments.
Next we iterate over the the container and sum the values.
A hive iterates no faster than a linked list here, slightly slower, in fact, and about eight times slower than a vector. (Update: Joseph Garvin points out that I measure the happy case for the std::list in this instance where all the entries were allocated in sequence. The worst case scenario for std::list when the nodes are all over the heap can be much slower.)
The vector loop retires one instruction per element and finishes in 0.78 cycles: the processor is executing several elements at once. This is possible because the std::vector implementation benefits from autovectorization: the compiler recognizes that it can load several words at once in wide (SIMD). Further, it does not have to check the bitfield like the std::hive data structure.
We can check this. Walk the same container with two independent iterators, one starting halfway in, and count the cost per element visited:
The vector does not care: it was already throughput-bound. The hive and the list get nearly twice as fast per element, because two independent chains can be in flight at once. Hive iteration is latency-bound, exactly like list iteration. It merely has better locality.
That locality does show up when the data gets big. At ten million elements the list falls apart while the hive holds steady:
Erasing is what a hive is for, so it would be unfair not to look. I erase half the elements at scattered positions using std::remove_if:
The hive wins, but by less than you might expect, and at ten million elements the ordering reverses (1.3 ns for the vector against 2.5 for the hive). std::remove_if is a single streaming pass, and streaming passes are cheap. Of course the vector moved every surviving element and invalidated every pointer into it, which is precisely what a hive promises not to do.
Memory, measured by asking glibc how many bytes it has handed out, per live element:
A hive costs about a byte per element over a vector, for a payload of eight bytes, when the vector is packed tight. A list costs more due to the overhead of the linked list.
A vector built by push_back has a capacity that typically exceeds its size. Thus even if you have 8-byte entries, you will use, on average, more than 8 bytes per entry even for large vectors. You can recover the excess capacity with the shrink_to_fit method.
What should we conclude?
The std::hive data structure is not a faster vector. But it is a much better std::list. It gives you the same guarantees that make people reach for a list, stable references, cheap erasure anywhere, while using less memory.
Daniel Lemire, "How fast is C++26’s std::hive?," in Daniel Lemire's blog, August 2, 2026, https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/.
[BibTeX]
I would be interested in the benchmark of deleting a single element in the middle of a 10M hive vs vector. Hive should shine here far more than deleting half of the elements at random.
Can you define what you mean by deleting an element in the middle? You mean that you iterate through half of the values, and then delete the element in the middle of the iteration, is that what you mean?
std::hive sounds a lot like several implementations of std::deque. Adding that to your comparison would be interesting.
I don’t think std::hive is comparable to std::deque. I don’t think it could be used for a similar purpose.
It’s a good article, but I think your last paragraph confused quite a few people who read this. It’s not really a better list, because a list maintains very clear and rigorous guarantees around ordering – your insertion point determines where you are ordered and its part of the public API. In hive, “holes” from previous deletions are being reused, so in practical usage with both deletions and insertions you don’t really maintain any kind of usable insertion order.
So rather than being a better list, it’s a way to get much better performance when you only need some of what a list provides.
That’s a fair point. I would still push back and say that the closest match in the existing container is std::list. In many cases where you use an std::list today, you could switch. But yeah, it is not a drop-in replacement in all cases.
A more analogically accurate animal-related name for hive would have been “cote”. A dovecote is a structure with a slot for each dove, but one is assigned by convenience when the dove arrives, and becomes available for any other dove the moment its occupant leaves.
But what it resembles more than anything is a coat-check booth at the opera. You hand over your coat and are given a ticket. When you hand over the ticket afterward, the number on it locates the hanger, and off you go. You had no idea what hanger your coat would be on, but you carry with you what you need to find it. Unlike a booth, though, you can iterate over all the occupied slots, something that might be done at a booth only if you lose your ticket, after everybody else has picked theirs up and gone home (provided nobody pickpocketed you and ran off with your coat).
Well just reserving and then appending 1 million values in a loop is not necessarily realistic, especially when worring about the memory fragmentation, because the std::list elements are likely to be allocated in contiguous memory and fit into the cache.
It would be more realistic to do some random allocation (at least 1kb average) in between appending every element. Then the comparisons for the iteration performance would probably yield very different results.
My assessment: there is room for meaningful incremental implementation improvement, especially in iteration, but no likely breakthrough that makes hive a replacement for vector.
Its real success criterion is becoming the clearly superior stable-address alternative to list and hand-built object pools.
How would I do that?
– Track whether each hive block contains erased elements.
– In iterator::operator++, when the current block has no holes, advance with a simple pointer increment.
– Use the existing skipfield logic only for blocks containing erased slots.
– Keep block boundaries and frequently accessed metadata together to reduce cache misses.
– Tune the branch arrangement so the common dense case is predicted correctly.
For bulk operations, process an entire contiguous live run at once instead of repeatedly calling operator++.
This enables compiler unrolling and vectorization.
The change should be benchmarked across dense and fragmented containers: the additional “is this block dense?” branch must improve normal iteration without slowing workloads containing many erased elements.
like that:
Dense-block iterator fast path
iterator& operator++()
{
if (group_->erased_count == 0) {
// Dense block: no skipfield lookup required.
++element_;
++skipfield_;
} else {
// Fragmented block: jump over the next erased run.
++skipfield_;
const auto skip = *skipfield_;
element_ += 1 + skip;
skipfield_ += skip;
}
if (element_ == group_->used_end)
move_to_next_group();
return *this;
}
The block’s erased_count is updated during erasure and hole reuse:
void erase(iterator pos)
{
destroy(pos.element_);
mark_erased_in_skipfield(pos);
++pos.group_->erased_count;
}
void insert_into_erased_slot(group* g, value_type value)
{
construct(reusable_slot(g), value);
remove_from_skipfield(g);
if (–g->erased_count == 0)
mark_group_dense(g);
}
Bulk operations can bypass iterators completely for dense blocks:
for (group* g = first_group; g != nullptr; g = g->next) {
if (g->erased_count == 0) {
process_contiguous_range(g->begin, g->used_end);
} else {
process_live_runs_using_skipfield(g);
}
}
This allows unrolling and vectorization of dense blocks. However, the extra erased_count == 0 branch must be benchmarked: it may accelerate dense traversal but slightly penalize highly fragmented containers.