0

Решил разобраться с структурой данных vector и посмотреть как написать это на чистом Си. Нашел пример, который работает на int, double, char*. Решил попробовать с структурами и вот что получается:

 typedef struct{
    void** data;
    int size;
    int capacity;
    size_t element_size;
}Cvector;

Это структура вектора.

    void cvectorInit(Cvector* v, size_t dataSize){
    v->capacity = CVECTOR_INIT_CAPACITY;
    v->size = 0;
    v->element_size = dataSize;
    v->data = (void **) malloc(CVECTOR_INIT_CAPACITY  * sizeof(void *));
}

Это создание вектора и выделение памяти для массива. Вопрос вот в чем: Если просто создавать структуры и закидывать их в этот "вектор" - то все хорошо. Если их начинать сортировать по полю типа int начинается непонятная (для меня) вещь.

При сортировке с помощью qsort

    int compare_f(const void* a, const void* b){
    const Some *tmpa;
    const Some *tmpb;
    tmpa = a;
    tmpb = b;
    return tmpa->id - tmpb->id;
}

    int main(){
    /*

    */

    struct Some **arr = ((struct Some**)vec.data);

    qsort(*arr, getCvectorSize(&vec), sizeof(Some), compare_f);

    /*
    */
    return 0;
    }

при установленном "CVECTOR_INIT_CAPACITY = 24" Все сортируется, проверял на 10000 элементов, но если поменять на 4, тогда никакой сортировки нет, и все вылезает за пределы массива (ну я так понял), значения идут от большого минуса (-1564469376) и до такого же большого плюса. Объясните мне в чем дело. Если вручную, в функции malloc, указать вместо sizeof(void *) любое другое значение - ничего не меняется. От чего зависит сортировка?

UPD:

    void cvectorPush(Cvector* v, void* data){

    if(v->size >= v->capacity){
        cvectorResize(v, v->capacity + (v->capacity / 2) + 1);
    }

    if(!(v->data[v->size] = (void*) malloc(v->element_size))){
    }
    memcpy(v->data[v->size], data, v->element_size);


    v->size++;

}

void cvectorResize(Cvector* v, int newCap){
    v->capacity = newCap;
    void** new_data = realloc(v->data, newCap * sizeof(void *));
    if(new_data == NULL){
    printf("%s", "Something wrong");
    }
    v->data = new_data;
}

Как начальный размер массива может влиять на распределение памяти? Какая разница когда сделать realloc через 4 элемента или через 24?

2
  • Не пойдет, т. к. размер элемента массива(выделяется в cvectorPush()) больше чем размер указателя. И инициализируется вектор вот так: cvectorInit(&vec, sizeof(Some)); 5 янв 2020 в 11:55
  • Именно так, а элемент массива (Не вектора) : v->data[v->size] = (void*) malloc(v->element_size) 5 янв 2020 в 12:57

1 ответ 1

0

Ошибка в функции-компараторе, туда передаются указатели на указатели элементов. В комментарии было правильно сказано об использовании sizeof(Some *) и передачи массива. Вот так выглядит вызов функции:

qsort(vec.data, getCvectorSize(&vec), sizeof(Some *), compare_f);

А вот так компаратор:

  int compare_f(const void* a, const void* b){                                                                                                                               
      const Some** tmpa = (void *)a;                                                                                                                                         
      const Some** tmpb = (void *)b;                                                                                                                                         
      /* tmpa = a; */                                                                                                                                                        
      /* tmpb = b; */                                                                                                                                                        
      return (*tmpa)->id - (*tmpb)->id;                                                                                                                                      
  }

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.