使用 C

Question

我想“回到基础”并尝试编写一个 C 向量实现。 它使用 void* 来存储数据，我尝试稍微模仿一下 C++ 计数器部分。

我在删除元素时遇到困难。确切地说，向量的大小似乎与删除多个元素后的预期不匹配。

这里是擦除函数的实现：

typedef void* vector_iterator;

vector_iterator vector_begin(vector* vec) {
    return vec->data;
}

vector_iterator vector_end(vector* vec) {
    return ((unsigned char*)vec->data) + ((vec->element_size * (vec->size+1))); // "past the last element"
}

void vector_erase(vector* vec, vector_iterator iterator) {
    assert(iterator >= vector_begin(vec));
    assert(iterator < vector_end(vec));
    assert(((uintptr_t)iterator - (uintptr_t)vector_begin(vec)) % vec->element_size == 0);
    unsigned char* dest = (unsigned char*)iterator;
    unsigned char* src = dest + vec->element_size; // src is the element erased element + 1, since we want to pull all objects forward
    size_t bytes_to_copy= (unsigned char*)vector_end(vec) - (unsigned char*)src - vec->element_size;
    memcpy(dest, src, bytes_to_copy); // copy all elements from (iterator +1) forward
    vec->size--;
}

vector_iterator vector_iterator_offset(vector_iterator iterator,vector* vec, ptrdiff_t offset) {
    return (unsigned char*)iterator + (vec->element_size * offset);
}

擦除的用法是这样使用的。

vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase the second element

当我删除 3 个元素时，报告的向量大小是正确的，但我的循环打印 size+1 个元素。

    vector* vec = vector_create_capacity(sizeof(char), 10);
    //test for push back
    for(char i = 'A'; i < 'A'+10; ++i) {
        vector_push_back(vec, &i);
    }
    
    //...//
    
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'C'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'D'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);

    vector_erase(vec, vector_iterator_offset(vector_begin(vec),vec,2)); // erase 'E'
    fprintf(stdout, "Size: %zu\n",vector_size(vec));
    fflush(stdout);
    
    it = vector_begin(vec);
    for(;it != vector_end(vec); (it = vector_iterator_offset(it, vec, 1))) {
        
        char data = *(char*)it;
        fprintf(stdout,"%c\n", data);
        fflush(stdout);
    }
    fprintf(stdout,"%zu",vector_size(vec));
    fflush(stdout);
    //8 printed letters instead of 7 with double 'J'?
    vector_destroy(vec);

最后的输出是

A
B
F
G
H
I
J
J

Godbolt demo，因为代码很长

我的vector_end(vec)不正确还是擦除不正确？

Answer 1

 // "past the last element"

但是

size + 1

指向最后一个元素之后的 next 元素之后的字节。所以它不是“最后一个元素之后”，而是“一加最后一个元素之后的字节”。

当您位于

vec->data + vec->element_size * vec->size

时，您已经指向最后一个元素之后的字节。不

+1

，大小已经是向量中元素的数量，并且数组索引从0开始。

我的vector_end(vec)不正确还是擦除不正确？

是的，vector_end 令人困惑。只是：

vector_iterator vector_end(vector* vec) {
    return ((char *)vec->data) + vec->element_size * vec->size; // "past the last element"
}

然后你自然会复制结束和开始之间的范围。

 size_t bytes_to_copy = (unsigned char*)vector_end(vec) - (unsigned char*)src;

我的 godbolt 链接 https://godbolt.org/z/z5TvWzM7T .

---

无主观化妆品：

• typedef 指针对我来说仍然是一个危险信号。
  • 我会这样做

    typedef struct { vector *parent; void *pos; } vector_iterator

    而不是每次传递两个参数。
  • 或至少

    typedef struct { void *pos; } vector_iterator;

    这样我就可以进行基本的类型检查
  • 但是有了

    void *

    ，你会得到很好的

    !=

    比较，所以我明白拥有它很好
• 如果您不打算取消引用它，只需使用

  char *

  来表示字节，无需键入

  unsigned

  。
• 这么多

  (

  )

  ，有些地方不需要

• #include "assert.h"

  ->

  #include <assert.h>

• vector_create_capacity

  需要为向量本身分配内存两次吗？它可以按值返回自身

  vector vector_create_capacity(...)

  。
• 有些地方缺少 NULL 分配错误检查，请参阅

  gcc -fanalyzer

  抱怨