EnTT: 容器 Container

EnTT 提供了两种特殊的容器: Dense Map (密集映射) 和Dense Set (密集集合), 它们类似标准库容器 (如 std::unordered_map 和 std::unordered_set), 但是这些容器的设计重点在于提升内存局部性和迭代效率, 非常适合在高性能场景中使用

密集映射 Dense Map

Dense Map 是一种哈希映射容器, 其数据存储在一个紧凑的数组中, 从而减少迭代时的内存跳跃, 优化了缓存性能

桶 bucket

每个 桶 bucket 通过数组中的 隐式列表 组织, 无需额外的指针链表

entt::dense_map<int, std::string> map;
map.insert({1, "one"});
map.insert({3, "three"});
map.insert({7, "seven"}); // 假设 1, 3, 7 的哈希值都落到同一个桶

假设哈希函数将键 1, 3, 和 7 映射到同一个桶 (假设桶索引为 0), 稀疏数组 会记录桶索引与 紧凑数组 的映射关系

sparse_array[0] = 0;  // 桶 0 的元素从紧凑数组的索引 0 开始

实际的键值对数据存储在紧凑数组中, 且属于同一桶的元素在紧凑数组中连续存储

// 也许是这样, 不确定
packed_array = [{1, "one"}, {3, "three"}, {7, "seven"}];

桶与元素的关系

• 在传统哈希表中, 一个桶直接存储多个元素的链表指针, 桶与元素的关系是一对多
• 在 EnTT 中, 一个桶通过稀疏数组 间接映射到 紧凑数组 中的 多个元素, 仍然是一对多, 但存储更加高效

迭代器返回类型

与 标准容器 不同的是, 迭代器将返回 引用的键值对, 这和标准库容器不同

标准库 std::unordered_map 返回对键值对的引用 std::pair<const Key, Value>&

std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}};
for (auto& pair : map) {
    std::cout << pair.first << " -> " << pair.second << std::endl;
    pair.second = "updated";  // 修改值
}

而 EnTT 的 Dense Map 返回引用对, std::pair<const Key&, Value&>

entt::dense_map<int, std::string> map;
map.insert({1, "one"});
map.insert({2, "two"});
 
for (auto [key, value] : map) {
    std::cout << key << " -> " << value << std::endl;
    value = "updated";  // 直接修改值
}

密集集合 Dense Set

Dense Set 是一种哈希集合容器, 与 Dense Map 类似, 数据同样存储在紧凑数组中, 但只存储元素本身, 而非键值对, 用于管理一组 不重复的值, 支持快速查找、插入和删除操作, 容器中的每个元素是唯一的