c++ - 在添加元素时使 vector 更高效

Question

我正在考虑使 vector 数据结构更高效。

假设它是针对某种通用数据类型 T...然后在向 vector 添加新元素时，当前 std::vector 所做的是重新分配一个全新的 n+1 个元素的内存块。

我想做什么...

我写了一个小程序:

#include<iostream>

using namespace std;

int main ()
{

    int *i,*j;
    i=new int;
    cout<<i;
    delete i;
    j=new int ;
    cout<<j;
    delete j;

        return 0;
}

两个内存位置相同...

现在我在想的是，首先我会像这样为通用数据类型分配内存:

T *temp=new T;

现在将 temp 的内存地址与 vector 的最后一个元素的地址进行比较......如果它们相差 sizeof (T) 那么我将自己添加新元素...... .else 以 std::vector 的方式做....

因此它减少了复制所有元素的成本...如果数据很大，那么这会产生显着差异......!!

请告诉我我是否在正确的轨道上......

Answer 1

我理解你的想法是

If new gives me back an address which is contiguous with the memory already held by the MyVector object, I will just use it without reallocating.

是的，这在理论上确实可行。然而，实际上，不可能获得这样一个连续的地址，因为分配器很可能会在它分配的 block 的开头存储一些内部数据(例如它的大小，或指向下一个 block 的指针，或其他)。

具体细节取决于您的标准库(以及最终的操作系统)使用的分配器，但这里有一个典型行为的示例。您调用 new T，其中 sizeof(T) 为 16(例如)。 operator new 在内部调用 malloc，这会调用操作系统的分配函数。该函数在地址 X 处分配 20 字节的内存。它在 X 的前 4 个字节中存储“16”，并将地址 X + 4 返回给 malloc，后者又将其返回给operator new 并将其添加到您的应用程序。所以你不可能获得连续的内存。