c++ - std::vector> 有更好的替代方案吗？

Question

我正在寻找需要满足以下要求的容器(针对游戏开发，尤其是实体管理):

1. 快速迭代
2. 没有存储元素的拷贝
3. 不会使指向元素的指针失效
4. 删除和插入元素

例子:

Container<Entity> container;

// This pointer will always point to the player
Entity* player{new Entity};          
container.add(player);               

// Set some entities to "dead"
for(auto& e : container) if(e->type == "Enemy") e->die(); 

// Use erase-remove idiom on "dead" entities
container.cleanup();                 

// Player pointer is still valid
player->doSomething();               

---

到目前为止，我已经尝试了两种不同的容器类型:

• std::vector<std::unique_ptr<T>>
  1. 缓存友好(快速迭代)
  2. 没有拷贝(感谢std::unique_ptr)
  3. 没有指针失效(感谢std::unique_ptr)

...和...

• std::list<T>
  1. 缓存不友好(迭代较慢)
  2. 无拷贝
  3. 没有指针失效

即使这看起来违反直觉，std::vector<std::unique_ptr<T>>比 std::list<T> 性能更高according to my benchmarks .

(对于更大的类型，std::list<T> 在插入期间性能更高，但 std::vector<std::unique_ptr<T>> 仍然胜出)。

---

我想知道是否有比 std::vector<std::unique_ptr<T>> 更好的选择.

理想情况下，替代方案应该缓存友好，以实现快速迭代，并允许用户在添加/删除现有项目后仍能引用相同的项目(指针不应失效)。

Answer 1

通过性能测试，您正在做正确的事情。这是回答这个问题的唯一正确方法。

我唯一知道的可能更快的是创建一个缓冲区。然后为 vector<unique_ptr<T>, custom_allocator<unique_ptr<T>>> 创建自定义分配器从你的缓冲区分配。

也从同一个缓冲区分配你的对象(这样 unique_ptr 指向缓冲区)。

为此，您必须知道上限，或者在超出限制时编写溢出逻辑。

让自定义分配器从缓冲区中间向上增长。

让 unique_ptr 的分配从缓冲区中间向下增长。

只要整个缓冲区适合缓存行，您就会尽可能快。这并非易事，您当前的解决方案可能已经足够好了。