(2025-2) Introduction to programming(2) 8. The C++ Libraries II

시험공부

(2025-2) Introduction to programming(2) 8. The C++ Libraries II

norepinephrine 2025. 12. 18. 14:53

주제: 연관 컨테이너(ordered/unordered), 정렬/비교·해시·동등성 규칙, 삽입/탐색/삭제 API, pair/emplace, 버킷/로드팩터, 이터레이터 제약, 커스텀 비교자·해시, 문자열/스트림 유틸(문자열 스트림, 포맷팅 기초)

🎯 학습 목표 (Exam Scope)

[ ] 정렬 연관 컨테이너: map/multimap/set/multiset의 키 정렬, 유일성, 이터레이터 성격
[ ] 비정렬(해시) 연관 컨테이너: unordered_map/unordered_set 계열의 버킷/로드팩터/재해시
[ ] 공통 연산: insert/emplace, find/count, lower_bound/upper_bound/equal_range, erase
[ ] pair/tuple 기본, map의 operator[] 의미(생성 주의), 범위 기반 삭제 패턴
[ ] 커스텀 비교자(정렬 컨테이너)와 커스텀 해시/동등성(해시 컨테이너) 작성
[ ] 이터레이터 제약: 키 수정 금지, 탐색/순회 복잡도 차이
[ ] 문자열 스트림 istringstream/ostringstream, 포맷팅 기초(채움/너비/정밀도)

0) 큰 그림 한 장

정렬 연관 컨테이너 (트리 기반, 기본: 오름차순 < 비교)
  - set / multiset (키만 저장)
  - map / multimap  (키-값 쌍 저장)

비정렬 연관 컨테이너 (해시 기반, == / hash 필요)
  - unordered_set / unordered_multiset
  - unordered_map / unordered_multimap

정렬 연관: 키가 정렬되어 저장, 탐색 O(log N), 순회가 키 순서
비정렬 연관: 순서 없음, 평균 탐색 O(1), 버킷/로드팩터 관리 필요

1) 정렬 연관 컨테이너 (트리 기반)

1-1. 핵심 특성

컨테이너 키 유일성 저장 값 정렬 기준 이터레이터

set<T>	유일	T	std::less<T>(기본 <)	양방향
multiset<T>	중복 허용	T	same	양방향
map<K,V>	키 유일	pair<const K, V>	same	양방향
multimap<K,V>	중복 허용	pair<const K, V>	same	양방향

map의 원소 타입은 pair<const K, V> → 키는 수정 불가(정렬 불변성 유지).
기본 정렬자는 std::less<K>(즉, operator< 기반). 커스텀 비교자 가능(아래 §4-1).

1-2. 기본 연산

#include <map>
#include <set>
#include <string>
using namespace std;

map<string, int> freq;
freq["apple"]++;                 // 없으면 ( "apple", 0 ) 생성 후 증가
freq.insert({"banana", 3});      // 삽입 (이미 있으면 무시)
freq.emplace("cherry", 5);       // 생성+삽입(중간 객체 최소화)

auto it = freq.find("banana");   // O(log N), 없으면 end()
size_t c = freq.count("apple");  // set: 0/1, multiset/map: 0/1, multi*는 0~여러 개
freq.erase("cherry");            // 키로 일괄 삭제

// 중복 키 범위(멀티 계열에서 유용)
auto [first, last] = freq.equal_range("apple"); // [first,last) 구간

1-3. operator[] 주의 (map 한정)

int &v = freq["new_key"];  // 없으면 (new_key, 0) '생성' 후 참조 반환
// 읽기만 하려면 find 사용이 안전

읽기 전용 조회는 find로! operator[]는 부수효과(생성) 가 있음.

2) 비정렬(해시) 연관 컨테이너

2-1. 핵심 특성

컨테이너 키 유일성 평균 탐색 필요 조건

unordered_set<T>	유일	O(1)	hash<T>, ==
unordered_multiset<T>	중복	O(1)	same
unordered_map<K,V>	유일	O(1)	hash<K>, ==
unordered_multimap<K,V>	중복	O(1)	same

순서 보장 없음(버킷 순서).
최악 O(N) 가능(충돌 심하면), 평균 O(1) 목표.

2-2. 버킷·로드팩터·재해시

#include <unordered_map>
using namespace std;

unordered_map<string,int> ufreq;
ufreq.reserve(10000);                 // 버킷 수 미리 확보(재해시 감소)
double lf = ufreq.load_factor();      // 평균 버킷당 원소 수
ufreq.max_load_factor(1.0);           // 목표 로드팩터 조정
ufreq.rehash(16384);                  // 버킷 수 직접 설정(재해시)

로드팩터(load factor) = size / bucket_count. 커지면 충돌↑ → rehash/reserve로 관리.

2-3. 해시/동등성 커스텀

#include <unordered_set>
#include <string>
using namespace std;

struct S { string first, last; };

// 동등성: 같은 사람?
struct Eq {
    bool operator()(S const& a, S const& b) const {
        return a.first==b.first && a.last==b.last;
    }
};

// 해시: 두 문자열 해시를 섞기
struct Hash {
    size_t operator()(S const& s) const {
        return std::hash<string>{}(s.first) ^ (std::hash<string>{}(s.last)<<1);
    }
};

unordered_set<S, Hash, Eq> people;

규칙: 같다고 판단(Eq)되는 두 키는 반드시 같은 해시값(Hash)이 나오도록!

3) 공통 패턴: 삽입/탐색/삭제

3-1. 삽입 결과 다루기 (insert 반환)

set<int> st;
auto [pos, ok] = st.insert(10);  // ok==true면 새로 삽입, false면 기존 원소 가리킴

3-2. 반복 중 삭제(안전 패턴)

map<int,int> mp{{1,10},{2,20},{3,30}};
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->second == 20) it = mp.erase(it);  // erase가 '다음' 반복자를 반환
    else ++it;
}

3-3. 멀티 컨테이너에서 특정 키 전부 삭제

multimap<string,int> mm;
/* ... */
auto range = mm.equal_range("k");
mm.erase(range.first, range.second); // 그 키의 모든 항목 삭제

4) 커스텀 정렬자 / 해시자

4-1. 정렬자(ordered 계열)

struct CaseInsensitiveLess {
    bool operator()(const string& a, const string& b) const {
        auto lower = [](unsigned char c){ return std::tolower(c); };
        size_t n = min(a.size(), b.size());
        for (size_t i=0; i<n; ++i) {
            char ca = lower(a[i]), cb = lower(b[i]);
            if (ca != cb) return ca < cb;
        }
        return a.size() < b.size();
    }
};

map<string,int, CaseInsensitiveLess> dict; // 대소문자 무시 정렬

불변성: 비교자는 엄밀한 약순서(strict weak ordering) 를 만족해야 함(대칭/추이 등).

4-2. 해시자(해시 계열) — 위 §2-3 예시 참고

hash<K>와 ==는 동치성을 표현. Eq(a,b)==true ⇒ Hash(a)==Hash(b) 보장 필요.

5) pair/tuple & 구조적 바인딩

#include <utility>
#include <tuple>
using namespace std;

pair<string,int> p{"apple", 3};
auto [name, cnt] = p;     // C++17 구조적 바인딩
// make_pair, tie, tuple도 유사하게 사용 가능

map 순회에서 자주 쓰는 패턴

for (auto const& [k,v] : freq) {
    // k, v 바로 사용
}

6) 이터레이터 제약(연관 컨테이너 전용 주의)

map/set 등의 이터레이터는 양방향. (list처럼 - 가능, +n 불가)
map 원소 타입: pair<const K, V> → 키는 수정 불가. 값(V)만 수정 가능.

for (auto& [k, v] : freq) v += 1;    // OK
// k = "new";                        // ❌ 키 변경 금지

7) 문자열 스트림 & 포맷팅(간단)

7-1. 문자열 스트림

#include <sstream>
#include <string>
#include <vector>
using namespace std;

string line = "10 20 30";
istringstream iss(line);  // 문자열을 입력 스트림처럼
int x; vector<int> v;
while (iss >> x) v.push_back(x);

ostringstream oss;
oss << "sum=" << 60;
string msg = oss.str();   // "sum=60"

7-2. 포맷팅 기본

#include <iomanip>
double d = 3.1415926;
cout << fixed << setprecision(2) << setw(8) << setfill('_') << d << "\\n";
// 출력 예: "__3.14"

8) 실전 스니펫 모음

8-1. 단어 빈도 (정렬 버전)

#include <map>
#include <string>
#include <iostream>
using namespace std;

int main() {
    map<string,int> freq;
    for (string w; cin >> w; ) ++freq[w]; // operator[]가 자동 생성+증가
    for (auto const& [w,c] : freq) cout << w << " " << c << "\\n";
}

8-2. 단어 빈도 (해시 버전, 성능형)

#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;

int main() {
    unordered_map<string,int> freq;
    freq.reserve(1<<16);                  // 성능 최적화
    for (string w; cin >> w; ) ++freq[w];
    // 순서는 비결정적
}

8-3. 접두사/접미사 집계: 멀티맵 활용

#include <map>
#include <string>
using namespace std;

multimap<string,string> groups;
groups.emplace("pre", "preview");
groups.emplace("pre", "prefix");
groups.emplace("post","postfix");

auto [first,last] = groups.equal_range("pre");
for (auto it=first; it!=last; ++it) /* it->second 사용 */;

8-4. 사용자 타입 해시/동등성

#include <unordered_set>
#include <string>
using namespace std;

struct User { string id; int lvl; };
struct Eq { bool operator()(User const&a, User const&b) const { return a.id==b.id; } };
struct Hash { size_t operator()(User const&u) const { return hash<string>{}(u.id); } };

unordered_set<User,Hash,Eq> users;

9) 자주 틀리는 포인트 (체크리스트)

[ ] map::operator[]는 없던 키를 생성한다 → 조회만이면 find 사용
[ ] set/map의 키는 수정 불가(원소 타입이 pair<const K, V>)
[ ] unordered_*는 평균 O(1)이지만 로드팩터 관리가 중요(reserve/rehash)
[ ] 커스텀 해시/동등성: 동치 ⇒ 같은 해시 규칙 지키기
[ ] equal_range는 멀티 계열에서 해당 키 구간을 한 번에 얻는 도구
[ ] 연관 컨테이너 이터레이터는 임의 접근 아님(정렬 컨테이너: 양방향)
[ ] erase 중 순회는 it = c.erase(it) 패턴으로 안전하게

🔎 미니 퀴즈 (해설 간단)

map<string,int> m;에서 m["x"]와 m.at("x") 차이?

[]: 없으면 생성(0으로 초기화). at: 없으면 예외.

unordered_map에서 성능이 급락한다. 무엇을 점검?

load_factor / bucket_count 확인, reserve/rehash로 조정.

multimap에서 "k" 키를 전부 순회하려면?

auto [first,last] = mm.equal_range("k");
for (auto it=first; it!=last; ++it) /* ... */;

아래 선언의 의미는?

map<string,int,MyLess> m;

MyLess 비교자를 사용해 사용자 정의 정렬 기준으로 키를 정렬.

왜 map의 키는 수정할 수 없나?

정렬 불변성 유지. 원소 타입이 pair<const K,V>이므로 키는 const.

✅ 마무리 요약

정렬 연관: 순서·범위질의(lower_bound/equal_range) 강점, O(log N)
비정렬 연관: 평균 O(1) 탐색, 버킷/로드팩터 관리 필수
공통 API: insert/emplace/find/count/erase, 멀티 계열은 equal_range
커스텀 비교/해시로 도메인 규칙을 녹여라
문자열 스트림과 포맷팅은 입출력 전처리/후처리에 유용