โครงสร้างข้อมูลใน C/C++

Dynamic Array และ std::vector

Dynamic array แยก logical size จาก capacity และเติบโตแบบ geometric

Dynamic Array และ std::vector คืออะไร?

Dynamic array แยก logical size จาก capacity และเติบโตแบบ geometric

ขยาย contiguous storage เมื่อ append ค่า

ประเด็นสำคัญ

  • กำหนด invariant ก่อนเขียน operation
  • จัดการกรณีว่าง เต็ม และ allocation ล้มเหลว
  • ประเมิน complexity และ ownership พร้อมกัน

ตัวอย่างโค้ด C และ C++

C
รันโค้ด →
main.c
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}
ผลลัพธ์ที่คาดหวัง
size=5 capacity=8 last=25
C++
รันโค้ด →
main.cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}
ผลลัพธ์ที่คาดหวัง
size=5 last=25

เปรียบเทียบ C และ C++

C ตรวจ realloc และอัปเดต capacity ส่วน std::vector รวม growth, destructor, iterator และ exception safety

C

Struct และ operation แยกกัน การจัดสรรชัดเจน

C++

Class และ container รักษา invariant และ resource

แบบฝึกหัด

รันทั้งสองเวอร์ชันแล้วแก้ไขเพื่อสังเกตความแตกต่างของภาษา

  • ทดสอบสถานะว่างและเต็ม
  • เขียน cleanup และตรวจ memory leak
  • เปรียบเทียบกับ standard container