Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 30.228 phút đọc

Vector tổng quát: hai cách

Sau bài này bạn sẽ làm được

  • Cài vector tổng quát bằng con trỏ void và kích thước phần tử
  • Cài vector an toàn kiểu bằng macro sinh mã
  • So sánh hai cách trên năm tiêu chí và đo kích thước mã
  • Chọn cách phù hợp theo tình huống

Bạn muốn một vector dùng được với int, double và SinhVien. C cho bạn đúng hai cách, chúng đối lập nhau ở mọi mặt, và bài này đo cả hai thay vì đoán.

#Cách A: con trỏ void và kích thước

vec.h
#ifndef VEC_H
#define VEC_H

#include <stddef.h>

typedef struct {
    void  *d;         /* vung du lieu tho */
    size_t n;         /* so phan tu dang dung */
    size_t cap;       /* so phan tu da cap phat */
    size_t esz;       /* kich thuoc MOT phan tu */
} Vec;

void  vec_khoi_tao(Vec *v, size_t esz);
void  vec_giai_phong(Vec *v);

int   vec_day(Vec *v, const void *phan_tu);
void *vec_tai(const Vec *v, size_t i);       /* NULL neu ngoai vung */

#endif /* VEC_H */
vec.c
#include <stdlib.h>
#include <string.h>

#include "vec.h"

void vec_khoi_tao(Vec *v, size_t esz) {
    v->d = NULL;
    v->n = v->cap = 0;
    v->esz = esz;
}

void vec_giai_phong(Vec *v) {
    free(v->d);
    vec_khoi_tao(v, v->esz);
}

int vec_day(Vec *v, const void *phan_tu) {
    if (v->n == v->cap) {
        size_t c = v->cap ? v->cap * 2 : 4;

        if (c > SIZE_MAX / v->esz) return -1;      /* chong tran */

        void *t = realloc(v->d, c * v->esz);

        if (!t) return -1;

        v->d   = t;
        v->cap = c;
    }

    memcpy((char *)v->d + v->n * v->esz, phan_tu, v->esz);
    ++v->n;

    return 0;
}

void *vec_tai(const Vec *v, size_t i) {
    return i < v->n ? (char *)v->d + i * v->esz : NULL;
}
Dùng nó
Vec a;
vec_khoi_tao(&a, sizeof(int));

for (int i = 0; i < 100; ++i)
    if (vec_day(&a, &i) != 0) return 1;        /* PHAI truyen dia chi */

int *p = vec_tai(&a, 50);
printf("%d\n", p ? *p : -1);                   /* PHAI ep kieu ngam */

vec_giai_phong(&a);

#Cách B: macro sinh mã

vec-macro.h
#ifndef VEC_MACRO_H
#define VEC_MACRO_H

#include <stdlib.h>

#define DINH_NGHIA_VECTOR(T, ten)                                     \
    typedef struct { T *d; size_t n, cap; } ten;                      \
                                                                      \
    static inline void ten##_khoi_tao(ten *v) {                       \
        v->d = NULL;                                                  \
        v->n = v->cap = 0;                                            \
    }                                                                 \
                                                                      \
    static inline void ten##_giai_phong(ten *v) {                     \
        free(v->d);                                                   \
        ten##_khoi_tao(v);                                            \
    }                                                                 \
                                                                      \
    static inline int ten##_day(ten *v, T x) {                        \
        if (v->n == v->cap) {                                         \
            size_t c = v->cap ? v->cap * 2 : 4;                       \
            T *t = realloc(v->d, c * sizeof *t);                      \
                                                                      \
            if (!t) return -1;                                        \
                                                                      \
            v->d   = t;                                               \
            v->cap = c;                                               \
        }                                                             \
                                                                      \
        v->d[v->n++] = x;                                             \
                                                                      \
        return 0;                                                     \
    }

#endif /* VEC_MACRO_H */
Dùng nó
#include "vec-macro.h"

DINH_NGHIA_VECTOR(int,    VecInt)
DINH_NGHIA_VECTOR(double, VecDouble)

int main(void) {
    VecInt a;
    VecInt_khoi_tao(&a);

    for (int i = 0; i < 100; ++i)
        if (VecInt_day(&a, i) != 0) return 1;     /* truyen GIA TRI, khong phai dia chi */

    printf("%d\n", a.d[50]);                       /* truy cap TRUC TIEP, co kieu */

    VecInt_giai_phong(&a);

    return 0;
}
terminal
# Bốn lỗi ở trên giờ đều bị bắt
gcc -std=c11 -Wall -Wextra -c dung-sai.c
dung-sai.c:8:20: error: incompatible type for argument 2 of 'VecInt_day'
    8 |     VecInt_day(&a, 1.5);
      |                    ^~~
      |                    |
      |                    double

#Đo kích thước và tốc độ

terminal
# Kích thước mã: void* xử lý mọi kiểu, macro sinh mã cho từng kiểu
gcc -std=c11 -O2 -c vecA.c vecB.c vecB3.c && size vecA.o vecB.o vecB3.o
   text    data     bss     dec     hex filename
    216       0       0     216      d8 vecA.o
    388       0       0     388     184 vecB.o
    524       0       0     524     20c vecB3.o
TệpSố kiểu hỗ trợKích thước mãGhi chú
vecA.oMọi kiểu216 byteMột bản duy nhất
vecB.o2 kiểu388 byteint và double
vecB3.o3 kiểu524 byteThêm char
Mỗi kiểu thêm vào cách B tốn khoảng 136 byte mã nữa. Cách A không đổi.
terminal
# Tốc độ: hai mươi triệu lần đẩy phần tử int
gcc -std=c11 -O2 -o bench bench.c && ./bench
void* + esz : 0.069 giay
macro sinh ma: 0.049 giay

#Chọn cách nào

Tiêu chívoid * và eszMacro sinh mã
An toàn kiểuKhôngCó, đầy đủ
Tốc độ đẩy phần tửChậm hơn khoảng 40 phần trămNhanh hơn
Tốc độ duyệtChậm hơn nhiều, không vector hóa đượcNhanh, vector hóa được
Kích thước mãMột bản cho mọi kiểuMột bản cho mỗi kiểu
Gỡ lỗiDễ, mã bình thườngKhó, lỗi hiện trong macro
Kiểu quyết định lúc chạyĐượcKhông, phải biết lúc biên dịch
Một vector chứa nhiều kiểuĐược, nếu bạn tự quảnKhông
Đọc mã lần đầuDễPhải hiểu macro trước

Cách thứ ba: tệp mẫu include nhiều lần

vec-mau.h, không có header guard
/* Tep nay duoc include NHIEU LAN, moi lan voi mot T khac.
   KHONG co header guard, va do la co y. */

#ifndef T
#error "Phai dinh nghia T truoc khi include vec-mau.h"
#endif

#ifndef TEN
#error "Phai dinh nghia TEN truoc khi include vec-mau.h"
#endif

#define NOI_(a, b) a##b
#define NOI(a, b)  NOI_(a, b)

typedef struct { T *d; size_t n, cap; } TEN;

static inline void NOI(TEN, _khoi_tao)(TEN *v) {
    v->d = NULL;
    v->n = v->cap = 0;
}

static inline int NOI(TEN, _day)(TEN *v, T x) {
    if (v->n == v->cap) {
        size_t c = v->cap ? v->cap * 2 : 4;
        T *t = realloc(v->d, c * sizeof *t);

        if (!t) return -1;

        v->d   = t;
        v->cap = c;
    }

    v->d[v->n++] = x;

    return 0;
}

#undef NOI
#undef NOI_
#undef T
#undef TEN
Dùng nó
#define T   int
#define TEN VecInt
#include "vec-mau.h"

#define T   double
#define TEN VecDouble
#include "vec-mau.h"

/* Uu diem so voi macro mot dong:
     - ma nam trong tep .h binh thuong, khong co dau gach cheo nguoc
     - trinh soan thao to mau va thut le dung
     - thong bao loi tro vao dong that trong vec-mau.h

   Nhuoc diem:
     - cu phap la, nguoi doc lan dau khong hieu
     - phai nho #undef moi macro o cuoi, neu khong thi lan include
       thu hai bao "T redefined"
     - la cach ma thu vien C++ dung truoc khi co template */

Tự làm thử

  1. Cài Vec theo cách A và dùng nó với int rồi với một struct.
  2. Gọi vec_day với sai kiểu và xác nhận trình biên dịch không cảnh báo gì.
  3. Cài DINH_NGHIA_VECTOR và gọi sai kiểu, so thông báo lỗi với trên.
  4. Đo kích thước mã của cả hai cách với một, hai, ba kiểu.
  5. Đo tốc độ đẩy hai mươi triệu phần tử bằng cả hai cách trên máy bạn.
  6. Viết tệp mẫu vec-mau.h và include nó hai lần với hai kiểu khác nhau.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Cách void * giữ kích thước phần tử trong struct, nên một bản mã chạy với mọi kiểu, nhưng mất hết kiểm kiểu.
  • Cách macro sinh một bộ hàm riêng cho mỗi kiểu, nên có kiểm kiểu đầy đủ và truy cập trực tiếp.
  • Đo thật: mỗi kiểu thêm vào cách macro tốn khoảng 136 byte mã, và đẩy phần tử nhanh hơn khoảng bốn mươi phần trăm.
  • Chênh lệch lớn nhất không nằm ở đẩy mà ở duyệt, vì cách macro vector hóa được còn cách void * thì không.
  • Nếu dự án chỉ dùng một hai kiểu thì đừng tổng quát hóa. Viết thẳng là câu trả lời đúng.