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

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更昂貴，以便將其擴展到更大的內存分配。