是否有可能在其本身之前有效地重新分配数据？

Question

我在此示例代码来说明我的问题：

/** 
* begin  end 
* v   v 
* XXXXXXXXXXXXXXXX 
*^
* data 
* [===========] size 
* [==============] capacity 
*/ 
typedef struct list_t 
{ 
    int *data; 
    int *begin; 
    int *end; 
    size_t size; 
    size_t capacity; 
} list_t; 


/** 
* begin  end 
* v   v 
* XXXXXXXXXXXXXXXX 
*^
* old_data 
* 
* becomes 
* 
* begin  end 
* v   v 
* XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 
*^
* data 
*/ 
void reserve_back(list_t *this) { 
    int *old_data = this->data; 

    this->capacity *= 2; 
    this->data = (int *) realloc(this->data, this->capacity * sizeof(int)); 

    if (old_data != this->data) { 
     this->begin = this->begin - old_data + this->data; 
     this->end = this->end - old_data + this->data; 
    } 
} 

/** 
* begin  end 
* v   v 
* XXXXXXXXXXXXXXXX 
*^
* old_data 
* 
* becomes 
* 
*     begin  end 
*     v   v 
* XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 
*^
* data 
*/ 
void reserve_front(list_t *this) { 
    int *old_data = this->data; 

    this->data = (int *) malloc(this->data, this->capacity * sizeof(int) * 2); 
    memmove(this->data + this->capacity, old_data, this->capacity * sizeof(int)); 
    free(old_data); 

    this->capacity *= 2; 
    this->begin = this->begin - old_data + this->data; 
    this->end = this->end - old_data + this->data; 
} 

list_t基本上是一个双端动态阵列上两端在恒定的时间，以及通常的随机接入提供推入和弹出操作。

当我需要增加后面的容量时，我可以使用realloc来重新分配数据块，而realloc只在必要时移动数据。然而，为了增加前端的容量，我不得不每次都移动数据，这在大型列表中可能变得非常沉重。

当已经分配的数据之前有可用内存时，是否有任何方法可以在恒定时间内进行这种重新分配？

Answer 1

总之，没有。 （除非你编写自己的内存分配器，并且如果你尝试了，你很快就会明白为什么它没有在公共库分配器中实现。）

一般来说，实现双端队列（双端队列）的最好方法是将数据分段保存，而不是试图保留一个连续的向量。只要段的大小合理，这与用于索引访问或迭代的单个连续缓冲区几乎一样快，并且可以更快地将数据添加到任一端。

分段表示法的一个缺点是，您无法将双端队列的内容传递给期望简单向量的函数。另一方面，如果你不需要经常这样做，那么你可能会对这样一个观察结果感到放心：制作一个deque的平面副本并不比复制vector更昂贵，以便将其扩展到更大的内存分配。