更好的替代std :: vector <std :: unique_ptr <T >>？

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> 我的基准更高效.

(对于较大的类型,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 的分配从缓冲区中间向下增长。

只要整个缓冲区适合缓存行，您就会尽可能快。实施起来并不容易，您当前的解决方案可能已经足够好了。