std::vector

std::vector는 C++ 표준 라이브러리에서 가장 기본적이고 널리 사용되는 시퀀스 컨테이너(sequence container)다.

자동으로 크기가 조절되는 동적 배열(dynamic array)로, 데이터를 연속된 메모리 공간에 저장하여 효율적인 접근과 순회를 가능하게 한다.

1. 이론

1.1. std::vector의 개념과 특징

std::vector는 일반 C-스타일 배열과 유사하지만, 컴파일 시간이 아닌 실행 시간에 크기를 변경할 수 있는 유연성을 제공한다.

• 동적 크기: 원소를 추가하거나 삭제함에 따라 std::vector의 크기가 자동으로 늘어나거나 줄어들 수 있다.
• 연속 메모리 할당: std::vector의 모든 원소는 C-스타일 배열처럼 메모리 상에 연속적으로 저장된다. 이 특징은 캐시 효율성(cache locality)을 극대화하여, 특히 원소를 순차적으로 순회할 때 매우 빠른 속도를 보장한다.
• 임의 접근(Random Access): 인덱스를 사용하여 O(1)의 시간 복잡도로 특정 위치의 원소에 즉시 접근할 수 있다.
• 시퀀스 컨테이너: 원소들이 삽입된 순서대로 저장된다.

1.2. 내부 구현과 계층 구조

std::vector는 내부적으로 힙(Heap)에 할당된 동적 배열을 가리키는 3개의 포인터(또는 반복자)를 통해 관리된다.

1. _Myfirst: 할당된 메모리 블록의 시작을 가리킨다.
2. _Mylast: 저장된 원소들 중 마지막 원소 바로 다음을 가리킨다. (size()는 _Mylast - _Myfirst로 계산된다.)
3. _Myend: 할당된 전체 메모리 공간의 끝 바로 다음을 가리킨다. (capacity()는 _Myend - _Myfirst로 계산된다.)

size()는 현재 저장된 원소의 개수이며, capacity()는 재할당 없이 저장할 수 있는 최대 원소의 개수다. 항상 size() <= capacity 관계가 성립한다.

재할당 (Reallocation)

push_back 등으로 원소를 추가할 때 size()가 capacity()와 같아지면, std::vector는 더 큰 메모리 블록을 새로 할당하고 기존 원소들을 모두 새 위치로 복사(또는 이동)한 후, 이전 메모리 블록을 해제한다. 이 과정을 재할당이라고 한다.

재할당은 비용이 큰 연산이지만, std::vector는 capacity를 점진적으로 늘리지 않고 현재의 1.5배 또는 2배(구현에 따라 다름)로 늘린다. 이 성장 전략(Growth Strategy) 덕분에 push_back의 시간 복잡도는 평균적으로 O(1)이다.

동작 계층 구조

1. 사용자 영역 (User Code): my_vector.push_back(42); 코드를 실행.
2. C++ 표준 라이브러리 (<vector>):
   • push_back 함수는 size()가 capacity()보다 작은지 확인.
   • size() < capacity(): _Mylast가 가리키는 위치에 원소를 생성하고 _Mylast를 1 증가.
   • size() == capacity():
     • 새로운 capacity(예: 기존의 2배)를 계산.
     • std::allocator를 통해 새 capacity만큼의 메모리를 힙에 요청.
     • 기존 원소들을 새 메모리 블록으로 이동(move) 또는 복사(copy).
     • 이전 메모리 블록을 해제.
     • 내부 포인터(_Myfirst, _Mylast, _Myend)를 갱신.
     • 새 원소를 맨 뒤에 추가.
3. C 런타임 라이브러리 (CRT): std::allocator는 new 연산자를 통해 malloc()을 호출하여 메모리를 할당.
4. 운영체제 (OS Kernel): malloc은 필요 시 시스템 콜(예: brk, mmap)을 통해 커널에 메모리를 요청.
5. 하드웨어 (MMU): CPU의 MMU가 가상 주소를 물리 주소로 변환.

1.3. 주요 멤버 함수와 시간 복잡도

• push_back(value): 맨 뒤에 원소 추가. Amortized O(1).
• pop_back(): 맨 뒤의 원소 제거. O(1).
• operator[i], at(i): i번째 원소 접근. O(1). (at은 범위 검사를 포함)
• insert(pos, value): pos 위치에 원소 삽입. pos부터 끝까지 모든 원소를 뒤로 밀어야 하므로 O(N).
• erase(pos): pos 위치의 원소 삭제. pos 다음부터 모든 원소를 앞으로 당겨야 하므로 O(N).
• reserve(n): capacity를 최소 n개까지 늘립니다. 재할당을 미리 방지하여 성능을 최적화할 때 사용.
• resize(n): size를 n으로 변경합니다. size가 늘어나면 기본값으로 초기화된 원소가 추가되고, 줄어들면 뒤의 원소들이 삭제.
• shrink_to_fit(): 사용하지 않는 여분의 메모리(capacity - size)를 해제하도록 요청.

2. 실습 코드 (게임 스킬 관리)

다음은 std::vector를 사용하여 플레이어의 스킬 목록을 관리하는 예제다. 스킬을 추가하고, 특정 스킬을 찾아 삭제하며, 전체 스킬 목록을 순회하는 기능을 구현한다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // std::find_if 사용

struct Skill {
    std::string name;
    int damage;
    float cooldown;

    // 비교를 위한 연산자 오버로딩
    bool operator==(const std::string& skillName) const {
        return this->name == skillName;
    }
};

// 플레이어의 스킬을 관리하는 클래스
class SkillManager {
public:
    // 새로운 스킬을 배우는 함수
    void LearnSkill(const Skill& newSkill) {
        // Q1: 스킬을 수백 개 추가해야 하는 상황을 가정해봅시다.
        // 이 함수를 루프 안에서 반복 호출하기 전에 `reserve()`를 호출하면 어떤 이점이 있을까요?
        // A: (사용자가 답변을 작성할 부분)
        skills_.push_back(newSkill);
        std::cout << "스킬 '" << newSkill.name << "'을(를) 배웠습니다." << std::endl;
    }

    // 특정 스킬을 잊는 함수
    void ForgetSkill(const std::string& skillName) {
        // Q2: 아래 `std::find_if`는 스킬을 이름으로 찾기 위해 전체 벡터를 순회할 수 있습니다.
        // 스킬이 수천 개일 때, 특정 스킬을 찾는 이 과정의 성능은 어떨까요?
        // `std::map`과 비교했을 때 어떤 차이가 있을까요?
        // A: (사용자가 답변을 작성할 부분)
        auto it = std::find_if(skills_.begin(), skills_.end(), [skillName](const Skill& skill) {
            return skill.name == skillName;
        });

        if (it != skills_.end()) {
            // Q3: `erase` 함수는 왜 인덱스가 아닌 반복자(iterator)를 인자로 받을까요?
            // `erase` 후 `it` 반복자는 어떻게 될까요? (유효할까요, 무효화될까요?)
            // A: (사용자가 답변을 작성할 부분)
            skills_.erase(it);
            std::cout << "스킬 '" << skillName << "'을(를) 잊었습니다." << std::endl;
        } else {
            std::cout << "스킬 '" << skillName << "'을(를) 찾을 수 없습니다." << std::endl;
        }
    }

    // 모든 스킬 정보를 출력하는 함수
    void PrintAllSkills() const {
        std::cout << "--- 보유 스킬 목록 ---" << std::endl;
        if (skills_.empty()) {
            std::cout << "보유한 스킬이 없습니다." << std::endl;
        } else {
            // Q4: 이 반복문은 왜 std::map을 순회할 때보다 일반적으로 더 빠를까요?
            // std::vector의 어떤 메모리 구조적 특징 때문일까요?
            // A: (사용자가 답변을 작성할 부분)
            for (const auto& skill : skills_) {
                std::cout << "  - " << skill.name << " (데미지: " << skill.damage << ", 쿨타임: " << skill.cooldown << "초)" << std::endl;
            }
        }
        std::cout << "----------------------" << std::endl;
    }

private:
    // 스킬 목록을 저장하는 벡터
    std::vector<Skill> skills_;
};

int main() {
    SkillManager playerSkills;

    playerSkills.PrintAllSkills();

    // 스킬 배우기
    playerSkills.LearnSkill({"화염구", 30, 5.0f});
    playerSkills.LearnSkill({"얼음 화살", 25, 4.0f});
    playerSkills.LearnSkill({"번개 사슬", 40, 8.0f});

    playerSkills.PrintAllSkills();

    // 스킬 잊기
    playerSkills.ForgetSkill("얼음 화살");
    playerSkills.ForgetSkill("치유"); // 없는 스킬

    playerSkills.PrintAllSkills();

    return 0;
}

3. 구술형 요약

std::vector에 대해 설명해주세요.

 

std::vector는 C++ 표준 라이브러리가 제공하는 동적 배열 컨테이너입니다. 데이터를 메모리 상에 연속적으로 저장하기 때문에, 인덱스를 통한 임의 접근이 O(1)으로 매우 빠르고 캐시 효율이 높아 순차적인 데이터 처리에 강점을 가집니다.

 

push_back을 통해 맨 뒤에 원소를 추가하는 연산은 평균적으로 O(1)의 시간 복잡도를 가집니다. 이는 내부적으로 재할당이 필요할 때 현재 크기의 1.5배나 2배로 용량(capacity)을 늘리는 성장 전략 덕분입니다. 하지만 배열의 중간에 원소를 삽입하거나 삭제하는 것은 O(N)의 비용이 발생하는데, 이는 뒤따르는 모든 원소들을 이동시켜야 하기 때문입니다.

 

따라서 std::vector는 데이터의 순서가 중요하고, 임의 접근이 빈번하며, 주로 데이터의 끝에서 삽입/삭제가 일어나는 경우에 가장 이상적인 선택입니다.