高效调整动态数组的大小

Question

我有一个动态数组作为我的班级的一员。我试图找到一种有效的方式来调整它的大小，并保留所有的信息。我知道矢量可以很好地工作，但我想用动态数组来代替。

我的班级有一个动态数组类型unsigned _int8被称为数据。

以下可以接受吗？

unsigned _int8 * temp = data; 
data = new unsigned _int8[NewSize](); 

if(OldSize >= NewSize) 
{ 
    for(int i = 0; i < NewSize; i++) 
     data[i] = temp[i]; 
} 
else 
{ 
    for(int i = 0; i < OldSize; i++) 
     data[i] = temp[i]; 
} 

delete [] temp; 

或者我应该以不同的方式做到这一点？有什么建议么？

编辑

固定在我的例子错误，并改变焦炭为unsigned _int8。

编辑2

我不会经常重新分配，如果在所有。我希望功能在那里，以避免编写代码来创建新对象，并在需要时复制所有内容。

我写的课程是用于创建和保存位图（.bmp）图像。该数组只是保存文件字节。创建对象时，图像大小将（应该）已知。

Answer 1

由于阵列是使用POD (plain old data)类型，你可以用memcpy()，而不是代替循环：

unsigned _int8 *temp = new unsigned _int8[NewSize]; 

if (OldSize >= NewSize) 
    memcpy(temp, data, NewSize * sizeof(unsigned _int8)); 
else 
{ 
    memcpy(temp, data, OldSize); 
    memset(&temp[OldSize], 0, (NewSize-OldSize) * sizeof(unsigned _int8)); 
} 

delete[] data; 
data = temp; 

，或者至少使用std::copy()（POD的类型，std::copy()就像memcpy()，但对于非POD类型它采用循环使对象分配语义保留）：

unsigned _int8 *temp = new unsigned _int8[NewSize]; 

if (OldSize >= NewSize) 
    std::copy(data, &data[NewSize], temp); 
else 
{ 
    std::copy(data, &data[OldSize], temp); 
    std::memset(&temp[OldSize], 0, (NewSize-OldSize) * sizeof(unsigned _int8)); 
} 

delete[] data; 
data = temp; 

话虽这么说，你真的应该使用std::vector<unsigned _int8>代替。它为你处理这些细节。这种类型的数组管理是您必须在C中使用的，但如果您可以避免使用，则实际上不应该在C++中使用，而应该使用本机C++功能。

Answer 2

通过这样做，每次将新元素添加到数组中时，都必须调整其大小。 调整大小的操作是Θ（n），所以插入操作也变为Θ（n）。每次需要调整大小时，通常的过程是重复（或重复三次）数组大小，对此，调整大小操作仍然是Θ（n），但摊销的插入代价是Θ（1） 。

此外，通常容量与大小分开，因为容量是实现细节，而大小是数组接口的一部分。

而且您可能需要验证元素何时被移除，容量是否过大，如果是，请减小它，否则一旦变大，该空间将永远不会释放。

你可以看到更多关于它在这里： http://en.wikipedia.org/wiki/Dynamic_array

Answer 3

这种方法的问题是，你调整到刚需的大小。这意味着当你插入一个新元素时，所需要的时间会有很大变化。

因此，例如，如果您继续进行“push_back”类似的操作，那么您将一直重新分配。

另一种想法是分配额外的大小，以避免成本有关业绩

矢量例如分配额外的大小有一个amortisized redimensionning不断大量频繁的重新分配。

下面是exaplains它详细

向量中以STL使用这种方法要更effiicient的链接。

Amortized analysis of std::vector insertion