Introduction of std::hive to the standard library (2021)

2 months ago by lysdexic to c/cpp

refalo 4 points 2 months ago

ELI5?

path: 0 25416883, hotness: undefined, score: 4, children: 1
xthexder 5 points 2 months ago

Just quoting from the introduction:

hive is a formalisation, extension and optimization of what is typically known as a 'bucket array' container in game programming

The concept of a bucket array is: you have multiple memory blocks of elements, and a boolean token for each element which denotes whether or not that element is 'active' or 'erased', commonly known as a skipfield. If it is 'erased', it is skipped over during iteration. When all elements in a block are erased, the block is removed, so that iteration does not lose performance by having to skip empty blocks. If an insertion occurs when all the blocks are full, a new memory block is allocated.

It seems a little similar to a std::deque with the addition of flags to mark elements as erased to avoid reallocating blocks.
The main advantage is stable references and iterators with minimal extra allocations/deallocations.

I've built similar structures in my own game engine where I keep a sorted list of free indexes, so new entries fill up the earliest free index, and on average the empty entries stay at the end with valid entires staying packed together in contiguous memory at the beginning.

path: 0 25416883 25420514, hotness: undefined, score: 5, children: 0
basiliscos2 1 point 2 months ago

What is the need of that if there is a std::pmr::vector and similar?

path: 0 25427743, hotness: undefined, score: 1, children: 0
cpp
cpp

@programming.dev

login for more options
2380
415
47

The center for all discussion and news regarding C++.

Rules

  • Respect instance rules.
  • Don't be a jerk.
  • Please keep all posts related to C++.

go to feed...