Как в vector на си вставлять элемент на конкретное место?

Question

[pshevnin]

Добрый день. Есть динамический массив реализованный с помощью vector на Си.

int vector_push_back(vector_t *v, const void *item) {
    if (!v || !item) {
        return 0;
    }

    if (v->count == v->capacity) {
        if (!vector_realloc(v, v->capacity * VECTOR_SIZE_MULT)) {
            return 0;
        }
    }

    memcpy((void *)((char *)v->data + (v->count * v->item_size)), item, v->item_size);
    v->count++;

    return 1;
}

Это функция добавления нового элемента. Как сделать так, чтобы я мог вставлять новые элементы на конкретное место массива с помощью индекса? Спасибо

Answer 1

[Wataru]

Сначала через memmove надо сдвинуть элементы с i по count-1 на позиции i+1...count. Потом чуть изменить memcopy, чтобы записать новв элемент на позицию i, а не count.

Comments

[pshevnin]

Насколько я понимаю, если сдвинуть элементы через memmove, то они изменят свои позиции в массиве? Мне нужно, чтобы элементы были на своих местах всё время, чтобы я мог обратиться к любому из них по индексу. В случае добавления элемента на место указанное индексом, я подразумеваю, что это место ничем не занято.

[pshevnin]

Dmitrii, ага, теперь понятно.

[pshevnin]

Wataru, не подскажете как решить проблему того, что некоторые добавляемые индексы выходят за пределы количества элементов массива? То есть мне нечего двигать memmove'ом, а в конце массива получится каша из разных индексов, бОльших чем длина массива

[Wataru]

pshevnin, Т.е. у вас массив на 10 элементов и вам надо вставить на индекс 100?

[pshevnin]

Wataru, У меня динамический массив. Он нужен мне для того, чтобы считывать элементы формата: "id,source,target,capacity,isvalid" из документа. Мне важно добавлять эти элементы в массив под ID, который указан в документе. Элементы в документе не упорядочены. Грубо говоря, да у меня есть массив сначала на 10 элементов, а мне нужно вставить на индекс 100. Расширяться мой массив умеет, но не умеет вставлять элементы в любое место. Я воспользовался memmove по Вашему совету, но пришёл к выводу, что если индекс добавляемого элемента будет больше, чем количество элементов в массиве, то работать он будет некорректно

[Wataru]

pshevnin, Нет у вас не массив тогда, а словарь. Вам надо реализовывать какое-то бинарное самобалансирующееся дерево, или хеш-таблицу.

Если хотите делать массивом, то тогда вам не надо ничего сдвигать memove. Я то думал что вы вставляете элементы по порядковому номеру, а не абсолютному индексу. В вашем случае вам придется увеличивать массив так, чтобы capacity было больше вставляемого id. Может придется в цикле увеличивать массив в VECTOR_SIZE_MULT раз, или высчитывать размер массива в зависимости от id.

Но тут может быть большая проблема с тем, что если id расположенны не плотно, то у вас будет очень большое потребление памяти (вот введу я вам id=2000000000 - вам придется выделить пару десятков гигабайт памяти). Да и работать это будет на порядки медленнее словаря.

[pshevnin]

Wataru, Элементы в документе расположены не по порядку, но очень плотно, то есть после прохождения всего документа, пустых мест в массиве не будет. Так же не будет и экстремально больших индексов. И, я полагаю, что преподаватель подразумевал использование именно динамического массива

[Wataru]

pshevnin, Ну тогда, да, ваш подход будет работать. Просто увеличивайте массив, чтобы все индексы существовали. Не забудьте через memset затереть новую область нулями.

[pshevnin]

Wataru, Спасибо