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

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) 的最佳方式是将数据分段保存，而不是试图保存一个连续的向量。只要段的大小合理，这几乎与用于索引访问或迭代的单个连续缓冲区一样快，并且向两端添加数据的速度更快。

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

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

Is it possible to efficiently reallocate data in front of itself?

c

memory-management

allocation

realloc