什么更有效（特别是在 C 中）：移动数组元素或删除它并在新位置创建它？

Question

我正在学习C语言，在学习的过程中遇到了问题。

如何最好地对数组进行下一次更改：

我有一个结构数组。数组的大小变化非常频繁。特别是，我需要删除它的最后一个元素并创建一个具有 [0] 索引的新元素，更改结构的内容（结构包含坐标，我需要更改这些坐标）。

如果我将最后一个元素移动到 [0] 索引的位置，将数组的元素向前移动，会有什么不同吗？ g.，使用 memmove() 函数而不是删除最后一个元素并创建一个具有 [0] 索引的新元素（另外，据我所知，我在这里也需要使用 memmove() 将 1 个元素上的数组“压缩”到向前函数?)?

还是不重要？也许有更好的方法（特别是，我对 C 或 C++（更具体地说，C 子集）感兴趣）。

如果您需要任何说明，请告诉我，我会尽力解释得更详细。

感谢您的关注！

更新（为了更好地理解）。

数组包含包含 2 个整数变量 x 和 y（坐标）的结构。我应该用“array”做什么：

为了能够删除最后一个元素 - 这必须经常进行。
与 (1) 平行，我需要在开头添加一个新元素 - “head”。这就是问题的关键——我可以改变最后一个元素的坐标，将它移到开头。要么创建一个具有新结构的新元素，然后简单地删除最后一个元素。
另外，有时“array”会增加，即会添加一个新的结构。无论 (1) 和 (2) 点如何，都会发生这种情况。

Answer 1

您所描述的——数组两端的频繁操作——是双端队列的典型用例，或deque。 C++ 标准库有 std::deque<T>。在 C 中，您可以将双端队列实现为循环缓冲区。

假设您有一个固定大小的数组。除了大小，数组还有一个长度，即数组中有效值的数量。您现在可以在末尾压入和弹出元素：

[. . . . . . . .]       length = 0
[0 . . . . . . .]       push(arr, 0)      arr[length++] = 0
[0 1 . . . . . .]       push(arr, 1)      arr[length++] = 1
[0 1 2 . . . . .]       push(arr, 2)      arr[length++] = 2
[0 1 . . . . . .]       x = pop(arr)      x = arr[--length]0

现在，如果你想在前面添加或删除元素，你必须移动剩余的元素。循环缓冲区做一些不同的事情：当你在开始插入一个元素时，你从右边填充“间隙”（点）并保留开始索引。这样，数组换行：

[0 1 2 3 4 . . .]       ^: start index
 ^                                           // seen as:
[0 1 2 3 4 . . a]       unshift(arr, a)      // [a, 0, 1, 2, 3, 4]
               ^
[0 1 2 3 4 . b a]       unshift(arr, b)      // [b, a, 0, 1, 2, 3, 4]
             ^
[0 1 2 3 4 . . a]       x = shift(arr)       // == b
               ^

在此缓冲区中，您将不会直接使用 arr[i] 访问元素。您需要访问将在幕后执行 wrappig 逻辑的函数。

您可以让双端队列随着它的增长分配更多的内存。下面是一个示例实现。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>



typedef struct Queue Queue;
typedef unsigned Item;

#define enforce(COND, MSG) \
    if (COND); else exit((fprintf(stderr, "Fatal :" MSG "\n"), 1))

struct Queue {
    size_t length;
    size_t size;
    size_t start;
    Item *item;
};

/* 
 *      Create queue object
 */
Queue *queue_create(void)
{
    Queue *q = calloc(1, sizeof(*q));

    return q;
}

/*
 *      Destroy queue object
 */
void queue_destroy(Queue *q)
{
    if (q) {
        free(q->item);
        free(q);
    }
}

/* 
 *      Internal: re-allocate
 */
static void queue_grow(Queue *q)
{
    if (q->length >= q->size) {
        size_t old_size = q->size;
        
        q->size = (old_size) ? 2 * old_size : 16;
        
        q->item = realloc(q->item, q->size * sizeof(*q->item));        
        enforce(q->item, "Allocation failed!");
            
        memcpy(q->item + q->start + old_size,
               q->item + q->start,
               (old_size - q->start) * sizeof(*q->item));
        q->start += old_size;
    }
}

/*
 *      Add an item at the end
 */
void queue_push(Queue *q, Item item)
{
    queue_grow(q);
    
    q->item[(q->start + q->length++) % q->size] = item;
}

/*
 *      Remove the item at the end
 */
Item queue_pop(Queue *q)
{
    if (q->length) {
        return q->item[(q->start + --q->length) % q->size];
    }
    
    enforce(0, "Queue underflow!");
    
    return 0;
}

/*
 *      Add an item at the front
 */
void queue_unshift(Queue *q, Item item)
{
    queue_grow(q);
    
    if (q->start) {
        q->start--;
    } else {
        q->start = q->size - 1;
    }
    
    q->length++;
    q->item[q->start] = item;
}

/*
 *      Remove the item from the front
 */
Item queue_shift(Queue *q)
{
    Item item = q->item[q->start];
    
    q->length--;
    q->start++;
    if (q->start == q->size) q->start = 0;
    
    return item;
}

/*
 *      Get the item at index (Neg. index counts from the end)
 */
Item queue_at(const Queue *q, long long index)
{
    if (index < 0) index += q->length;

    enforce(0 <= index && index < q->length, "Bad index!");
    
    return q->item[(q->start + index) % q->size];    
}

/*
 *      Get a pointer to the item at index
 */
Item *queue_ref_at(const Queue *q, long long index)
{
    if (index < 0) index += q->length;

    if (index < 0 || index >= q->length) return 0;
    
    return (Item *) &q->item[(q->start + index) % q->size];    
}

/*
 *      Get the length of the queue
 */
size_t queue_length(const Queue *q)
{
    return q->length;
}



/*
 *      (Rather silly) Example
 */
int main(void)
{
    Queue *q = queue_create();
    
    unsigned sum = 0;
    unsigned i;
    
    for (i = 0; i < 1000; i++) {
        queue_push(q, i);
    }
    
    for (i = 0; i < 100; i++) {
        queue_unshift(q, -(1 + i));
    }
    
    printf("start: %d\n", queue_at(q, 0));      // -100
    printf("end: %d\n", queue_at(q, -1));       // 999
    
    unsigned *ref = queue_ref_at(q, -1);
    
    if (ref) *ref = 10000;
    printf("end: %d\n", queue_pop(q));    
    
    while (queue_length(q)) {
        sum += queue_shift(q);
    }

    printf("sum: %d\n", sum);
    
    queue_destroy(q);

    return 0;
}

什么更有效（特别是在 C 中）：移动数组元素或删除它并在新位置创建它？

What is more effective (in particular, in C): moving an array element or deleting it and creating it in a new place?

c

arrays

dynamic-arrays