C++ STL 컨테이너 완벽 가이드

#include <vector>

// 생성
vector<int> vec;                    // 빈 벡터
vector<int> vec(10);               // 크기 10, 기본값 0
vector<int> vec(10, 5);            // 크기 10, 모든 값 5
vector<int> vec{1, 2, 3, 4, 5};    // 초기화 리스트

// 주요 함수
vec.push_back(10);          // 끝에 추가
vec.pop_back();             // 끝에서 제거
vec.insert(vec.begin() + 2, 99);  // 특정 위치에 삽입
vec.erase(vec.begin() + 2); // 특정 위치 삭제

// 크기 관련
vec.size();                 // 현재 크기
vec.capacity();             // 할당된 용량
vec.reserve(100);           // 용량 예약
vec.resize(20);             // 크기 변경
vec.shrink_to_fit();        // 불필요한 메모리 해제

// 접근
vec[0];                     // 인덱스 접근 (범위 검사 X)
vec.at(0);                  // 안전한 접근 (범위 검사 O)
vec.front();                // 첫 번째 요소
vec.back();                 // 마지막 요소
vec.data();                 // 내부 배열 포인터

#include <deque>

deque<int> dq;

// 양쪽 끝 조작
dq.push_front(1);           // 앞에 추가
dq.push_back(2);            // 뒤에 추가
dq.pop_front();             // 앞에서 제거
dq.pop_back();              // 뒤에서 제거

// vector와 유사한 인터페이스
dq[0] = 10;
dq.at(1) = 20;
dq.insert(dq.begin() + 1, 15);

#include <list>

list<int> lst{1, 2, 3, 4, 5};

// 삽입/삭제
lst.push_front(0);          // 앞에 추가
lst.push_back(6);           // 뒤에 추가
auto it = lst.begin();
advance(it, 2);
lst.insert(it, 99);         // 특정 위치에 삽입

// 리스트 특화 연산
lst.remove(3);              // 값 3인 모든 요소 제거
lst.remove_if([](int x) { return x > 3; }); // 조건 만족하는 요소 제거
lst.unique();               // 연속된 중복 제거
lst.sort();                 // 정렬
lst.reverse();              // 뒤집기

// 두 리스트 합치기
list<int> other{10, 20, 30};
lst.merge(other);           // 정렬된 두 리스트 병합
lst.splice(lst.begin(), other); // other의 모든 요소를 lst 앞으로 이동

#include <forward_list>

forward_list<int> flst{1, 2, 3, 4, 5};

// 앞쪽만 조작 가능
flst.push_front(0);
flst.pop_front();

// 특정 위치 다음에 삽입
auto it = flst.begin();
flst.insert_after(it, 99);
flst.erase_after(it);

#include <array>

array<int, 5> arr{1, 2, 3, 4, 5};

// C 배열과 유사하지만 STL 인터페이스 제공
arr[0] = 10;
arr.at(1) = 20;
arr.fill(0);                // 모든 요소를 0으로

#include <set>

set<int> s{3, 1, 4, 1, 5, 9}; // 중복 제거되어 {1, 3, 4, 5, 9}

// 삽입/삭제
s.insert(2);                // 삽입
s.erase(3);                 // 값으로 삭제
s.erase(s.find(4));         // 반복자로 삭제

// 검색
auto it = s.find(5);        // 찾기
bool exists = s.count(5);   // 존재 여부 (0 또는 1)
auto it = s.lower_bound(3); // 3 이상인 첫 번째 요소
auto it = s.upper_bound(3); // 3 초과인 첫 번째 요소

// 사용자 정의 비교 함수
set<int, greater<int>> desc_set; // 내림차순

#include <set>

multiset<int> ms{3, 1, 4, 1, 5, 9, 1}; // 중복 허용

ms.count(1);                // 1의 개수 반환
auto range = ms.equal_range(1); // 1인 요소들의 범위

#include <map>

map<string, int> m;

// 삽입
m["apple"] = 5;
m.insert({"banana", 3});
m.emplace("orange", 7);

// 접근
int count = m["apple"];     // 없으면 기본값으로 생성
int count = m.at("apple");  // 없으면 예외 발생

// 검색
auto it = m.find("apple");
if (it != m.end()) {
    cout << it->first << ": " << it->second << endl;
}

// 순회
for (const auto& [key, value] : m) { // C++17 구조화 바인딩
    cout << key << ": " << value << endl;
}

#include <map>

multimap<string, int> mm;
mm.insert({"fruit", 1});
mm.insert({"fruit", 2});    // 같은 키에 다른 값

auto range = mm.equal_range("fruit"); // 해당 키의 모든 값

#include <unordered_set>

unordered_set<int> us{1, 2, 3, 4, 5};

// set과 유사한 인터페이스, 하지만 정렬되지 않음
us.insert(6);
us.erase(3);
bool exists = us.count(4);

// 해시 테이블 정보
cout << "Bucket count: " << us.bucket_count() << endl;
cout << "Load factor: " << us.load_factor() << endl;

#include <unordered_map>

unordered_map<string, int> um;
um["key1"] = 100;
um["key2"] = 200;

// map과 유사하지만 더 빠른 평균 접근 시간

#include <stack>

stack<int> st;

st.push(1);                 // 추가
st.push(2);
st.push(3);

cout << st.top() << endl;   // 최상단 요소 (3)
st.pop();                   // 제거 (반환값 없음)
cout << st.size() << endl;  // 크기

#include <queue>

queue<int> q;

q.push(1);                  // 추가
q.push(2);
q.push(3);

cout << q.front() << endl;  // 앞쪽 요소 (1)
cout << q.back() << endl;   // 뒤쪽 요소 (3)
q.pop();                    // 앞에서 제거

#include <queue>

priority_queue<int> pq;

pq.push(3);
pq.push(1);
pq.push(4);

cout << pq.top() << endl;   // 최대값 (4)
pq.pop();                   // 최대값 제거

// 최소 힙
priority_queue<int, vector<int>, greater<int>> min_pq;

// 사용자 정의 비교
struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // second 기준 최소 힙
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> custom_pq;

// 일반적인 배열 대체 → vector
vector<int> general_use;

// 양쪽 끝 삽입/삭제 빈번 → deque
deque<int> buffer;

// 중간 삽입/삭제 빈번 → list
list<int> frequently_insert;

// 고정 크기 → array
array<int, 100> fixed_size;

// 정렬된 고유 요소 → set
set<int> unique_sorted;

// 정렬된 키-값 → map
map<string, int> sorted_dict;

// 빠른 검색 (정렬 불필요) → unordered_set/unordered_map
unordered_set<int> fast_lookup;
unordered_map<string, int> fast_dict;

// 중복 허용 → multiset/multimap
multiset<int> allow_duplicates;

// LIFO 필요 → stack
stack<int> undo_operations;

// FIFO 필요 → queue
queue<int> task_queue;

// 우선순위 처리 → priority_queue
priority_queue<int> urgent_tasks;

class LRUCache {
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;

        // 최근 사용으로 이동
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 기존 키 업데이트
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        } else {
            // 새 키 추가
            if (cache.size() >= capacity) {
                // 가장 오래된 항목 제거
                map.erase(cache.back().first);
                cache.pop_back();
            }
            cache.emplace_front(key, value);
            map[key] = cache.begin();
        }
    }
};

map<string, int> count_words(const vector<string>& words) {
    map<string, int> frequency;
    for (const string& word : words) {
        frequency[word]++;
    }
    return frequency;
}

// 빠른 버전
unordered_map<string, int> count_words_fast(const vector<string>& words) {
    unordered_map<string, int> frequency;
    for (const string& word : words) {
        frequency[word]++;
    }
    return frequency;
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 인덱스 저장
    vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        // 윈도우 밖의 요소 제거
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 현재 요소보다 작은 요소들 제거
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

// 미리 크기 예약
vector<int> vec;
vec.reserve(expected_size);

// emplace_back vs push_back
vec.emplace_back(args...);  // 제자리 생성 (더 효율적)
vec.push_back(Type(args)); // 임시 객체 생성 후 복사

// 정렬이 필요하거나 키가 복잡한 타입 → map
map<ComplexKey, Value> sorted_map;

// 단순 검색, 빠른 속도 → unordered_map
unordered_map<int, Value> hash_map;

vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();

// 위험: 벡터 크기 변경으로 반복자 무효화
vec.push_back(6);  // it가 무효화될 수 있음

// 안전한 방법: 인덱스 사용 또는 반복자 갱신