初始化最小容量为cap

每次达到cap则扩容成两倍cap

对于一个空的数组，不断的加入元素直到n个，扩容的次数应该是x次，$cap\times 2^x \ge n \Rightarrow x\approx O(log_2\frac{n}{cap})$

如果申请大小为k的内存，时间复杂度是$O(k)$的话。

第$i$次申请内存的大小是$cap\times 2^i$，申请$x\approx O(log_2\frac{n}{cap})$次，总内存大小是$cap\times(2^0+2^1+\cdots+2^x)\Rightarrow cap\times(2^{x+1}-1)\Rightarrow cap\times(2\frac{n}{cap}-1)\approx O(n)$

扩容后，原有连续的内存首地址会发生变化，所以元素内不能存元素的地址，否则扩容后元素内保留的是野指针。

// ==================== vector =======================
typedef struct cntnode {
    unsigned long long key;
    struct cntnode* prev;
    struct cntnode* next;
} cntnode;

// #define VEC_VT cntnode* 直接替换，连续声明变量失效
typedef cntnode* VEC_VT; 

typedef struct {
    VEC_VT* data;      
    int size;   
    int cap;
} vector;

vector* vc_new(int size) {
    vector* vec = (vector*)malloc(sizeof(vector));
    assert(vec != NULL);
    
    int cap = 16;
    while (size>cap) cap<<=1;
    vec->data = (VEC_VT*)malloc(cap * sizeof(VEC_VT));
    assert(vec->data != NULL);
    
    memset(vec->data, 0, size*sizeof(VEC_VT));
    vec->size = size;
    vec->cap = cap;
    return vec;
}

void vc_del(vector* v) {
    free(v->data);
    free(v);
}

void vc_reverse(vector* vec) {
    int l = 0, r = vec->size-1;
    while (l<r) {
        VEC_VT t = vec->data[l];
        vec->data[l] = vec->data[r];
        vec->data[r] = t;
        l++; r--;
    }
}

void vc_push_back(vector* vec, VEC_VT value) {
    if (vec->size >= vec->cap) {
        VEC_VT* new_data = (VEC_VT*)realloc(vec->data, 2 * vec->cap * sizeof(VEC_VT));
        // printf("before %p, after %p\\n", vec->data, new_data);
        // 地址会发生变化，所以元素内不能存元素的地址，否则扩容后会出现野指针
        assert(new_data != NULL);
        vec->data = new_data;
        vec->cap <<= 1;
    }
    vec->data[vec->size] = value;
    vec->size++;
}

void vc_pop_back(vector* vec) {
    assert(vec->size>0);
    vec->size--;
}

VEC_VT vc_get(vector* vec, size_t index) {
    assert(vec && index<vec->size);
    return vec->data[index];
}

void vc_set(vector* vec, int index, VEC_VT value) {
    assert(vec && index<vec->size);
    vec->data[index] = value;
}

void vc_swap(VEC_VT* a, VEC_VT* b) {
    VEC_VT t = *a;
    *a = *b;
    *b = t;
}

typedef int (*VCmp)(VEC_VT, VEC_VT);

// modify
int vc_cmp(VEC_VT a, VEC_VT b) {
    // return a-b;
    return -1;
}

void vc_sort(vector* nums, int left, int right, VCmp cmp) { // [left, right)
    if (left + 1 >= right) return ;
    int m = left+right>>1;
    vc_sort(nums, left, m, cmp);
    vc_sort(nums, m, right, cmp);
    vector* mg = vc_new(0);
    int p1 = left, p2 = m;
    while (p1<m && p2<right) {
        if (cmp(nums->data[p1], nums->data[p2])<0) { // cmp(a, b)<0 a<b
            vc_push_back(mg, nums->data[p1++]);
        } else {
            vc_push_back(mg, nums->data[p2++]);
        }
    }
    while (p1<m) {
        vc_push_back(mg, nums->data[p1++]);
    }
    while (p2<right) {
        vc_push_back(mg, nums->data[p2++]);
    }
    for (int i=left; i<right; i++) {
        nums->data[i] = mg->data[i-left];
    }
    vc_del(mg);
}

// modify
void vc_print(vector* vec) {
    // your code
    printf("vector size:%d, cap:%d\\n", vec->size, vec->cap);
    for (int i=0; i<vec->size; i++) {
        VEC_VT ed = vec->data[i], cur = ed->next;
        printf("idx:%d addr:%p pre:%llu nxt:%llu \\nlru order:", i, ed, GET_PREV(ed->key), GET_NEXT(ed->key));
        while (ed != cur) {
            printf(" %llu", cur->key);
            cur = cur->next;
        }
        printf("\\n");
    }
}