C++ 中不同派生类的高效容器

Question

在编写游戏程序时，我曾经将所有游戏对象存储在 std::vector 中，并具有初始化和固定大小。最近觉得游戏对象之间需要一些继承classes.

所以假设我有 40 个 classes 来自我的 class Enemy。如果我想将那些 class 中的 objects/instances 存储在向量中，我只能选择将它们存储为向量 Enemy* 对吧？所以唯一连续分配的是指针，对吧？所以当需要取消引用时，我仍然会有很多缓存未命中，对吗？

是否有任何 "best practice" 方法将派生的 classes 存储在连续分配的内存中，以便循环遍历它们花费最少的时间？

Answer 1

Boost 刚刚接受了一个专门用于此目的的库：poly_collection. In particular, you are looking for base_collection

在内部，它使用多个向量，每个（派生）类型一个，同时提供接近标准容器的接口。

This article by its author provides some design background and a comparison to other solutions, like a vector of unique_ptr. The advantage is two-fold: first, by not using pointers and dynamic memory allocation per element you have better memory locality, and second, grouping elements of the same type together, you help branch prediction 和虚拟成员函数的指令缓存。

Answer 2

这个呢？

struct alignas(...) Base {};
struct Derived1 : Base {};
struct Derived2 : Base {};

int main()
{
    std::vector<Base> v(2);
    new (&v[0]) Derived1();
    new (&v[1]) Derived2();
    return 0;
}

新的展示位置可以解决问题。它适用于多态性。对齐是为了确保向量包含相同大小的对象。将 ... 替换为数字（2 的幂），使得 Derived1 和 Derived2 的实例都适合向量。如果 sizeof(Derived1) returns 16 和 sizeof(Derived2) returns 24，则需要 alignas(32).

编辑

正如@KubaOber 所说，alignas 不是为了管理分配大小而设计的，而只是为了在内存中定位对象。实现目标的更好方法是使用 std::variant。像这样：

int main()
{
    std::vector<std::variant<Derived1, Derived2>> v;
    v.emplace_back(Derived1());
    v.emplace_back(Derived2());

    for (const auto& e : v)
        std::visit(VisitPackage(), e);

    return 0;
}

其中 VisitPackage 可能是这样的：

struct VisitPackage
{
    void operator()(const Derived1&) { std::cout << "Derived 1.\n"; }
    void operator()(const Derived2&) { std::cout << "Derived 2.\n"; }
};

C++ 中不同派生类的高效容器

Efficient container for different derived classes in C++

c++

memory

containers

allocation

vector

C++ 中不同派生 类 的高效容器

Efficient container for different derived classes in C++

c++

memory

containers

allocation

vector

C++ 中不同派生类的高效容器