有没有比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>>的方法。

理想情况下，这种替代方法应该是缓存友好的，能够快速迭代，并且在添加/删除现有项后仍允许用户引用相同的项（指针不应失效）。

- Vittorio Romeo

---

为什么需要一个替代 vector 的东西，而 vector 已经表现得很好了？ - Nawaz

你尝试过使用std::deque吗？它可以带来与std::vector相同的许多好处，但对于大量数据不需要大量连续的内存。 - Zac Howland

你将会更频繁地执行哪些操作？ - Andy Prowl

我怀疑性能会更好，但你可以尝试使用 boost::ptr_vector<T>。 - Benjamin Lindley

@VittorioRomeo：如果您可以找到要创建的对象数量的上限，您可以使用某种对象池模式，避免拥有指针。 - Andy Prowl

Answer 1

你正在做性能测试，这是回答这个问题的唯一方法。

唯一可能更快的方法是创建缓冲区。然后为`vector , custom_allocator > >`创建一个自定义分配器，该分配器从缓冲区中分配。

同时从同一缓冲区分配对象（使得unique_ptr指向缓冲区）。

要做到这一点，您必须知道上限，或者在超出限制时编写溢出逻辑。

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

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

只要整个缓冲区适合一个缓存行，就可以尽可能地快。 这并不容易实现，而您当前的解决方案可能已经足够好了。

- Howard Hinnant

Answer 2

听起来好像你需要一个简单的std::vector。这是迭代速度最快的方法，因为你只需要在内存的连续部分进行一次扫描。如果你了解T的结构，你可以做得更好。

使用push_back可以在O(1)时间内插入新元素。使用swap和pop_back的组合可以在O(1)时间内删除单个元素。使用remove_if和erase的组合可以删除多个元素。

你不能存储指针，因为它们将失效。但是，你可以存储索引，并使向量几乎全局可用。

使用索引而不是指针有两个进一步的优点：

1. int使用4字节，而指针使用8字节。使用指针会自动导致更大的内存占用量，从而导致更多的缓存未命中。我怀疑你不会有超过2^32个实体，所以8字节是过剩的。
2. 你可以使用数组结构而不是结构数组。

为了说明第2点，请看以下两个示例：

struct Unit{
    int type, health;
};
vector<Unit>units;
for(int i=0; i<(int)units.size(); ++i)
    if(units[i].type == medic)
        units[i].health += 10;

vs

vector<int>type, health;
for(int i=0; i<(int)type.size(); ++i)
    if(type[i] == medic)
        health[i] += 10;

假设只有很少的医务人员。在第一个代码片段中，整个内存必须通过缓存进行传输，因为类型和健康值在内存中是相邻的。在第二个示例中，只需加载所有类型和少量医务人员的健康值。总体而言，需要加载较少的内存，这导致迭代更快。

- Someone Anonymous