C++ STL 주요 컨테이너 및 알고리즘 활용 가이드

Vector (벡터)

std::vector는 동적 배열을 구현한 시퀀스 컨테이너입니다. 메모리 상에서 연속적인 공간을 사용하며, 임의 접근(Random Access)이 가능하다는 특징이 있습니다.

반복자 및 범위 기반 for 루프

begin()은 첫 번째 요소를 가리키는 반복자를, end()는 마지막 요소의 다음 위치를 가리키는 반복자를 반환합니다. C++11부터 도입된 범위 기반 for 루프는 이를 간편하게 대체할 수 있습니다.

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

// 범위 기반 for 루프
for (int num : numbers) {
    std::cout << num << " ";
}

// 반복자를 사용한 전통적인 방식
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
}

참조(Reference)를 통한 원본 수정

범위 기반 for 루프에서 변수를 값으로 받으면 복사본이 생성되어 원본 벡터가 수정되지 않습니다. 원본 요소를 직접 수정하려면 참조(&)를 사용해야 합니다.

// 값 복사: 원본 수정 불가
for (int num : numbers) {
    num = 99; // numbers의 요소는 변하지 않음
}

// 참조 사용: 원본 직접 수정
for (int& num : numbers) {
    num = 99; // numbers의 모든 요소가 99로 변경됨
}

초기화 및 다차원 벡터

벡터는 다양한 방식으로 초기화할 수 있으며, 벡터 내부에 벡터를 중첩하여 다차원 구조를 만들 수 있습니다.

std::vector<int> v1;               // 빈 벡터
std::vector<int> v2(5);            // 크기가 5이고 기본값(0)으로 초기화
std::vector<int> v3(5, 10);        // 크기가 5이고 모든 요소가 10으로 초기화

// N x M 크기의 2차원 벡터 (기본값 0)
int rows = 3, cols = 4;
std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, 0));

주의: 일반 2차원 배열은 단일 연속 메모리 블록을 할당하지만, 2차원 벡터는 행 벡터들이 각각 별도의 메모리 공간에 할당되므로 메모리 상에서 완전히 연속적이지 않을 수 있습니다.

Priority Queue (우선순위 큐)

std::priority_queue는 힙(Heap) 자료구조를 기반으로 하며, 우선순위가 가장 높은 요소가 항상 큐의 맨 앞에 위치합니다. 내부적으로 포인터나 반복자를 제공하지 않으므로 범위 기반 for 루프로 순회할 수 없습니다.

최대 힙과 최소 힙

기본적으로 C++의 우선순위 큐는 최대 힙(Max-Heap)으로 동작합니다. 최소 힙(Min-Heap)으로 사용하려면 std::greater 비교자를 명시해야 합니다.

// 최대 힙 (기본값)
std::priority_queue<int> maxHeap;

// 최소 힙
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

사용자 정의 타입과 비교 연산자

사용자 정의 구조체를 사용할 경우 operator<를 오버로드해야 합니다. 우선순위 큐는 내부적으로 std::less를 사용하므로, < 연산자가 true를 반환하는 요소가 힙의 하단으로 밀려나게 됩니다. 즉, 최소 힙을 원한다면 > 논리를 반환하도록 구현해야 합니다.

struct Task {
    int priority;
    int id;
    
    // 최소 힙 구성을 위한 오버로딩 (priority가 작을수록 먼저 나오도록)
    bool operator<(const Task& other) const {
        if (priority != other.priority)
            return priority > other.priority;
        return id > other.id;
    }
};

std::priority_queue<Task> taskQueue;

Set과 Multiset (집합과 다중 집합)

std::set은 레드-블랙 트리(Red-Black Tree) 기반의 연관 컨테이너로, 정렬된 상태의 고유한 원소를 저장합니다. 원소 존재 여부 확인, 특정 값 이상의 최소 값 탐색 등에 유용합니다.

기본 연산 및 중복 처리

insert로 원소를 추가하며, 이미 존재하는 원소는 무시됩니다. erase는 특정 원소를 삭제하고, count는 원소의 존재 여부(0 또는 1)를 반환합니다.

std::set<int> uniqueNums;
uniqueNums.insert(10);
uniqueNums.insert(20);
uniqueNums.insert(10); // 중복이므로 무시됨

bool exists = uniqueNums.count(10); // 1 반환
uniqueNums.erase(10); // 10 삭제

Multiset의 특성

std::multiset은 중복된 원소를 허용합니다. 여기서 주의할 점은 erase(value)를 호출하면 해당 값을 가진 모든 원소가 삭제된다는 것입니다. 단일 원소만 삭제하려면 find를 통해 반복자를 획득한 후 삭제해야 합니다.

std::multiset<int> multiNums = {1, 2, 2, 2, 3};

// 모든 2가 삭제됨
multiNums.erase(2); 

// 단일 원소만 삭제하는 올바른 방법
auto it = multiNums.find(3);
if (it != multiNums.end()) {
    multiNums.erase(it);
}

Lower Bound 활용 팁

Set에는 특정 값보다 '작은' 최대 원소를 직접 찾는 함수가 없습니다. 대신 lower_bound(주어진 값 이상인 첫 번째 원소)를 사용하여 이전 반복자로 이동함으로써 이를 구현할 수 있습니다.

std::set<int> s = {10, 20, 30, 40};
int target = 25;

auto it = s.lower_bound(target); // 30을 가리킴
if (it != s.begin()) {
    --it; // 20을 가리킴 (25보다 작은 최대 값)
    std::cout << *it << std::endl;
}

Bitset (비트셋)

std::bitset은 고정된 크기의 비트(0과 1) 배열을 효율적으로 관리하기 위한 컨테이너입니다. 템플릿 인자로 전달되는 크기는 반드시 컴파일 타임에 결정되는 상수여야 합니다.

const int SIZE = 8;
std::bitset<SIZE> bits("10101010");

int oneCount = bits.count(); // 1의 개수 (4)
bool hasOne = bits.any();    // 1이 하나라도 있는지 (true)
bool isAllOne = bits.all();  // 모두 1인지 (false)
bits.set(0, 1);              // 0번 비트를 1로 설정

이진 탐색 알고리즘 (Lower/Upper Bound)

<algorithm> 헤더에 포함된 전역 함수 std::lower_bound와 std::upper_bound는 정렬된 시퀀스에서 이진 탐색을 수행합니다. 시간 복잡도는 $O(\log N)$입니다.

  • lower_bound: 주어진 값 이상인 첫 번째 원소의 반복자 반환
  • upper_bound: 주어진 값 초과인 첫 번째 원소의 반복자 반환
std::vector<int> sortedData = {1, 3, 3, 5, 7};

auto lb = std::lower_bound(sortedData.begin(), sortedData.end(), 3); // 첫 번째 3을 가리킴
auto ub = std::upper_bound(sortedData.begin(), sortedData.end(), 3); // 5를 가리킴

// 반복자 연산을 통한 인덱스 계산
int index = lb - sortedData.begin(); // 1

최소/최대 값 및 N번째 원소 찾기

C++11 이후 std::min과 std::max는 초기화 리스트를 지원합니다. 배열이나 컨테이너 전체에서 최솟값/최댓값을 찾을 때는 min_element와 max_element를 사용합니다.

int a = std::min({5, 2, 8, 1, 9}); // 1
int b = std::max({5, 2, 8, 1, 9}); // 9

std::vector<int> data = {4, 1, 5, 2, 3};
auto maxIt = std::max_element(data.begin(), data.end()); // 5를 가리킴

// std::nth_element: 특정 인덱스에 정렬 후 위치해야 할 원소를 배치 (부분 정렬)
std::nth_element(data.begin(), data.begin() + 2, data.end());
// data[2]에는 전체 원소 중 3번째로 작은 값(3)이 위치하게 됨

순열 생성 (Next Permutation)

std::next_permutation은 주어진 시퀀스를 사전순으로 다음 순열로 재배열합니다. 모든 순열을 생성하려면 시퀀스를 먼저 오름차순으로 정렬한 후 do-while 루프와 함께 사용해야 합니다.

std::vector<int> perm = {1, 2, 3};

do {
    for (int num : perm) {
        std::cout << num << " ";
    }
    std::cout << "\n";
} while (std::next_permutation(perm.begin(), perm.end()));

Lambda 표현식을 활용한 정렬

std::sort는 세 번째 인자로 사용자 정의 비교 함수를 받을 수 있습니다. Lambda 표현식을 사용하면 외부 변수를 캡처하여 복잡한 조건으로 정렬할 수 있습니다.

std::vector<int> indices = {0, 1, 2};
std::vector<int> weights = {30, 10, 20};

// weights 배열의 값을 기준으로 indices를 정렬
std::sort(indices.begin(), indices.end(), [&weights](int i, int j) {
    return weights[i] < weights[j];
});

// 결과: indices는 {1, 2, 0}이 됨 (weights 기준 10, 20, 30 순서)

태그: C++ STL vector priority_queue set

9월 8일 10:41에 게시됨

인기 태그

©2026 괴물 클럽