c++ - Boost.享元内存消耗

Question

我正在阅读 article关于 Boost.Flyweight 性能

正如您在链接中看到的，工厂的开销是
- 对于 hashed_factory:~2.5 * sizeof(word)
- 对于 set_factory:4 * sizeof(word)

基本问题是....为什么 set 是 4 个词而不是 0？

据我所知，使用散列意味着计算和存储散列键，而不是使用集合:它被实现为红黑树，插入和查找需要 log(n)，所以没有值被存储并且内存开销应该为零(缺点是在哈希的情况下你将进行 log(n) 比较而不是一次比较)。哪里错了？

Answer 1

RB树的每个节点包含一个指向左 child 的指针，一个指向右 child 的指针，颜色和一个数据。前三个算作开销，这意味着它不是 0。我不太清楚为什么当 3 个元素很容易用 3 个词表示时他们说它是 4，但也许它们算在其他东西中(比如父节点指针，这不是绝对必要的，也不是内存分配开销，尽管这不太可能)。