[C++] Vector

chooha·2026년 1월 17일

C++

목록 보기

19/22

📚 C++ Vector

🔸 Vector란?

Vector의 특징

동적 크기 배열 (Dynamic Size Array)
시퀀스 컨테이너 (Sequence Container)
연속된 메모리 공간에 원소 저장
C++에서 가장 많이 사용되는 컨테이너

Vector 객체의 메모리 구조

Vector 객체 (스택):
┌──────────────────────┐
│ 포인터 (8 bytes)    │ → 실제 데이터 (힙)
├──────────────────────┤
│ size (8 bytes)     │   현재 원소 개수
├──────────────────────┤
│ capacity (8 bytes) │  할당된 공간 크기
└──────────────────────┘

🔸 reserve와 메모리 재할당

메모리 재할당 문제

std::vector<int> vec;
vec.push_back(1);  // capacity: 1
vec.push_back(2);  // capacity: 2 (메모리 재할당!)
vec.push_back(3);  // capacity: 4 (메모리 재할당!)
vec.push_back(4);  // capacity: 4 (재할당 없음)
vec.push_back(5);  // capacity: 8 (메모리 재할당!)

재할당 과정:

1. 새로운 더 큰 공간 할당 (보통 2배)
2. 기존 원소들을 새 공간으로 복사/이동 (O(n))
3. 기존 공간 해제

문제점:

벡터 뒤에 다른 메모리가 할당되어 있으면 확장 불가
새 공간 할당 후 전체 복사/이동 발생
시간 복잡도: O(n)
성능 저하 발생

reserve로 해결

std::vector<int> vec;
vec.reserve(100);  // 미리 100개 공간 확보

for (int i = 0; i < 100; i++)
{
    vec.push_back(i);  // 재할당 없음!
}

reserve의 효과:

메모리 재할당 횟수 감소
불필요한 복사/이동 제거
성능 향상

🔸 noexcept와 Move 최적화

문제 상황

class Cat
{
public:
    explicit Cat(std::string name) : mName{std::move(name)}
    {
        std::cout << mName << " Cat constructor" << std::endl;
    }
    
    ~Cat()
    {
        std::cout << mName << " ~Cat()" << std::endl;
    }
    
    Cat(const Cat& other) : mName{other.mName}
    {
        std::cout << mName << " copy constructor" << std::endl;
    }
    
    Cat(Cat&& other) : mName{std::move(other.mName)}
    {
        std::cout << mName << " move constructor" << std::endl;
    }
    
private:
    std::string mName;
};

int main()
{
    std::vector<Cat> cats;
    cats.emplace_back("kitty");
    cats.emplace_back("nabi");
    
    return 0;
}

출력:

kitty Cat constructor
nabi Cat constructor
kitty copy constructor  ← ❌ Move가 아닌 Copy!
kitty ~Cat()
kitty ~Cat()
nabi ~Cat()

왜 Copy가 발생했을까?

메모리 재할당 과정:

1. kitty 추가 (capacity: 1)
2. nabi 추가 시도
3. capacity 부족 → 새 공간 할당 (capacity: 2)
4. kitty를 새 공간으로 이동
   → 하지만 Copy Constructor 호출됨!

컴파일러가 Copy를 선택하는 이유:

Move Constructor에서 예외가 발생하면 원본 데이터가 손상될 수 있음
Copy는 예외가 발생해도 원본이 안전함 (Strong Exception Guarantee)
안전을 위해 Move 대신 Copy 선택

해결 방법 1: noexcept 추가

class Cat
{
public:
    explicit Cat(std::string name) : mName{std::move(name)}
    {
        std::cout << mName << " Cat constructor" << std::endl;
    }
    
    ~Cat() noexcept
    {
        std::cout << mName << " ~Cat()" << std::endl;
    }
    
    Cat(const Cat& other) : mName{other.mName}
    {
        std::cout << mName << " copy constructor" << std::endl;
    }
    
    Cat(Cat&& other) noexcept  // ✅ noexcept 추가
        : mName{std::move(other.mName)}
    {
        std::cout << mName << " move constructor" << std::endl;
    }
    
    Cat& operator=(const Cat& other)
    {
        mName = other.mName;
        return *this;
    }
    
    Cat& operator=(Cat&& other) noexcept  // ✅ noexcept 추가
    {
        mName = std::move(other.mName);
        return *this;
    }
    
private:
    std::string mName;
};

int main()
{
    std::vector<Cat> cats;
    cats.emplace_back("kitty");
    cats.emplace_back("nabi");
    
    return 0;
}

출력 (noexcept 추가 후):

kitty Cat constructor
nabi Cat constructor
kitty move constructor  ← ✅ Move로 변경!
~Cat()                  ← 이동된 원본의 소멸자 (mName이 비어있음)
kitty ~Cat()            ← 새 위치의 kitty
nabi ~Cat()

해결 방법 2: reserve 사용

int main()
{
    std::vector<Cat> cats;
    cats.reserve(2);  // ✅ 미리 공간 확보
    
    cats.emplace_back("kitty");
    cats.emplace_back("nabi");
    // 재할당 없음 → Copy/Move 모두 발생하지 않음!
    
    return 0;
}

noexcept를 붙여야 하는 함수
1. Destructor (소멸자)
2. Move Constructor (이동 생성자)
3. Move Assignment (이동 대입 연산자)

이유:

위 함수들은 새로운 리소스를 요청하지 않음
메모리 할당 실패 등의 예외가 발생할 가능성이 없음
noexcept를 명시하면 컴파일러가 최적화 가능

🔸 Vector for Loop의 함정

세 가지 반복문 방식

std::vector<int> nums{0, 1, 0, 1};

// 1. Index-based
for (std::size_t idx = 0; idx < nums.size(); idx++)
{
    if (nums[idx] == 0)
    {
        nums.emplace_back(2);
    }
}

// 2. Iterator-based
for (auto itr = nums.begin(); itr != nums.end(); itr++)
{
    if (*itr == 0)
    {
        nums.emplace_back(2);
    }
}

// 3. Range-based
for (auto& num : nums)
{
    if (num == 0)
    {
        nums.emplace_back(2);
    }
}

결과:

Index-based: ✅ 정상 동작
Iterator-based: ❌ 잘못된 결과 또는 무한 루프
Range-based: ❌ 잘못된 결과 또는 크래시

Iterator-based의 문제

std::vector<int> nums{0, 1, 0, 1};  // capacity: 4

for (auto itr = nums.begin(); itr != nums.end(); itr++)
{
    if (*itr == 0)  // 첫 번째 0 발견
    {
        nums.emplace_back(2);  // capacity 부족 → 재할당!
        // ❌ 문제: 재할당으로 메모리 주소 변경
        //    itr은 여전히 옛날 주소를 가리킴 (dangling iterator)
        //    nums.end()는 새 주소를 가리킴
    }
}

Range-based의 문제

Range-based for는 내부적으로 iterator를 사용하므로 같은 문제 발생

// C++17: Range-based는 이렇게 변환됨
{
    auto&& __range = nums;
    auto __begin = __range.begin();
    auto __end = __range.end();
    for (; __begin != __end; ++__begin)
    {
        auto& num = *__begin;
        // capacity 변경 시 __begin과 __end가 invalidate됨
    }
}

Index-based는 왜 안전한가?

for (std::size_t idx = 0; idx < nums.size(); idx++)
{
    if (nums[idx] == 0)
    {
        nums.emplace_back(2);
        // nums.size()는 매번 새로 계산됨
        // nums[idx]는 매번 새 주소에서 접근
        // ✅ 재할당되어도 문제없음
    }
}

핵심 규칙

❗ For loop 내부에서 vector의 크기가 변경(증가)되면 반드시 index-based를 사용!

// ✅ 안전: Index-based
for (std::size_t i = 0; i < vec.size(); i++)
{
    vec.push_back(x);  // OK
}

// ❌ 위험: Iterator-based
for (auto it = vec.begin(); it != vec.end(); it++)
{
    vec.push_back(x);  // Undefined Behavior 가능!
}

// ❌ 위험: Range-based
for (auto& elem : vec)
{
    vec.push_back(x);  // Undefined Behavior 가능!
}

예외: reserve로 미리 공간 확보

std::vector<int> nums{0, 1, 0, 1};
nums.reserve(100);  // 충분한 공간 확보

// ✅ capacity 변경이 없으므로 iterator도 안전
for (auto it = nums.begin(); it != nums.end(); it++)
{
    if (*it == 0)
    {
        nums.emplace_back(2);  // 재할당 없음 → 안전
    }
}

🔸 erase vs remove (erase-remove idiom)

erase의 비효율성

std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 짝수 제거 (비효율적인 방법)
for (auto it = nums.begin(); it != nums.end();)
{
    if (*it % 2 == 0)
    {
        it = nums.erase(it);  // ❌ 매번 뒤의 원소들을 이동
    }
    else
    {
        ++it;
    }
}

erase의 동작:

[1, 2, 3, 4, 5]에서 2 제거:

1. 2 제거
2. 뒤의 모든 원소를 앞으로 이동
   [1, _, 3, 4, 5]
   [1, 3, _, 4, 5]
   [1, 3, 4, _, 5]
   [1, 3, 4, 5, _]
3. size 감소

→ 한 번 제거할 때마다 O(n)
→ k개 제거 시 O(n*k)

remove의 효율적인 동작

std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// std::remove는 제거할 원소를 뒤로 모음
auto new_end = std::remove_if(nums.begin(), nums.end(), 
    [](int n) { return n % 2 == 0; }
);

// 실제 제거는 erase로
nums.erase(new_end, nums.end());

remove의 two-pointer 알고리즘:

초기: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
       ↑
     write (복사할 위치)
       ↑
     read (확인할 위치)

1. read=1 (홀수) → write 위치에 복사, 둘 다 전진
   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
       ↑
     write
       ↑
     read

2. read=2 (짝수) → 복사 안 함, read만 전진
   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
       ↑
     write
          ↑
         read

3. read=3 (홀수) → write에 복사, 둘 다 전진
   [1, 3, 3, 4, 5, 6, 7, 8, 9, 10]
          ↑
        write
             ↑
           read

4. 반복...

최종: [1, 3, 5, 7, 9, 6, 7, 8, 9, 10]
                     ↑
                   new_end (반환값)

→ new_end부터 end()까지 erase
→ 총 O(n) 한 번만!

erase-remove idiom (표준 패턴)

// ✅ 효율적인 방법
nums.erase(
    std::remove_if(nums.begin(), nums.end(), 
        [](int n) { return n % 2 == 0; }
    ),
    nums.end()
);

// 한 줄로 표현 가능

성능 비교:

erase 반복: O(n*k) - k는 제거할 원소 개수
erase-remove idiom: O(n) - 단 한 번의 순회

C++20: std::erase_if

// C++20부터는 더 간단
std::erase_if(nums, [](int n) { return n % 2 == 0; });

🔸 Vector 알고리즘

정렬 알고리즘

std::sort (일반 정렬)

#include <algorithm>

std::vector<int> nums{5, 2, 8, 1, 9, 3};

std::sort(nums.begin(), nums.end());
// nums: {1, 2, 3, 5, 8, 9}

// 내림차순
std::sort(nums.begin(), nums.end(), std::greater<int>{});
// nums: {9, 8, 5, 3, 2, 1}

// 커스텀 비교
std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return std::abs(a) < std::abs(b);  // 절댓값 기준
});

시간 복잡도: O(n log n)

std::stable_sort (안정 정렬)

struct Person
{
    std::string name;
    int age;
};

std::vector<Person> people{
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 25},
    {"David", 30}
};

// 나이 기준 정렬
std::stable_sort(people.begin(), people.end(), 
    [](const Person& a, const Person& b) {
        return a.age < b.age;
    }
);

// stable_sort: 나이가 같으면 원래 순서 유지
// Alice(25), Charlie(25), Bob(30), David(30)

// sort: 나이가 같으면 순서 보장 안 됨
// Charlie(25), Alice(25), David(30), Bob(30) 가능

stable_sort의 특징:

동일한 값의 원소들의 상대적 순서 유지
시간 복잡도: O(n log n) (merge sort 기반으로 추측)
sort보다 약간 느리지만 안정성 보장

std::partial_sort (부분 정렬)

std::vector<int> nums{5, 2, 8, 1, 9, 3, 7, 4, 6};

// 처음 3개만 정렬
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end());
// nums: {1, 2, 3, ?, ?, ?, ?, ?, ?}
//        ↑정렬됨  ↑정렬 안 됨 (순서 불확정)

// 실제: {1, 2, 3, 8, 9, 5, 7, 4, 6}

사용 사례:

Top K 문제 (상위 K개만 필요)
전체 정렬보다 빠름
시간 복잡도: O(n log k) - k는 부분 정렬할 개수

std::nth_element

std::vector<int> nums{5, 2, 8, 1, 9, 3, 7, 4, 6};

// 중앙값 찾기 (5번째로 작은 원소)
std::nth_element(nums.begin(), nums.begin() + 4, nums.end());
// nums[4]는 정확히 5번째로 작은 원소
// nums[4] 왼쪽은 모두 작거나 같음
// nums[4] 오른쪽은 모두 크거나 같음
// 하지만 양쪽이 정렬된 것은 아님

std::cout << nums[4] << std::endl;  // 5 (중앙값)

특징:

n번째 원소만 정확한 위치에 배치
양쪽은 정렬되지 않음
시간 복잡도: O(n) (평균)
중앙값, 백분위수 찾기에 유용

최솟값/최댓값 찾기

std::vector<int> nums{5, 2, 8, 1, 9, 3};

// 최솟값
auto min_it = std::min_element(nums.begin(), nums.end());
std::cout << *min_it << std::endl;  // 1

// 최댓값
auto max_it = std::max_element(nums.begin(), nums.end());
std::cout << *max_it << std::endl;  // 9

// 최솟값과 최댓값 동시에
auto [min_it2, max_it2] = std::minmax_element(nums.begin(), nums.end());
std::cout << *min_it2 << ", " << *max_it2 << std::endl;  // 1, 9

// 인덱스 찾기
auto min_idx = std::distance(nums.begin(), min_it);
std::cout << "Min index: " << min_idx << std::endl;  // 3

std::distance

Iterator 간의 거리 계산
인덱스를 구할 때 유용

auto it = std::find(nums.begin(), nums.end(), 8);
if (it != nums.end())
{
    std::size_t index = std::distance(nums.begin(), it);
    std::cout << "Found at index: " << index << std::endl;
}

합계 및 누적 연산

std::accumulate

#include <numeric>

std::vector<int> nums{1, 2, 3, 4, 5};

// 합계
int sum = std::accumulate(nums.begin(), nums.end(), 0);
std::cout << sum << std::endl;  // 15

// 곱셈
int product = std::accumulate(nums.begin(), nums.end(), 1,
    [](int acc, int n) { return acc * n; }
);
std::cout << product << std::endl;  // 120

// 문자열 연결
std::vector<std::string> words{"Hello", " ", "World"};
std::string result = std::accumulate(words.begin(), words.end(), 
    std::string{},
    [](std::string acc, const std::string& s) { return acc + s; }
);
std::cout << result << std::endl;  // "Hello World"

std::reduce (C++17)

// std::accumulate와 비슷하지만 병렬 실행 가능
int sum = std::reduce(std::execution::par,  // 병렬 실행
    nums.begin(), nums.end(), 0
);

차이점:

accumulate: 순차 실행, 순서 보장
reduce: 병렬 실행 가능, 순서 보장 안 됨 (결합 법칙 필요)

🔸 핵심 정리

Vector 메모리 관리

Vector 객체: 24 bytes (포인터 + size + capacity)
reserve()로 재할당 방지
noexcept로 move 최적화

반복문 주의사항

Loop 내부에서 크기 변경 시 반드시 index-based 사용
Iterator와 Range-based는 재할당 시 dangling

효율적인 삭제

erase 반복: O(n*k)
erase-remove idiom: O(n)
C++20: std::erase_if

알고리즘 선택

전체 정렬: std::sort O(n log n)
안정 정렬: std::stable_sort O(n log n)
부분 정렬: std::partial_sort O(n log k)
n번째 원소: std::nth_element O(n)
최솟값/최댓값: std::min_element / std::max_element O(n)

<참고 자료>

코드없는 프로그래밍
C++ std::vector
C++ Algorithms Library

chooha

이전 포스트

[C++] 함수형 프로그래밍 & 람다

다음 포스트