C โปรเจกต์: สร้าง dynamic array (vector)
C ไม่มี std::vector หรือ list ในตัว — โปรแกรม C จริงเกือบทุกตัวมี dynamic array เวอร์ชันของตัวเอง สร้างให้สะอาดและปลอดภัย
API ที่จะได้
IntVec *v = vec_new();
vec_push(v, 10);
vec_push(v, 20);
vec_push(v, 30);
int x;
vec_get(v, 1, &x); // x = 20
vec_set(v, 0, 99);
vec_pop(v, &x); // x = 30, len ลดเป็น 2
printf("len=%zu cap=%zu\n", vec_len(v), vec_cap(v));
vec_free(v);intvec.h
#ifndef INTVEC_H
#define INTVEC_H
#include <stddef.h>
typedef struct IntVec IntVec; // opaque — ผู้ใช้เข้า field ไม่ได้
IntVec *vec_new(void);
IntVec *vec_with_capacity(size_t cap);
void vec_free(IntVec *v);
int vec_push(IntVec *v, int value); // 0 = ok, -1 = OOM
int vec_pop(IntVec *v, int *out); // 0 = ok, -1 = ว่าง
int vec_get(const IntVec *v, size_t i, int *out); // -1 = index เกิน
int vec_set(IntVec *v, size_t i, int value);
size_t vec_len(const IntVec *v);
size_t vec_cap(const IntVec *v);
int vec_is_empty(const IntVec *v);
void vec_clear(IntVec *v); // len = 0 (ไม่คืน memory)
int vec_reserve(IntVec *v, size_t min_cap);
#endifintvec.c
#include "intvec.h"
#include <stdlib.h>
#include <stdint.h> // SIZE_MAX
#include <string.h>
#define INITIAL_CAP 8
#define GROWTH_FACTOR 2
struct IntVec {
int *data;
size_t len;
size_t cap;
};
IntVec *vec_with_capacity(size_t cap)
{
IntVec *v = malloc(sizeof(*v));
if (!v) return NULL;
v->len = 0;
v->cap = cap;
v->data = NULL;
if (cap > 0) {
if (cap > SIZE_MAX / sizeof(int)) { // cap * sizeof(int) จะ overflow
free(v);
return NULL;
}
v->data = malloc(cap * sizeof(int));
if (!v->data) {
free(v);
return NULL;
}
}
return v;
}
IntVec *vec_new(void)
{
return vec_with_capacity(0);
}
void vec_free(IntVec *v)
{
if (!v) return;
free(v->data);
free(v);
}
// ขยายให้จุอย่างน้อย min_cap
int vec_reserve(IntVec *v, size_t min_cap)
{
if (v->cap >= min_cap) {
return 0;
}
size_t new_cap = v->cap == 0 ? INITIAL_CAP : v->cap;
while (new_cap < min_cap) {
// เช็ค overflow ก่อนคูณ
if (new_cap > SIZE_MAX / GROWTH_FACTOR) {
new_cap = min_cap;
break;
}
new_cap *= GROWTH_FACTOR;
}
if (new_cap > SIZE_MAX / sizeof(int)) {
return -1; // ใหญ่เกิน
}
int *new_data = realloc(v->data, new_cap * sizeof(int));
if (!new_data) {
return -1; // v->data เดิมยังใช้ได้
}
v->data = new_data;
v->cap = new_cap;
return 0;
}
int vec_push(IntVec *v, int value)
{
if (v->len == v->cap) {
if (vec_reserve(v, v->len + 1) != 0) {
return -1;
}
}
v->data[v->len++] = value;
return 0;
}
int vec_pop(IntVec *v, int *out)
{
if (v->len == 0) {
return -1;
}
v->len--;
if (out) {
*out = v->data[v->len];
}
return 0;
}
int vec_get(const IntVec *v, size_t i, int *out)
{
if (i >= v->len) {
return -1;
}
*out = v->data[i];
return 0;
}
int vec_set(IntVec *v, size_t i, int value)
{
if (i >= v->len) {
return -1;
}
v->data[i] = value;
return 0;
}
size_t vec_len(const IntVec *v) { return v->len; }
size_t vec_cap(const IntVec *v) { return v->cap; }
int vec_is_empty(const IntVec *v) { return v->len == 0; }
void vec_clear(IntVec *v) { v->len = 0; }ทำไม growth factor 2
เมื่อ push แล้วเต็ม เราขยาย cap เป็น 2 เท่า (ไม่ใช่ +1) — ทำให้ n ครั้งของ push ใช้เวลารวม O(n) (“amortized O(1)” ต่อครั้ง) ถ้าขยายทีละ 1 จะเป็น O(n²) เพราะ realloc (ซึ่งอาจ copy ข้อมูลทั้งหมด) ทุกครั้ง
test_intvec.c
#include "test.h" // จากบทที่ 34
#include "intvec.h"
#include <stdlib.h>
static void test_basic(void)
{
TEST("push/get/len");
IntVec *v = vec_new();
CHECK(v != NULL);
CHECK_EQ_INT(vec_len(v), 0);
CHECK(vec_is_empty(v));
for (int i = 0; i < 100; i++) {
CHECK_EQ_INT(vec_push(v, i * i), 0);
}
CHECK_EQ_INT(vec_len(v), 100);
CHECK(vec_cap(v) >= 100);
int x;
CHECK_EQ_INT(vec_get(v, 0, &x), 0);
CHECK_EQ_INT(x, 0);
CHECK_EQ_INT(vec_get(v, 50, &x), 0);
CHECK_EQ_INT(x, 2500);
CHECK_EQ_INT(vec_get(v, 100, &x), -1); // เกินขอบ
vec_free(v);
}
static void test_pop(void)
{
TEST("pop");
IntVec *v = vec_new();
vec_push(v, 1);
vec_push(v, 2);
vec_push(v, 3);
int x;
CHECK_EQ_INT(vec_pop(v, &x), 0);
CHECK_EQ_INT(x, 3);
CHECK_EQ_INT(vec_len(v), 2);
CHECK_EQ_INT(vec_pop(v, &x), 0);
CHECK_EQ_INT(vec_pop(v, &x), 0);
CHECK_EQ_INT(vec_pop(v, &x), -1); // ว่างแล้ว
vec_free(v);
}
static void test_edge(void)
{
TEST("edge cases");
IntVec *v = vec_new();
int x;
CHECK_EQ_INT(vec_get(v, 0, &x), -1); // ว่าง
CHECK_EQ_INT(vec_set(v, 0, 5), -1);
vec_clear(v); // ไม่พัง
vec_free(v);
vec_free(NULL); // ไม่พัง
}
int main(void)
{
test_basic();
test_pop();
test_edge();
TEST_SUMMARY();
}gcc -std=c17 -Wall -Wextra -g -fsanitize=address,undefined \
test_intvec.c intvec.c -o test && ./test[push/get/len]
[pop]
[edge cases]
118 ผ่าน, 0 ล้มเหลว (จาก 118)เทสต์ชุดนี้ยังไม่ครอบคลุม
vec_reserve/vec_with_capacityboundary,vec_setสำเร็จ,vec_clearหลังมีข้อมูล, และกรณี OOM/overflow — “ผ่านหมด” ไม่ได้แปลว่าไม่มีบั๊ก เพิ่มเคสเมื่อเจอปัญหาใหม่
ใช้ vector ทำงานจริง
#include "intvec.h"
#include <stdio.h>
int main(void)
{
IntVec *v = vec_new();
if (!v) return 1;
// อ่านตัวเลขจาก stdin จนกว่าจะจบ
int n;
while (scanf("%d", &n) == 1) {
if (vec_push(v, n) != 0) {
fprintf(stderr, "หน่วยความจำหมด\n");
vec_free(v);
return 1;
}
}
// หาผลรวมและค่ามากสุด
long sum = 0;
int max = 0;
for (size_t i = 0; i < vec_len(v); i++) {
int x;
vec_get(v, i, &x);
sum += x;
if (i == 0 || x > max) max = x;
}
printf("%zu ตัว, รวม %ld, มากสุด %d\n", vec_len(v), sum, max);
vec_free(v);
return 0;
}ทำ generic vector (ขั้นสูง)
เก็บชนิดอะไรก็ได้ด้วย void * + element size:
// ── โครงร่าง (skeleton) — ยังไม่ครบ: realloc, เช็ค NULL, overflow, vec_free ต้องเติมเอง ──
typedef struct {
void *data;
size_t len, cap, elem_size;
} Vec;
int vec_push(Vec *v, const void *elem) // memcpy elem_size ไบต์
{
if (v->len == v->cap) { /* realloc: ต้องเช็ค NULL + overflow เหมือน IntVec ข้างบน */ }
memcpy((char *)v->data + v->len * v->elem_size, elem, v->elem_size);
v->len++;
return 0;
}หรือใช้ macro สร้าง typed vector (DEFINE_VEC(int)) — ทั้งสองแบบมีข้อดีข้อเสีย
สัญญาการใช้ API (precondition): ทุกฟังก์ชันข้างบนถือว่า
vไม่เป็น NULL และvec_get/vec_setต้องส่งoutที่ valid — ตรวจที่ผู้เรียก (หรือใส่assert(v != NULL)ในโหมด debug)
เรื่องที่คนมักพลาด
v->data = realloc(v->data, ...)— ถ้า realloc คืน NULL จะ leak data เดิม ใช้ตัวแปรชั่วคราว (โค้ดข้างบนทำถูก)- ขยาย cap ทีละ 1 — O(n²) รวม ใช้ growth factor 2
- ไม่เช็ค integer overflow ใน
cap * sizeof(int)— ผู้ใช้ push เยอะมากจน wrap vec_getคืนค่าตรง ๆ แทน out-parameter — ไม่มีทางบอก “index เกิน” (ค่าintทุกค่า valid)vec_popไม่เช็คว่าว่าง —v->len--เมื่อ len เป็น 0 → wrap เป็นค่ามหาศาล- ลืม
vec_free— leak ทั้ง struct และ data - เก็บ pointer ไป
v->data[i]แล้ว push ต่อ — realloc อาจย้าย data, pointer เดิมใช้ไม่ได้ (dangling)
สรุป
- dynamic array =
{data, len, cap}—pushเพิ่ม, เต็มแล้วขยาย cap เป็น 2 เท่าด้วยrealloc - growth factor 2 → n pushes เป็น O(n) รวม (amortized O(1))
- opaque struct — ผู้ใช้เข้า field ไม่ได้ เปลี่ยน implementation ได้อิสระ
- ทุกฟังก์ชันคืน
0/-1;get/setใช้ out-parameter + return บอก index เกิน reallocผลใส่ตัวแปรใหม่ (ไม่ leak เมื่อ NULL), เช็ค overflow ก่อนคูณขนาด- เตือน: pointer ไปสมาชิกอาจ dangle หลัง push (realloc ย้าย)
บทถัดไป โปรเจกต์เขียน wc แบบ Unix — อ่าน stdin/ไฟล์, นับบรรทัด/คำ/ไบต์, flag