调整数组大小 - 两个执行块之间的差异？

I have a function which grows an array when trying to add an element if it is full. Which of the execution blocks is better or faster?

我有一个函数,当尝试添加一个元素时,它会生成一个数组。哪个执行块更好或更快?

I think my second block (commented out) may be wrong, because after doubling my array I then go back and point to the original.

我认为我的第二个块(注释掉了)可能是错误的,因为在我的数组加倍之后我会回去指向原始数据块。

When creating arrays does the compiler look for a contiguous block in memory which it entirely fits into? (On the stack/heap? I don't fully understand which, though it is important for me to learn it is irrelevant to the actual question.)

在创建数组时,编译器是否在内存中寻找一个完全适合的连续块? (在堆栈/堆上?我不完全理解哪些,尽管对我来说重要的是学习它与实际问题无关。)

If so, would this mean using the second block could potentially overwrite other information by overwriting adjacent memory? (Since the original would use 20 adjacent blocks of memory, and the latter 40.)

如果是这样,这是否意味着使用第二个块可能会通过覆盖相邻内存来覆盖其他信息? (因为原来会使用20个相邻的内存块,而后者是40个。)

Or would it just mean the location of elements in my array would be split, causing poor performance?

或者它只是意味着我的数组中的元素的位置将被拆分,导致性能不佳?

void Grow()
{
  length *= 2; // double the size of our stack

  // create temp pointer to this double sized array
  int* tempStack = new int[length];

  // loop the same number of times as original size
  for(int i = 0; i < (length / 2); i++) 
  {
    // copy the elements from the original array to the temp one
    tempStack[i] = myStack[i]; 
  }

  delete[] myStack; //delete the original pointer and free the memory
  myStack = tempStack; //make the original point to the new stack

  //Could do the following - but may not get contiguous memory block, causing
  // overwritten >data
#if 0
  int* tempStack = myStack; //create temp pointer to our current stack
  delete[] myStack; //delete the original pointer and free memory
  myStack = new int[length *= 2]; //delete not required due to new?
  myStack = tempStack;
#endif
}

3 个解决方案

#1

The second block wouldn't accomplish what you want at all.

第二个块根本无法实现你想要的。

When you do

当你这样做

myStack = new int[length *= 2];

then the system will return a pointer to wherever it happens to allocate the new, larger array.

然后系统将返回一个指针,指向分配新的更大数组的地方。

You then reassign myStack to the old location (which you've already de-allocated!), which means you're pointing at memory that's not allocated (bad!) and you've lost the pointer to the new memory you just allocated (also bad!).

然后你将myStack重新分配给旧位置(你已经取消分配!),这意味着你指的是未分配的内存(坏!)并且你丢失了指向你刚刚分配的新内存的指针(也不好!)

Edit: To clarify, your array will be allocated on the heap. Additionally, the (new) pointer returned by your larger array allocation (new int[foo]) will be a contiguous block of memory, like the old one, just probably in a different location. Unless you go out of bounds, don't worry about "overwriting" memory.

编辑:为了澄清,您的数组将在堆上分配。此外,较大的数组分配(new int [foo])返回的(新)指针将是一个连续的内存块,就像旧的一样,可能位于不同的位置。除非你走出界限,否则不要担心“覆盖”内存。

#2

Your second block is incorrect because of this sequence:

由于这个顺序,你的第二个块是不正确的:

int* tempStack = myStack; //create temp pointer to our current stack
delete[] myStack; //delete the original pointer and free memory

tempStack and myStack and both simply pointers to the same block of memory. When you delete[] the pointer in the second line, you no longer have access to that memory via either pointer.

tempStack和myStack都只是指向同一块内存的指针。当您删除第二行中的[]指针时,您无法再通过任一指针访问该内存。

Using C++ memory management, if you want to grow an array, you need to create a new array before you delete the old one and copy over the values yourself.

使用C ++内存管理,如果要增长数组,则需要先创建一个新数组,然后再删除旧数组并自行复制值。

That said, since you are working with POD, you could use C style memory management which supports directly growing an array via realloc. That can be a bit more efficient if the memory manager realizes it can grow the buffer without moving it (although if it can't grow the buffer in place, it will fall back on the way you grow your array in your first block).

也就是说,既然你正在使用POD,你可以使用C风格的内存管理,它支持通过realloc直接增长数组。如果内存管理器意识到它可以在不移动缓冲区的情况下增长缓冲区,那么这可能会更高效一些(尽管如果它不能增加缓冲区,它将会回退到你在第一个块中增长阵列的方式)。

C style memory management is only okay for arrays of POD. For non-POD, you must do the create new array/copy/delete old array technique.

P风格的内存管理仅适用于POD阵列。对于非POD,您必须执行create new array / copy / delete旧数组技术。

#3

This doesn't exactly answer your question, but you shouldn't be doing either one. Generally new[] or delete[] should be avoided in favor of using std::vector. new[] is hard to use because it requires explicit memory management (if an exception is thrown as the elements are being copied, you will need to catch the exception and delete the array to avoid a memory leak). std::vector takes care of this for you, automatically grows itself, and is likely to have an efficient implementation tuned by the vendor.

这并不完全回答你的问题,但你不应该做任何一个。通常应该避免使用new []或delete []来支持使用std :: vector。 new []很难使用,因为它需要显式的内存管理(如果在复制元素时抛出异常,则需要捕获异常并删除数组以避免内存泄漏)。 std :: vector为您处理这个问题,自动增长,并且很可能有一个由供应商调整的高效实现。

One argument for using explicit arrays is to have a contiguous block of memory that can be passed to C functions, but that also can be done with std::vector for any non-pathological implementation (and the next version of the C++ standard will require all conforming implementations to support that). (For reference, see http://www.gotw.ca/publications/mill10.htm by Herb Sutter, former convener of the ISO C++ standards committee.)

使用显式数组的一个参数是拥有一个可以传递给C函数的连续内存块,但是对于任何非病态实现也可以用std :: vector完成(并且下一版本的C ++标准将需要所有符合要求的实现以支持)。 (供参考,请参阅ISO C ++标准委员会前召集人Herb Sutter的http://www.gotw.ca/publications/mill10.htm。)

Another argument against std::vector is the weirdness with std::vector<bool>, but if you need that you can simply use std::vector<char> or std::vector<int> instead. (See: http://www.gotw.ca/publications/mill09.htm)

反对std :: vector的另一个论点是std :: vector 的奇怪之处,但如果你需要它,你可以简单地使用std :: vector 或std :: vector 。 (见:http://www.gotw.ca/publications/mill09.htm)

#1