C/C++ 자료 구조

C와 C++의 동적 배열과 std::vector

이 레슨에서는 요소를 추가하면 스스로 커지는 동적 배열을 C로 구현하고 C++의 std::vector와 비교합니다.

소개

동적 배열(dynamic array)은 필요할 때 커질 수 있는 배열입니다. 들어 있는 요소의 수(size)와 할당해 둔 공간(capacity)이라는 두 개념을 구분합니다. 배열이 가득 차면 프로그램은 보통 두 배 크기의 더 큰 영역을 할당하고 그곳으로 데이터를 옮깁니다.

핵심 정리

연산을 작성하기 전에 항상 참이어야 하는 조건(불변식)을 정하세요.
구조가 비어 있을 때, 가득 찼을 때, 메모리 할당에 실패했을 때를 처리하세요.
각 연산의 복잡도와 메모리 관리를 함께 따져 보세요.

동작 원리 보기

push_back을 여러 번 눌러 보세요. 배열이 가득 차면 두 배 크기의 공간을 할당하고 모든 요소를 복사합니다.

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 버전에서는 size가 capacity에 이르면 프로그램이 capacity를 두 배로 늘리고 realloc을 호출해 메모리를 키웁니다. realloc의 결과는 임시 포인터 grown에 담아서, 할당이 실패해도 이전 메모리를 해제할 수 있게 합니다. C++의 std::vector는 바로 이 증가 전략을 감싸고 있으며, 그 밖에도 메모리를 스스로 해제하고 반복자를 지원하며 예외에도 안전합니다.

데이터(struct)와 연산이 분리되어 있고, 메모리는 직접 할당하고 해제합니다.

C++

클래스와 컨테이너가 데이터의 일관성을 지키고 자원을 스스로 관리합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

비어 있는 상태와 최대 용량에 이른 순간에 대한 테스트를 추가해 보세요.
메모리 해제 코드를 작성하고 누수가 없는지 확인해 보세요.
표준 라이브러리의 같은 역할을 하는 컨테이너와 복잡도를 비교해 보세요.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지