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

до c ++ и вектора / списков, как они увеличивали размер массивов, когда им нужно было хранить больше данных?

Ответы на вопрос(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);

подобный вектору. Динамические массивы настолько распространены, что приятно абстрагировать управление памятью как можно больше. Типичная реализация 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, поэтому код более общий. Во всяком случае, такие вещи реализованы во многих проектах на Си. Видетьhttp://codingrecipes.com/implementation-of-a-vector-data-structure-in-c для примера векторной реализации в C.

 Warlike Chimpanzee04 нояб. 2017 г., 22:31
Ссылка не работает, смотритеgist.github.com/EmilHernvall/953968/... за то, что кажется популярной реализацией
 Kai13 нояб. 2016 г., 17:15
Здесь вы, кажется, создаете указатель на переменную данных вашей структуры, но для многих других векторных реализаций онлайн я видел, что переменная данных структуры содержалась двойным указателем. В чем разница между этими двумя способами?
Решение Вопроса

Типичный код C выглядит так:

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

oldMem = newMem;

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

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

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

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

 Steve Jessop14 янв. 2011 г., 19:26
А такжеnewSize как правило, должен быть кратным старому размеру, чтобы получить амортизированную O (1) временную сложность для операции добавления одного элемента. То есть для предотвращения частых перераспределений. Таким образом, вы записываете размер и емкость отдельно, так же, какvector делает.
 doug6553617 янв. 2013 г., 04:41
@ Крис стандарта C89, который я имею, говорит: «4.10.3.2 Свободная функция вызывает освобождение пространства, на которое указывает ptr, то есть делает его доступным для дальнейшего распределения.Если ptr является нулевым указателем, никаких действий не происходит."
 Kaije14 янв. 2011 г., 19:17
вау круто, так что же такое эквивалент C ++? например malloc = new, free = delete, realloc =?
 Charles Salvia14 янв. 2011 г., 19:20
@ybungalobill, эм ...vector::clear() на самом деле не имеет никакого отношения кfree.
 Beanz14 янв. 2011 г., 19:24
ни один из них не является правильным. new вызывает создание объекта, а также выделение и удаление памяти, вызывает удаление объекта, а также возврат памяти в систему. realloc может использоваться для выделения, освобождения и копирования памяти, однако он не создает объекты в смысле слова на языке c ++. Также помните, что malloc, free и realloc не ведут себя так же, как new и delete. malloc может вернуть ноль для неудачного размещения, тогда как new выдаст исключение. Также свободно используется для нулевого указателя, это приведет к разыменованию нулевого указателя, в то время как удаление для нулевого указателя ничего не изменит

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

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

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);
}

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

 Michael Smith14 янв. 2011 г., 19:55
Написал это за 30 минут, без гарантии.

Ваш ответ на вопрос