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

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来重新分配数据 block ，而realloc只在需要时移动数据。 但是，为了增加前端的容量，我不得不每次都移动数据，这在大型列表中会变得非常繁重。

当在已分配数据之前有可用内存时，有没有办法在恒定时间内进行这种重新分配？

Answer 1

一句话，没有。 (除非您编写自己的内存分配器，如果您尝试这样做，您很快就会明白为什么它没有在公共(public)库分配器中实现。)

一般来说，实现双端队列 (deque) 的最佳方式是将数据分段保存，而不是试图保存一个连续的 vector 。只要段的大小合理，这几乎与用于索引访问或迭代的单个连续缓冲区一样快，并且向任一端添加数据的速度更快。

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