具有未初始化存储的STL载体？

Question

我正在编写一个内部循环,需要将structs放在连续的存储中.我不知道有多少这些struct会提前出现.我的问题是STL vector将其值初始化为0,所以无论我做什么,我都要承担初始化的成本以及将struct成员设置为其值的成本.

有没有办法阻止初始化,或者是否有一个类似STL的容器,那里有可调整大小的连续存储和未初始化的元素？

(我确信这部分代码需要进行优化,我确信初始化是一项重要的成本.)

另外,请参阅下面的评论,以了解初始化发生的时间.

一些代码:

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size()
    memberVector.resize(mvSize + count); // causes 0-initialization

    for (int i = 0; i < count; ++i) {
        memberVector[mvSize + i].d1 = data1[i];
        memberVector[mvSize + i].d2 = data2[i];
    }
}

Answer 1

std::vector必须以某种方式初始化数组中的值,这意味着必须调用一些构造函数(或复制构造函数).vector如果要访问数组的未初始化部分(如初始化),则(或任何容器类)的行为是未定义的.

最好的方法是使用reserve()和push_back(),以便使用复制构造函数,避免默认构造.

使用您的示例代码:

struct YourData {
    int d1;
    int d2;
    YourData(int v1, int v2) : d1(v1), d2(v2) {}
};

std::vector<YourData> memberVector;

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size();

    // Does not initialize the extra elements
    memberVector.reserve(mvSize + count);

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a temporary.
        memberVector.push_back(YourData(data1[i], data2[i]));
    }
}

调用reserve()(或resize())这样的唯一问题是,您最终可能会比您需要更频繁地调用复制构造函数.如果你可以对数组的最终大小做一个很好的预测,那么reserve()在开始时对空间的改善就更好了.如果您不知道最终尺寸,至少平均副本数量将是最小的.

在当前版本的C++中,内部循环有点效率低,因为临时值在堆栈上构造,复制构造到向量内存,最后临时被破坏.然而,下一版本的C++有一个名为R-Value references(T&&)的功能,这将有所帮助.

提供的接口std::vector不允许使用其他选项,即使用某些类似工厂的类来构造默认值以外的值.下面是一个粗略的例子,说明这个模式在C++中的实现:

template <typename T>
class my_vector_replacement {

    // ...

    template <typename F>
    my_vector::push_back_using_factory(F factory) {
        // ... check size of array, and resize if needed.

        // Copy construct using placement new,
        new(arrayData+end) T(factory())
        end += sizeof(T);
    }

    char* arrayData;
    size_t end; // Of initialized data in arrayData
};

// One of many possible implementations
struct MyFactory {
    MyFactory(int* p1, int* p2) : d1(p1), d2(p2) {}
    YourData operator()() const {
        return YourData(*d1,*d2);
    }
    int* d1;
    int* d2;
};

void GetsCalledALot(int* data1, int* data2, int count) {
    // ... Still will need the same call to a reserve() type function.

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a factory
        memberVector.push_back_using_factory(MyFactory(data1+i, data2+i));
    }
}

这样做意味着您必须创建自己的矢量类.在这种情况下,它也应该是一个简单的例子.但是有时候使用这样的工厂函数会更好,例如,如果插入是以某些其他值为条件的,那么即使实际上并不需要,你也必须无条件地构造一些昂贵的临时函数.

Answer 2

的C++ 0x增加了新的成员函数模板emplace_back来vector(这依赖于可变参数模板和完善的转发)是摆脱完全的任何临时对象:

memberVector.emplace_back(data1[i], data2[i]);

Answer 3

要澄清reserve()响应:您需要将reserve()与push_back()结合使用.这样,不会为每个元素调用默认构造函数,而是调用复制构造函数.您仍然需要在堆栈上设置结构,然后将其复制到向量.另一方面,如果你使用它可能

vect.push_back(MyStruct(fieldValue1, fieldValue2))

编译器将直接在与向量相同的内存中构造新实例.这取决于优化器的智能程度.您需要检查生成的代码才能找到答案.

Answer 4

您可以使用boost::noinit_adaptor默认初始化新元素（这不是内置类型的初始化）：

std::vector<T, boost::noinit_adaptor<std::allocator<T>> memberVector;

只要您不将初始化程序传递给resize，它就会默认初始化新元素。

Answer 5

在C++ 11(和boost)中,您可以使用数组版本unique_ptr来分配未初始化的数组.这不是一个stl容器,但仍然是内存管理和C++ - ish,这对于许多应用程序来说已经足够了.

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]);

Answer 6

那么问题来了，resize正在调用insert，它正在从默认构造的元素为每个新添加的元素进行复制构造。为了使其成本为零，您需要编写自己的默认构造函数和自己的复制构造函数作为空函数。对复制构造函数执行此操作是一个非常糟糕的主意，因为它会破坏 std::vector 的内部重新分配算法。

摘要：您将无法使用 std::vector 来做到这一点。