Как копировать вектор в c?

Question

В дни, предшествующие C++ и vector/lists, как они расширяли размер массивов, когда им нужно было хранить больше данных?

Answer 1

Типичный код C выглядит следующим образом:

void* newMem = realloc(oldMem, newSize); 
if(!newMem) 
{ 
    // handle error 
} 

oldMem = newMem; 

Обратите внимание, что если перераспределить терпит неудачу, то возвращается ноль, но старая память остается в силе, это типичное использование вызывает утечку памяти:

oldMem = realloc(oldMem, newSize); 
if(!oldMem) 
{ 
    // handle error 
} 

К сожалению это очень распространено;

Также обратите внимание, что в C++ vector/list нет ничего особенного. Подобные структуры могут быть реализованы в C, только синтаксис (и обработка ошибок) выглядят по-разному. Например, см. LodePNG's аналог std :: vector для C.

Answer 2

Многие проекты C в конечном итоге реализуют векторный API. Динамические массивы - такая общая потребность, что приятно абстрагировать управление памятью как можно больше. Типичная реализация C может выглядеть примерно так:

typedef struct dynamic_array_struct 
{ 
    int* data; 
    size_t capacity; /* total capacity */ 
    size_t size; /* number of elements in vector */ 
} vector; 

Тогда они будут иметь различные вызовы функций API, которые работают на vector:

int vector_init(vector* v, size_t init_capacity) 
{ 
    v->data = malloc(init_capacity * sizeof(int)); 
    if (!v->data) return -1; 

    v->size = 0; 
    v->capacity = init_capacity; 

    return 0; /* success */ 
} 

Тогда, конечно, вам нужна функция для push_back, insert, resize , и т. д., который будет звонить realloc, если size превышает capacity.

vector_resize(vector* v, size_t new_size); 

vector_push_back(vector* v, int element); 

Обычно, когда перераспределение необходимо, capacity удваивается, чтобы избежать перераспределить все время. Обычно это одна и та же стратегия, используемая внутренне: std::vector, за исключением, как правило, std::vector не будет звонить realloc из-за конструкции/уничтожения объекта C++. Скорее, std::vector может выделить новый буфер, а затем скопировать конструкцию/перемещение объектов (используя размещение new) в новый буфер.

Фактическая реализация вектора в C может использовать void* указатели в качестве элементов, а не int, поэтому код более общий. Во всяком случае, такого рода вещи реализуются во многих проектах C. См. http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c для примера реализации вектора в C.

Answer 3

Они начнут с сокрытия определения структуры, которая будет содержать элементы, необходимые для реализации. Затем предоставляем группу функций, которые будут манипулировать содержимым структуры.

Что-то вроде этого:

typedef struct vec 
{ 
    unsigned char* _mem; 
    unsigned long _elems; 
    unsigned long _elemsize; 
    unsigned long _capelems; 
    unsigned long _reserve; 
}; 

vec* vec_new(unsigned long elemsize) 
{ 
    vec* pvec = (vec*)malloc(sizeof(vec)); 
    pvec->_reserve = 10; 
    pvec->_capelems = pvec->_reserve; 
    pvec->_elemsize = elemsize; 
    pvec->_elems = 0; 
    pvec->_mem = (unsigned char*)malloc(pvec->_capelems * pvec->_elemsize); 
    return pvec; 
} 

void vec_delete(vec* pvec) 
{ 
    free(pvec->_mem); 
    free(pvec); 
} 

void vec_grow(vec* pvec) 
{ 
    unsigned char* mem = (unsigned char*)malloc((pvec->_capelems + pvec->_reserve) * pvec->_elemsize); 
    memcpy(mem, pvec->_mem, pvec->_elems * pvec->_elemsize); 
    free(pvec->_mem); 
    pvec->_mem = mem; 
    pvec->_capelems += pvec->_reserve; 
} 

void vec_push_back(vec* pvec, void* data, unsigned long elemsize) 
{ 
    assert(elemsize == pvec->_elemsize); 
    if (pvec->_elems == pvec->_capelems) { 
     vec_grow(pvec); 
    } 
    memcpy(pvec->_mem + (pvec->_elems * pvec->_elemsize), (unsigned char*)data, pvec->_elemsize); 
    pvec->_elems++;  
} 

unsigned long vec_length(vec* pvec) 
{ 
    return pvec->_elems; 
} 

void* vec_get(vec* pvec, unsigned long index) 
{ 
    assert(index < pvec->_elems); 
    return (void*)(pvec->_mem + (index * pvec->_elemsize)); 
} 

void vec_copy_item(vec* pvec, void* dest, unsigned long index) 
{ 
    memcpy(dest, vec_get(pvec, index), pvec->_elemsize); 
} 

void playwithvec() 
{ 
    vec* pvec = vec_new(sizeof(int)); 

    for (int val = 0; val < 1000; val += 10) { 
     vec_push_back(pvec, &val, sizeof(val)); 
    } 

    for (unsigned long index = (int)vec_length(pvec) - 1; (int)index >= 0; index--) { 
     int val; 
     vec_copy_item(pvec, &val, index); 
     printf("vec(%d) = %d\n", index, val); 
    } 

    vec_delete(pvec); 
} 

В дополнение к этому они достигли бы инкапсуляцию с использованием пустот * в месте VEC * для группы функций, а на самом деле скрыть определение структуры от пользователя, определяя его в модуль C, содержащий группу функций, а не заголовок. Также они скроют функции, которые вы считаете приватными, оставив их вне заголовка и просто прототипируя их только в модуле C.

Answer 4

Вы можете увидеть реализацию vc_vector:

struct vc_vector { 
    size_t count; 
    size_t element_size; 
    size_t reserved_size; 
    char* data; 
    vc_vector_deleter* deleter; 
}; 

... 

vc_vector* vc_vector_create_copy(const vc_vector* vector) { 
    vc_vector* new_vector = vc_vector_create(vector->reserved_size/vector->count, 
              vector->element_size, 
              vector->deleter); 
    if (unlikely(!new_vector)) { 
    return new_vector; 
    } 

    if (memcpy(vector->data, 
      new_vector->data, 
      new_vector->element_size * vector->count) == NULL) { 
    vc_vector_release(new_vector); 
    new_vector = NULL; 
    return new_vector; 
    } 

    new_vector->count = vector->count; 
    return new_vector; 
} 

Чтобы использовать его:

vc_vector* v1 = vc_vector_create(0, sizeof(int), NULL); 
for (int i = 0; i < 10; ++i) { 
    vc_vector_push_back(v1, &i); 
} 

// v1 = 0 1 2 3 4 5 6 7 8 9 

vc_vector* v2 = vc_vector_create_copy(v1); 

// v2 = 0 1 2 3 4 5 6 7 8 9 (copy of v1) 

// to get pointer to int: 

const int* v2_data = vc_vector_data(v1);