带有未初始化存储的STL向量？

Question

我正在编写一个内部循环，需要将struct放置在连续的存储空间中。 我不知道有多少这些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];
    }
}

- Jim

---

注意 - 使用reserve()不是解决方案，因为您无法合法地访问位于end()及以上位置的数据。 - Jim Hunziker

另一个澄清：构造函数并不会将值初始化为0。而是resize调用了insert，它会这样做。 - Jim Hunziker

请注意：您无法访问未初始化的数据。对于超出vector<T> .end()和T[]未初始化成员的情况也是如此。但是，使用vector时，调试代码很可能会告诉您现在的情况。数组代码将在客户PC上默默失败。 - MSalters

这是一个很好的问题。对于一些应用程序来说，重要的是要意识到std::vector始终会初始化其元素，即使它们是平凡数据（POD）。 - Brent Bradburn

问题的关键在于向量默认进行“零”初始化，因为std::allocator只有值和零初始化，但没有默认初始化的方法。 - Mooing Duck

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引用（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));
    }
}

这样做意味着您必须创建自己的向量类。在这种情况下，它还使本应该是简单示例的事情变得复杂了。但是，在某些情况下，使用像这样的工厂函数可能更好，例如如果插入取决于其他值，并且您否则必须无条件构造一些昂贵的临时对象，即使实际上并不需要。

- Lloyd

Answer 2

在C++11（和boost）中，您可以使用unique_ptr的数组版本来分配未初始化的数组。这不完全是一个STL容器，但仍然是内存管理并且类似于C ++，对于许多应用程序来说已经足够好了。

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

- goertzenator

Answer 3

C++0x增加了一个新的成员函数模板emplace_back到vector中（该函数依赖于可变参数模板和完美转发），它完全消除了任何临时对象：

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

- fredoverflow

Answer 4

关于reserve()的解释：你需要将reserve()与push_back()结合使用。这样，对于每个元素，不会调用默认构造函数，而是调用复制构造函数。你仍然需要在堆栈上设置结构体，并将其复制到向量中，因此仍然需要付出代价。另一方面，如果你使用

vect.push_back(MyStruct(fieldValue1, fieldValue2))

编译器将直接在向量所拥有的内存中构造新实例。这取决于优化器的智能程度。您需要检查生成的代码以了解详情。

- user3458

---

事实证明，gcc的优化器在O3级别下并不足够聪明，无法避免复制。 - Jim Hunziker

Answer 5

你可以使用boost::noinit_adaptor来默认初始化新元素（对于内置类型而言，这意味着不进行初始化）：

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

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

- Maxim Egorushkin

Answer 6

所以问题在于，resize调用了insert，而每次添加新元素时都会对默认构造的元素进行复制构造。要使其成为0成本，您需要编写自己的默认构造函数和复制构造函数，并将其设为空函数。这样做会破坏std::vector的内部重新分配算法，因此对复制构造函数进行此操作是一个非常糟糕的想法。

总结：您无法使用std::vector来完成此操作。

- Don Neufeld

---

这是真正的问题。std::vector应该意识到，如果T具有平凡的默认构造函数，则不必进行任何初始化。感谢指出复制构造函数在这里正在做不必要的工作。 - Eric Hein

Answer 7

您可以使用一个包装器类型来包装您的元素类型，并提供一个默认构造函数，该函数不执行任何操作。例如：

template <typename T>
struct no_init
{
    T value;

    no_init() { static_assert(std::is_standard_layout<no_init<T>>::value && sizeof(T) == sizeof(no_init<T>), "T does not have standard layout"); }

    no_init(T& v) { value = v; }
    T& operator=(T& v) { value = v; return value; }

    no_init(no_init<T>& n) { value = n.value; }
    no_init(no_init<T>&& n) { value = std::move(n.value); }
    T& operator=(no_init<T>& n) { value = n.value; return this; }
    T& operator=(no_init<T>&& n) { value = std::move(n.value); return this; }

    T* operator&() { return &value; } // So you can use &(vec[0]) etc.
};

使用方法：

std::vector<no_init<char>> vec;
vec.resize(2ul * 1024ul * 1024ul * 1024ul);

- deonb

---

当程序没有进行优化编译时，它会变慢吗？在调试模式下，访问速度会变慢吗？ - no one special

Answer 8

我在这里测试了一些建议的方法。 我在一个容器/指针中分配了一个巨大的数据集（200GB）：

编译器/操作系统：

g++ (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

设置：（c++-17，-O3 优化）

g++ --std=c++17 -O3

我使用linux-time计时整个程序的运行时间

1.) std::vector:

#include <vector>

int main(){
  constexpr size_t size = 1024lu*1024lu*1024lu*25lu;//25B elements = 200GB
  std::vector<size_t> vec(size);
}
real    0m36.246s
user    0m4.549s
sys     0m31.604s

那是36秒。

2.) 使用boost::noinit_adaptor的std::vector

#include <vector>
#include <boost/core/noinit_adaptor.hpp>

int main(){
  constexpr size_t size = 1024lu*1024lu*1024lu*25lu;//25B elements = 200GB
  std::vector<size_t,boost::noinit_adaptor<std::allocator<size_t>>> vec(size);
}

real    0m0.002s
user    0m0.001s
sys     0m0.000s

所以这就解决了问题。只分配而不初始化基本上不会花费任何代价（至少对于大数组而言）。

3.) std::unique_ptr<T[]>：

#include <memory>

int main(){
  constexpr size_t size = 1024lu*1024lu*1024lu*25lu;//25B elements = 200GB
  auto data = std::unique_ptr<size_t[]>(new size_t[size]);
}

real    0m0.002s
user    0m0.002s
sys     0m0.000s

基本上和2)一样的性能，但不需要使用boost。 我还测试了简单的new/delete和malloc/free，其性能与2)和3)相同。

因此，如果您处理大数据集，则默认构造可能会导致巨大的性能损失。 在实践中，您实际上希望在之后初始化分配的数据。 然而，一些性能惩罚仍然存在，特别是如果稍后的初始化是并行执行的。 例如，我使用（伪）随机数集初始化一个巨大的向量：

（现在我在24核AMD Threadripper 3960X上使用fopenmp进行并行化）

g++ --std=c++17-fopenmp -O3

1.) std::vector：

#include <vector>
#include <random>

int main(){
  constexpr size_t size = 1024lu*1024lu*1024lu*25lu;//25B elements = 200GB
  std::vector<size_t> vec(size);
  #pragma omp parallel
  {
    std::minstd_rand0 gen(42);
    #pragma omp for schedule(static)
    for (size_t i = 0; i < size; ++i) vec[i] = gen();
  }
}
real    0m41.958s
user    4m37.495s
sys     0m31.348s

这是42秒，仅比默认初始化多6秒。问题在于，std::vector的初始化是顺序的。

2.) 使用boost::noinit_adaptor的std::vector：

#include <vector>
#include <random>
#include <boost/core/noinit_adaptor.hpp>

int main(){
  constexpr size_t size = 1024lu*1024lu*1024lu*25lu;//25B elements = 200GB
  std::vector<size_t,boost::noinit_adaptor<std::allocator<size_t>>> vec(size);
  #pragma omp parallel
  {
    std::minstd_rand0 gen(42);
    #pragma omp for schedule(static)
    for (size_t i = 0; i < size; ++i) vec[i] = gen();
  }
}
real    0m10.508s
user    1m37.665s
sys     3m14.951s

即使使用随机初始化，由于我们可以跳过std::vector的顺序初始化，因此代码仍然快了4倍。

因此，如果您处理大型数据集并计划之后在并行中初始化它们，您应该避免使用默认的std::vector。

- Henryk

Answer 9

啊...

尝试以下方法：

std::vector<T>::reserve(x)

它将使您能够为x个项目保留足够的内存，而无需初始化任何内容（您的向量仍为空）。因此，在超过x之前不会进行重新分配。

第二点是向量不会将值初始化为零。您在调试中测试代码了吗？

在g++上验证后，以下代码：

#include <iostream>
#include <vector>

struct MyStruct
{
   int m_iValue00 ;
   int m_iValue01 ;
} ;

int main()
{
   MyStruct aaa, bbb, ccc ;

   std::vector<MyStruct> aMyStruct ;

   aMyStruct.push_back(aaa) ;
   aMyStruct.push_back(bbb) ;
   aMyStruct.push_back(ccc) ;

   aMyStruct.resize(6) ; // [EDIT] double the size

   for(std::vector<MyStruct>::size_type i = 0, iMax = aMyStruct.size(); i < iMax; ++i)
   {
      std::cout << "[" << i << "] : " << aMyStruct[i].m_iValue00 << ", " << aMyStruct[0].m_iValue01 << "\n" ;
   }

   return 0 ;
}

给出以下结果：

[0] : 134515780, -16121856
[1] : 134554052, -16121856
[2] : 134544501, -16121856
[3] : 0, -16121856
[4] : 0, -16121856
[5] : 0, -16121856

你看到的初始化可能只是一个产物。

[编辑] 在resize的注释后，我修改了代码以添加resize行。resize有效地调用了向量内对象的默认构造函数，但如果默认构造函数什么也不做，那么就什么都没有被初始化... 我仍然相信这只是一个产物（我设法第一次使用以下代码将整个向量清零：

aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;

所以... :-/

[编辑2] 如Arkadiy所提供的，解决方案是使用内联构造函数，以取得所需的参数。类似于：

struct MyStruct
{
   MyStruct(int p_d1, int p_d2) : d1(p_d1), d2(p_d2) {}
   int d1, d2 ;
} ;

这段代码可能会被内联到你的代码中。

但是，你应该使用性能分析工具来检查你的代码，以确保这段代码是你的应用程序的瓶颈。

- paercebal

---

我上面写了一个注释。它并不是用于初始化为0的vector构造函数，而是resize()函数。 - Jim Hunziker

在这种情况下，MyStruct具有平凡的构造函数，因此没有进行任何初始化。这可能与OP的情况不同。 - Greg Rogers

我认为你走在了正确的道路上。在结构体中，我没有定义构造函数，因此它的默认构造函数（我相信）会对其进行零初始化。我将检查是否添加一个什么也不做的默认构造函数可以解决这个问题。 - Jim Hunziker

在这种情况下，似乎向量让我们失望了。即使我们不需要或不想要它，我们也会支付初始化费用。这是由insert()的语义保证的，resize()调用它。用于初始化的值基于传递给resize()的MyStruct中的任何内容。由于您在调用resize()时没有指定任何内容，因此使用了默认构造函数。由于在这种情况下默认构造函数什么也不做，因此您可能会得到零或其他内容。无论哪种方式，都要支付resize()执行的初始化费用。 - Brent Bradburn

@nobar：这取决于MyStruct构造函数。如果它是空的，并且是内联的，并且MyStruct成员具有零成本构造函数，则C++编译器将对其进行优化，使其变为无操作。然后，我们就不需要为此付费。只需为调整大小付费。 - paercebal

Answer 10

从你的代码来看，似乎你有一个结构体向量，每个结构体包含2个int。你是否可以改为使用2个整数向量呢？这样

copy(data1, data1 + count, back_inserter(v1));
copy(data2, data2 + count, back_inserter(v2));

现在你不需要每次复制一个结构体而支付费用。

- fizzer

---

有趣。这可能会奏效——它似乎可以避免构建中间对象。 - Brent Bradburn