시험공부

(2025-2) Introduction to programming(2) 7. The C++ Libraries I (STL: 컨테이너 · 반복자 · 알고리즘 · 어댑터)

norepinephrine 2025. 12. 18. 14:52

목표

  • 표준 라이브러리(일명 STL)의 3대 축: 컨테이너(Container) · 반복자(Iterator) · 알고리즘(Algorithm)을 연결해서 이해한다.
  • 시퀀스 컨테이너(vector, deque, list)의 차이와 선택 기준을 설명한다.
  • 반복자 카테고리와 const/비-const, 역방향/삽입/스트림 반복자를 활용한다.
  • 핵심 알고리즘(find, count, sort, unique, remove, transform, accumulate 등)을 람다/프레디케이트와 함께 사용한다.
  • erase–remove idiom, back_inserter, ostream/istream_iterator 등 어댑터를 능숙히 쓴다.

0) 한 장 요약

  • 컨테이너: 데이터를 담는 상자 (vector/deque/list …)
  • 반복자: 컨테이너 원소를 가리키고 이동하는 “포인터 같은” 것
  • 알고리즘: 반복자 구간(first, last)에 대해 동작하는 함수들
  • 어댑터: 인터페이스를 바꿔주는 도우미 (컨테이너/반복자/함수 어댑터)
[컨테이너] ←→ [반복자] ←→ [알고리즘]
         (back_inserter 등 어댑터로 연결 최적화)

1) 시퀀스 컨테이너 비교: 언제 무엇을 쓰나?

컨테이너 특징 장점 주의/단점 사용 예

vector<T> 연속 메모리(배열 유사), 임의접근 O(1) 대부분의 경우 가장 빠르고 범용 중간 삽입/삭제 비용 큼(이동/재할당) 수집·정렬·탐색 기본 구조
deque<T> 블록 배열, 양끝 삽입/삭제 빠름 push_front 효율적, 임의접근 O(1) 중간 삽입/삭제 여전히 비쌈 양끝 큐, 작업 파이프라인
list<T> 이중연결리스트, 노드 기반 중간 삽입/삭제 항상 O(1), 반복자 안정적 임의접근 불가(느림), 메모리 오버헤드 자주 중간 삽입/삭제할 때

기본값은 vector: 성능·메모리·호환성의 균형이 가장 좋음. 특별한 이유 있을 때만 다른 컨테이너 선택.

2) 반복자(Iterator) 핵심

2-1. 카테고리(능력치)

  • Input/Output: 한 방향·한 번 통과
  • Forward: 한 방향·여러 번 통과
  • Bidirectional: 앞/뒤로 이동 가능 (list)
  • Random Access: 임의 접근, 산술/비교 가능 (vector, deque, string)
  • Contiguous(C++20): 메모리 연속 (vector, string, array)

std::sort는 Random Access 이상 필요 → vector/deque/string O, list X(→ list.sort() 사용).

2-2. const/역방향/삽입/스트림 반복자

vector<int> v{1,2,3};

// (a) const 반복자: 읽기 전용
for (auto it = v.cbegin(); it != v.cend(); ++it) /* *it 읽기만 */

// (b) 역방향 반복자: 뒤에서 앞으로
for (auto it = v.rbegin(); it != v.rend(); ++it) /* *it 사용 */

// (c) 삽입 반복자(back_inserter): push_back을 반복자처럼
copy(v.begin(), v.end(), back_inserter(v)); // v 뒤에 자기 자신 복사(예시)

// (d) 스트림 반복자: 스트림을 컨테이너처럼
// ostream_iterator<int> out(cout, " "); copy(v.begin(), v.end(), out);

3) 알고리즘 핵심 콤보 (람다/프레디케이트와 함께)

3-1. 비변형(읽기) 알고리즘

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

vector<int> v{1,2,3,3,5};
auto it = find(v.begin(), v.end(), 3);     // 값 3 찾기
int c = count(v.begin(), v.end(), 3);      // 3의 개수 → 2
int sum = accumulate(v.begin(), v.end(), 0); // 합계 → 14

3-2. 변형 알고리즘 + 람다

vector<int> v{1,2,3,4,5};
transform(v.begin(), v.end(), v.begin(), [](int x){ return x*x; });
// v = [1,4,9,16,25]

sort(v.begin(), v.end());  // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순(함수 객체)
stable_sort(/*...*/); // 같은 키 유지하며 정렬

3-3. 중복 제거 관용구: sort → unique → erase

vector<int> a{3,1,2,3,2,1};
sort(a.begin(), a.end());                 // [1,1,2,2,3,3]
a.erase(unique(a.begin(), a.end()), a.end()); // [1,2,3]

3-4. 조건 삭제 관용구: erase–remove idiom

// 홀수만 남기기
vector<int> b{1,2,3,4,5,6};
b.erase(remove_if(b.begin(), b.end(), [](int x){ return x%2==0; }), b.end());
// 결과: [1,3,5]

왜 필요한가? remove 계열은 컨테이너 크기를 줄이지 않고 “앞으로 땡겨 놓기”만 함 → 실제 크기 조정은 erase로!

4) 어댑터(Adapters)

4-1. 컨테이너 어댑터

어댑터 내부 컨테이너(기본) 특징

stack<T> deque<T> LIFO(후입선출): push, pop, top
queue<T> deque<T> FIFO(선입선출): push, pop, front, back
priority_queue<T> vector<T> 힙 기반 우선순위 큐: 기본 최대 힙 
#include <queue>
priority_queue<int> pq;
for (int x : {3,1,5,2}) pq.push(x);
while(!pq.empty()) { cout << pq.top() << ' '; pq.pop(); } // 5 3 2 1

4-2. 반복자 어댑터

  • 삽입 반복자: back_inserter, inserter(c, pos), front_inserter
  • 스트림 반복자: istream_iterator<T>, ostream_iterator<T>
  • 역방향/이동 반복자: reverse_iterator, move_iterator
// 스트림 → 벡터 (EOF까지)
vector<int> nums((istream_iterator<int>(cin)), istream_iterator<int>());

// 벡터 → 콘솔
copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));

5) 함수 객체(Function Object) & 람다(Lambda)

  • 함수 객체: operator()를 가진 객체. 상태를 가질 수 있고 인라인화되기 쉬움.
  • 람다: “익명 함수”. 간단한 프레디케이트를 즉석에서 만들기 좋음.
// 람다: 캡쳐 없이
sort(v.begin(), v.end(), [](int a, int b){ return a>b; });

// 람다 캡쳐
int pivot = 10;
auto bigger = [pivot](int x){ return x > pivot; };
auto it = find_if(v.begin(), v.end(), bigger);

캡쳐 규칙: [=](값 캡쳐), [&](참조 캡쳐), a,&b. 캡쳐한 참조의 수명 주의!

6) 문자열(string) + 알고리즘

#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

// 공백/구두점 제거, 소문자화
string s = "Hello, World!";
s.erase(remove_if(s.begin(), s.end(),
                  [](unsigned char ch){ return isspace(ch) || ispunct(ch); }),
        s.end());
transform(s.begin(), s.end(), s.begin(),
          [](unsigned char ch){ return tolower(ch); });
// 결과: "helloworld"

<cctype> 함수는 unsigned char로 캐스팅 후 사용하는 습관!

7) 성능 & 무효화(Invalidation) 규칙 (중요)

컨테이너 삽입/삭제 시 반복자·참조 비고

vector/string 재할당(capacity 증가) 시 모두 무효화. 재할당이 없으면 삽입 위치 이후만 많은 삽입 예상 시 reserve()
deque 블록 구조: 양끝 삽입은 안전한 편이나, 중간 삽입/삭제 시 광범위 무효화  
list 노드 기반: 다른 원소 반복자는 유지. 지워진 원소만 무효화 안정성 필요할 때
queue/stack/priority_queue 내부 컨테이너 규칙 따름  

패턴

  • 미리 reserve(): 재할당을 줄여 반복자 무효화 방지
  • erase–remove: 컨테이너 크기와 반복자 처리 분리
  • 반복 중 삭제: it = v.erase(it); 패턴 사용
for (auto it=v.begin(); it!=v.end(); /* 증감 생략 */) {
    if (조건) it = v.erase(it);   // erase가 다음 반복자를 반환
    else ++it;
}

8) 실전 스니펫 모음

8-1. 입력(파일/표준입력) → 숫자 모으기 → 정렬/중복 제거 → 출력

#include <bits/stdc++.h>
using namespace std;

int main() {
    // EOF까지 정수 읽기
    vector<int> v((istream_iterator<int>(cin)), istream_iterator<int>());

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << '\\n';
}

8-2. 벡터를 조건부 필터링 후 제곱 변환

vector<int> src{1,2,3,4,5,6}, dst;
dst.reserve(src.size()); // 성능 최적화
for (int x : src) if (x%2==1) dst.push_back(x*x);  // [1,9,25]

(또는)

vector<int> dst2;
transform(src.begin(), src.end(), back_inserter(dst2),
          [](int x){ return x%2 ? x*x : 0; });
dst2.erase(remove(dst2.begin(), dst2.end(), 0), dst2.end());

8-3. 문자열 단어 빈도

#include <map>
#include <string>
#include <iterator>
int main() {
    map<string,int> freq;
    for (istream_iterator<string> it(cin), end; it!=end; ++it) ++freq[*it];
    for (auto& [w,c] : freq) cout << w << " " << c << "\\n";
}

9) 체크리스트 (시험 대비)

  • [ ] vector/deque/list 선택 기준을 말할 수 있다.
  • [ ] 반복자 카테고리와 cbegin/cend, rbegin/rend, 삽입/스트림 반복자를 구분한다.
  • [ ] find/count/sort/unique/remove(_if)/transform/accumulate의 사용법을 안다.
  • [ ] erase–remove idiom을 올바르게 쓴다.
  • [ ] 람다 캡쳐([=], [&], 혼합)와 프레디케이트를 설명하고 작성할 수 있다.
  • [ ] 반복자 무효화 규칙과 reserve()의 의미를 설명한다.

10) 미니 퀴즈 (스스로 풀어보기)

  1. list<int>를 std::sort로 정렬하면? 왜/대안은?

std::sort는 Random Access 필요 → list.sort() 사용.

  1. vector<int> v; 에서 짝수 삭제 (erase–remove idiom으로 한 줄)
v.erase(remove_if(v.begin(), v.end(), [](int x){ return x%2==0; }), v.end());
  1. back_inserter가 필요한 이유는?

크기를 모르는 상태에서 copy/transform 결과를 자동 push_back 하도록 연결하기 위해.

  1. unique만 호출했더니 크기가 그대로인 이유는?

unique는 뒤로 “밀어놓기”만 함 → 실제 크기 줄이려면 erase 필요.

  1. 다음 람다의 캡쳐 의미는? auto f = [base,&cnt](int x){ cnt++; return x>base; };

base는 값 캡쳐(복사), cnt는 참조 캡쳐(증가 반영).