C/C++ 자료 구조

동적 배열과 std::vector

Dynamic array는 logical size와 capacity를 분리하고 기하급수적으로 성장합니다.

동적 배열과 std::vector이란?

Dynamic array는 logical size와 capacity를 분리하고 기하급수적으로 성장합니다.

값 추가 시 연속 storage를 확장합니다.

중요한 점

연산 전에 invariant를 정의하세요.
비어 있음, 가득 참, 할당 실패를 처리하세요.
시간 복잡도와 ownership을 함께 평가하세요.

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는 성장, 소멸, iterator, exception safety를 묶습니다.

구조체와 연산이 분리되고 할당이 명시적입니다.

C++

Class와 container가 invariant와 resource를 관리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

빈 상태와 용량 경계를 테스트하세요.
Cleanup을 구현하고 leak을 확인하세요.
Standard container와 비교하세요.