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ệp | Số kiểu hỗ trợ | Kích thước mã | Ghi chú |
|---|---|---|---|
| vecA.o | Mọi kiểu | 216 byte | Một bản duy nhất |
| vecB.o | 2 kiểu | 388 byte | int và double |
| vecB3.o | 3 kiểu | 524 byte | Thêm char |
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à esz | Macro sinh mã |
|---|---|---|
| An toàn kiểu | Không | Có, đầy đủ |
| Tốc độ đẩy phần tử | Chậm hơn khoảng 40 phần trăm | Nhanh hơn |
| Tốc độ duyệt | Chậm hơn nhiều, không vector hóa được | Nhanh, vector hóa được |
| Kích thước mã | Một bản cho mọi kiểu | Một bản cho mỗi kiểu |
| Gỡ lỗi | Dễ, mã bình thường | Khó, lỗi hiện trong macro |
| Kiểu quyết định lúc chạy | Được | Khô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ản | Không |
| Đọc mã lần đầu | Dễ | 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 TENDù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ử
- Cài
Vectheo cách A và dùng nó vớiintrồi với một struct. - Gọi
vec_dayvới sai kiểu và xác nhận trình biên dịch không cảnh báo gì. - Cài
DINH_NGHIA_VECTORvà gọi sai kiểu, so thông báo lỗi với trên. - Đo kích thước mã của cả hai cách với một, hai, ba kiểu.
- Đo tốc độ đẩy hai mươi triệu phần tử bằng cả hai cách trên máy bạn.
- Viết tệp mẫu
vec-mau.hvà 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.