[C++] 컨테이너 (Containers)

chooha·6일 전
C++

C++

목록 보기
22/22

📚 C++ 컨테이너 (Containers)

🔸 list (이중 연결 리스트)

기본 특징

  • Doubly-Linked List로 구현
  • 각 노드는 이전/다음 노드를 가리키는 두 개의 포인터 보유
  • Insertion/Deletion: O(1) (위치를 알고 있을 때)
  • Random Access: O(n) (순차 탐색 필요)

메모리 구조

Stack:
┌──────────────────┐
│ first (pointer) │ → 첫 번째 노드
│ last (pointer)  │ → 마지막 노드
│ size            │ → 요소 개수
└──────────────────┘

Heap:
┌────┬────┬────┐    ┌────┬────┬────┐    ┌────┬────┬────┐
│prev│data│next│ ↔ │prev│data│next│ ↔ │prev│data│next│
└────┴────┴────┘    └────┴────┴────┘    └────┴────┴────┘
  • 스택에는 first 포인터, last 포인터, size 정보 저장
  • 실제 데이터는 힙(Heap)에 동적 할당

정렬

std::list<int> myList = {3, 1, 4, 1, 5};

// ✅ list 전용 sort() 멤버 함수 사용 (O(n log n))
myList.sort();  

// ❌ std::sort() 사용 불가 (Random Access Iterator 필요)
// std::sort(myList.begin(), myList.end());  // 컴파일 에러!

주요 연산 시간 복잡도

연산시간 복잡도비고
Insertion/Deletion (위치를 알 때)O(1)중간 삽입/삭제 효율적
Random Access ([], at())불가능순차 접근만 가능
Search (find)O(n)순차 탐색
SortO(n log n)멤버 함수 sort() 사용

🔸 forward_list (단일 연결 리스트)

기본 특징

  • Singly-Linked List로 구현
  • 각 노드는 다음 노드만 가리킴 (이전 노드 포인터 없음)
  • list보다 메모리 효율적 (포인터 하나만 필요)
  • Random Access: O(n)

메모리 구조

Stack:
┌──────────────────┐
│ front (pointer) │ → 첫 번째 노드
└──────────────────┘

Heap:
┌────┬────┐    ┌────┬────┐    ┌────┬────┐
│data│next│ → │data│next│ → │data│next│ → nullptr
└────┴────┘    └────┴────┘    └────┴────┘
  • 스택에는 front 포인터 하나만 저장
  • last 포인터나 size 정보는 저장하지 않음 (메모리 절약)

제한 사항

std::forward_list<int> fList = {1, 2, 3, 4, 5};

// ✅ 가능한 연산
fList.push_front(0);
fList.pop_front();
fList.insert_after(fList.begin(), 10);

// ❌ 불가능한 연산
// fList.push_back(6);   // back 포인터 없음
// fList.size();         // size 저장 안 함 (O(n)으로 계산 가능)
// fList[2];             // Random Access 불가

🔸 vector vs list vs forward_list

성능 비교

연산vectorlistforward_list
Random AccessO(1) ✅O(n) ❌O(n) ❌
Front Insertion/DeletionO(n)O(1) ✅O(1) ✅
Back Insertion/DeletionO(1) ✅O(1) ✅O(n) ❌
Middle Insertion/DeletionO(n)O(1) ✅O(1) ✅
find()O(n)O(n)O(n)
메모리 연속성연속 ✅분산분산
캐시 효율높음 ✅낮음낮음

실제 find() 성능

// 둘 다 O(n)이지만 실제로는 vector가 훨씬 빠름!
std::vector<int> vec(1000000);
std::list<int> lst(1000000);

// vector의 find: 메모리가 연속적 → 캐시 히트율 높음 ✅
auto it1 = std::find(vec.begin(), vec.end(), 999999);

// list의 find: 메모리가 분산 → 캐시 미스 많음 ❌
auto it2 = std::find(lst.begin(), lst.end(), 999999);

왜 vector가 더 빠를까? (캐시 지역성)

  • CPU는 메모리에서 데이터를 가져올 때 캐시 라인 단위로 가져옴
  • vector: 메모리가 연속 → 한 번에 여러 요소를 캐시에 로드 ✅
  • list: 메모리가 분산 → 각 노드마다 캐시 미스 발생 ❌

병렬 프로그래밍에서의 문제

// ❌ list는 병렬화가 어려움
// 각 노드가 분산되어 있어서 동시 접근 시 동기화 오버헤드 큼
std::list<int> lst;

// ✅ vector는 병렬화가 용이함
// 메모리가 연속적이라 분할하기 쉬움
std::vector<int> vec;
#pragma omp parallel for
for (int i = 0; i < vec.size(); i++) {
    // 병렬 처리
}

선택 가이드

  • 대부분의 경우: vector 사용 ✅
  • 중간 삽입/삭제가 빈번: list 고려
  • 메모리 최소화 + 단방향만 필요: forward_list

🔸 stack (스택)

기본 특징

  • LIFO (Last In First Out) 구조
  • Container Adapter (다른 컨테이너를 감싸서 구현)
  • 기본 컨테이너: deque (변경 가능)

지원 컨테이너

// ✅ 기본 (deque)
std::stack<int> s1;

// ✅ vector로 구현
std::stack<int, std::vector<int>> s2;

// ✅ list로 구현
std::stack<int, std::list<int>> s3;

// ❌ forward_list는 불가 (back 접근 필요)
// std::stack<int, std::forward_list<int>> s4;  // 컴파일 에러!

주요 연산

std::stack<int> s;

s.push(10);     // O(1) - 삽입
s.pop();        // O(1) - 제거 (값 반환 안 함!)
int top = s.top();  // O(1) - 최상단 접근
bool empty = s.empty();  // O(1)
size_t sz = s.size();    // O(1)

성능 최적화가 필요한 경우

// 직접 구현 예시 (vector 기반)
template<typename T>
class FastStack {
private:
    std::vector<T> data;
public:
    void push(const T& value) {
        data.push_back(value);
    }
    void pop() {
        data.pop_back();
    }
    T& top() {
        return data.back();
    }
    // ...
};

🔸 queue (큐)

기본 특징

  • FIFO (First In First Out) 구조
  • Container Adapter
  • 기본 컨테이너: deque (변경 가능)

지원 컨테이너

// ✅ 기본 (deque)
std::queue<int> q1;

// ✅ list로 구현
std::queue<int, std::list<int>> q2;

// ❌ vector는 불가 (front에서 pop이 O(n))
// std::queue<int, std::vector<int>> q3;  // 컴파일 에러!

// ❌ forward_list는 불가 (back 접근 필요)
// std::queue<int, std::forward_list<int>> q4;  // 컴파일 에러!

주요 연산

std::queue<int> q;

q.push(10);     // O(1) - 뒤에 삽입
q.pop();        // O(1) - 앞에서 제거
int front = q.front();  // O(1) - 앞 요소 접근
int back = q.back();    // O(1) - 뒤 요소 접근
bool empty = q.empty(); // O(1)
size_t sz = q.size();   // O(1)

🔸 priority_queue (우선순위 큐)

기본 특징

  • Max Heap으로 구현 (기본값)
  • 가장 큰 원소가 항상 top에 위치
  • Container Adapter (기본: vector)

시간 복잡도

연산시간 복잡도
Insertion (push)O(log n)
Extraction (pop)O(log n)
Top 접근 (top)O(1) ✅

힙 구조 (배열 기반)

인덱스:  0   1   2   3   4   5   6
값:    [100, 50, 80, 30, 20, 60, 70]

트리 구조:
           100 (idx=0)
          /   \
        50     80
       /  \   /  \
      30  20 60  70

부모-자식 관계:
- 부모 노드: (idx - 1) / 2
- 왼쪽 자식: 2 * idx + 1
- 오른쪽 자식: 2 * idx + 2

힙 속성

  • Max Heap: 부모 노드 ≥ 자식 노드
  • Min Heap: 부모 노드 ≤ 자식 노드

사용 예시

#include <queue>

// ✅ Max Heap (기본)
std::priority_queue<int> maxHeap;
maxHeap.push(30);
maxHeap.push(100);
maxHeap.push(50);
std::cout << maxHeap.top();  // 100

// ✅ Min Heap (greater 사용)
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(30);
minHeap.push(100);
minHeap.push(50);
std::cout << minHeap.top();  // 30

// ✅ 커스텀 비교 함수
auto cmp = [](int a, int b) { return a > b; };  // Min Heap
std::priority_queue<int, std::vector<int>, decltype(cmp)> customHeap(cmp);

인덱스 계산 예시

// 인덱스 3의 부모: (3 - 1) / 2 = 1
// 인덱스 1의 왼쪽 자식: 2 * 1 + 1 = 3
// 인덱스 1의 오른쪽 자식: 2 * 1 + 2 = 4

🔸 heap 알고리즘 (Algorithm Library)

기본 특징

  • <algorithm> 헤더에 포함된 힙 관련 함수들
  • 기존 컨테이너(주로 vector)를 힙으로 변환/관리
  • priority_queue와 동일한 내부 구조

주요 함수

함수시간 복잡도설명
make_heapO(n)범위를 힙으로 변환
push_heapO(log n)마지막 요소를 힙에 삽입
pop_heapO(log n)최대값을 마지막으로 이동

사용 예시

#include <algorithm>
#include <vector>

std::vector<int> vec = {30, 100, 50, 20, 80};

// ✅ 힙 생성 - O(n)
std::make_heap(vec.begin(), vec.end());
// vec: [100, 80, 50, 20, 30] (Max Heap)

// ✅ 최대값 확인
std::cout << vec.front();  // 100 (O(1))

// ✅ 최대값 제거
std::pop_heap(vec.begin(), vec.end());  // O(log n)
// 최대값을 맨 뒤로 이동
// vec: [80, 30, 50, 20, 100]
vec.pop_back();  // 실제 제거 - O(1)
// vec: [80, 30, 50, 20]

// ✅ 새 요소 추가
vec.push_back(90);  // O(1)
std::push_heap(vec.begin(), vec.end());  // O(log n)
// vec: [90, 80, 50, 20, 30]

make_heap이 O(n)인 이유

Naive 방식 (위에서 아래로): O(n log n)
- 각 요소를 하나씩 삽입: n번
- 각 삽입마다 heapify: O(log n)
- 총 시간: O(n log n)

Floyd 알고리즘 (아래에서 위로): O(n) ✅
- 리프 노드는 이미 힙 속성 만족
- 아래에서 위로 올라가며 heapify
- 높이 h인 노드 개수: n / 2^(h+1)
- 각 노드의 작업량: O(h)
- 총 시간: Σ(n / 2^(h+1) * h) = O(n)

priority_queue vs heap 알고리즘

// priority_queue: 편리하지만 유연성 낮음
std::priority_queue<int> pq;
pq.push(10);
// 내부 데이터 직접 접근 불가

// heap 알고리즘: 유연하지만 수동 관리 필요
std::vector<int> vec = {10, 20, 30};
std::make_heap(vec.begin(), vec.end());
// 벡터에 직접 접근 가능 ✅
vec[0];  // 최대값 확인

언제 heap 알고리즘을 사용할까?

  • 기존 컨테이너를 힙으로 변환해야 할 때
  • 힙 내부 데이터에 직접 접근이 필요할 때
  • 부분 정렬이 필요할 때 (Top K 문제 등)

🔸 핵심 정리

컨테이너 선택 가이드
1. 대부분의 경우: vector 사용 (캐시 효율, 랜덤 액세스)
2. 중간 삽입/삭제 빈번: list 고려
3. 메모리 최소화: forward_list
4. LIFO 필요: stack
5. FIFO 필요: queue
6. 우선순위 관리: priority_queue
7. 힙 직접 제어: heap 알고리즘

성능 최적화 팁

  • 대부분의 경우 vector가 가장 빠름 (캐시 지역성)
  • 병렬 프로그래밍에서는 vector 사용 권장
  • 성능이 매우 중요하면 직접 구현 고려
  • 힙 생성은 make_heap이 삽입보다 빠름 (O(n) vs O(n log n))
<참고 자료>

코드없는 프로그래밍
C++ Standard Containers
std::list
std::forward_list
std::priority_queue
Heap Algorithms
Container Adapters

profile
chooha
이전 포스트

[C++] 문자열 (string, string_view)

0개의 댓글