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

StackOverflow https://stackoverflow.com/questions/96579

  •  01-07-2019
  •  | 
  •  

题

我正在编写一个需要放置的内部循环 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];
    }
}
有帮助吗？

解决方案

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 值引用的功能（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));
    }
}

这样做确实意味着您必须创建自己的向量类。在这种情况下，它也使本应简单的示例变得复杂。但有时使用像这样的工厂函数可能会更好，例如，如果插入以其他值为条件，那么您就必须无条件地构造一些昂贵的临时函数，即使实际上并不需要它。

其他提示

C++0x 添加了新的成员函数模板 emplace_back 到 vector （依赖于可变参数模板和完美转发）完全摆脱任何临时变量：

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

澄清 Reserve() 响应：您需要将reserve() 与push_back() 结合使用。这样，就不会为每个元素调用默认构造函数，而是调用复制构造函数。您仍然会受到在堆栈上设置结构然后将其复制到向量的惩罚。另一方面，如果您使用

vect.push_back(MyStruct(fieldValue1, fieldValue2))

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

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

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

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

概括：你将无法使用 std::vector 来做到这一点。

呃...

尝试一下方法：

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

您看到的初始化可能是一个工件。

[编辑] 在对调整大小发表评论后，我修改了代码以添加调整大小行。调整大小有效地调用向量内对象的默认构造函数，但如果默认构造函数不执行任何操作，则不会初始化任何内容...我仍然相信这是一个工件（我第一次使用以下代码将整个向量归零：

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 ;
} ;

这可能会内联到您的代码中。

但无论如何，您应该使用分析器研究您的代码，以确保这段代码是您的应用程序的瓶颈。

使用 std::vector::reserve() 方法。它不会调整向量的大小，但会分配空间。

从您对其他海报的评论来看，您似乎只剩下 malloc() 和朋友了。Vector 不会让你拥有未构造的元素。

从您的代码来看，您似乎有一个结构向量，每个结构都包含 2 个整数。你可以使用 2 个整数向量吗？然后

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

现在您不必每次都为复制结构付费。

如果您确实坚持让元素未初始化并牺牲一些方法，例如 front()、back()、push_back()，请使用 numeric 中的 boost 向量。它甚至允许您在调用 resize() 时不保留现有元素...

您可以在元素类型周围使用包装类型，并使用不执行任何操作的默认构造函数。例如。：

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);

结构体本身是否需要位于连续的内存中，或者您可以使用 struct* 向量吗？

向量会复制添加到其中的任何内容，因此使用指针向量而不是对象向量是提高性能的一种方法。

我不认为 STL 是你的答案。您将需要使用 realloc() 推出您自己的解决方案。您必须存储一个指针以及元素的大小或数量，并使用它来查找在 realloc() 之后开始添加元素的位置。

int *memberArray;
int arrayCount;
void GetsCalledALot(int* data1, int* data2, int count) {
    memberArray = realloc(memberArray, sizeof(int) * (arrayCount + count);
    for (int i = 0; i < count; ++i) {
        memberArray[arrayCount + i].d1 = data1[i];
        memberArray[arrayCount + i].d2 = data2[i];
    }
    arrayCount += count;
}

我会做类似的事情：

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

  for (int i = 0; i < count; ++i) {
    memberVector.push_back(MyType(data1[i], data2[i]));
  }
}

您需要为存储在 memberVector 中的类型定义一个 ctor，但这是一个很小的成本，因为它将为您提供两全其美的效果；不会进行不必要的初始化，并且在循环期间不会发生重新分配。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top