c++ - 如何在现代 C++ 中有效地为指向虚拟基类的指针 vector 分配空间

Question

我有以下数据模型

struct Base {
    int x_;
    int y_;
    int z_;

    virtual int getId() const;
    virtual int getValue() const = 0;
    virtual Base* create() const = 0;
    bool operator<(const Base &other);
};

struct Derived0 : public Base {
    virtual Derived0* create() const { return new Derived0(); };
    virtual int getId() const;
    virtual int getValue() const;
};
//...
struct DerivedN : public Base {
    virtual DerivedN* create() const { return new DerivedN(); };
    virtual int getId() const;
    virtual int getValue() const;
};

并按照以下方式填写(简体)

int n = 0;
std::shared_ptr<Base> templ[100];

templ[n++] = std::make_shared<Derived0>();
//...
templ[n++] = std::make_shared<DerivedN>();

std::vector<std::shared_ptr<Base>> b;

for (int i = 0; i < n; i++) {
    while (...) { // hundreds of thousands iterations
        std::shared_ptr<Base> ptr(templ[i]->create());
        // previous call consumes most of the time
        //...
        b.push_back(ptr);
    }
}

std::sort(b.begin(), b.end());
// ...

因为我需要大量的派生对象，所以我想知道是否可以更有效地完成初始化。在展示的案例中，大部分时间花在了创建单个共享指针上。

我尝试了一种预分配 Base 对象数组的方法(因为所有 Derived 都具有相同的大小)，为每个模板转换虚拟类型并将原始指针存储到该数组.毫不奇怪，这种方法要快很多倍。但是不干净，不能使用vector，内存管理有问题。

谁能给我一个建议，如何用 C++ 的方式高效地做到这一点

• 如果所有对象的大小都相同？
• 如果大小不同？

Answer 1

在我看来，您的许多性能问题都可以通过使用 std::unique_ptr 并提前保留一些 std::vector 内存来解决。

std::shared_ptr<Base> ptr(templ[i]->create());

上述行涉及为派生类型和 std::shared_ptr 控制 block 动态分配内存。如果您没有共享所有权语义，那么使用 std::unique_ptr 将消除对这些分配之一的需要。

b.push_back(ptr);

当您执行上述操作次数足够多时， vector 将用完它为您分配的内存并尝试分配更多内存。 std::vector 的设计方式使其摊销了恒定的时间复杂度，但我们可以采取任何措施来减轻这种情况，尤其是对于巨大的 vector ，这将节省时间。

您的新代码可能类似于:

std::vector<std::unique_ptr<Base>> b;
b.reserve(n * /*number of iterations*/);

for (int i = 0; i < n; i++) {
    while (...) { // hundreds of thousands iterations
        std::unique_ptr<Base> ptr(templ[i]->create());
        //...
        b.push_back(ptr);
    }
}

顺便说一句，您可以通过执行以下操作来限制原型(prototype)数组创建的代码重复:

template <class Base, class... Derived, std::size_t... Idx>
auto arrayOfUniqueDerived (std::index_sequence<Idx...>)
{
    std::array<std::unique_ptr<Base>, sizeof...(Derived)> arr;
    (void) std::initializer_list<int> { (arr[Idx] = std::make_unique<Derived>(), 0)... };
    return arr;
}

template <class Base, class... Derived>
auto arrayOfUniqueDerived ()
{
    return arrayOfUniqueDerived<Base,Derived...>(std::index_sequence_for<Derived...>{});
}

然后像这样使用它:

std::array<std::unique_ptr<Base>,3> templ =
      arrayOfUniqueDerived<Base,Derived0,Derived1,Derived2>();