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);

#endif

intvec.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_capacity boundary, 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