STL(Standard Template Library) 컨테이너와 알고리즘을 학습하는 모듈입니다. 반복자(Iterator)와 알고리즘을 활용하여 효율적인 데이터 처리를 경험합니다.
주요 학습 포인트:
- STL 컨테이너 (vector, list, stack, etc.)
- 반복자 (Iterator)
- STL 알고리즘 (find, sort, etc.)
- 함수 객체 (Functor)
- 템플릿 특수화
ex00: Easy find
- easyfind 함수 템플릿
- 정수 컨테이너에서 특정 값 찾기
- STL 알고리즘 std::find 활용
- 못 찾으면 예외 발생
ex01: Span
- Span 클래스
- N개의 정수 저장
- shortestSpan(): 가장 짧은 간격
- longestSpan(): 가장 긴 간격
- 범위 기반 addNumber (반복자 사용)
ex02: Mutated abomination
- MutantStack 클래스 템플릿
- std::stack을 상속받아 반복자 기능 추가
- begin(), end() 함수 구현
- stack을 순회 가능하게 만들기
STL 컨테이너
- vector: 동적 배열, 빠른 랜덤 액세스
- list: 이중 연결 리스트, 삽입/삭제 효율적
- deque: 양방향 큐, 앞뒤 삽입/삭제 효율적
- stack: LIFO 구조, 후입선출
반복자 (Iterator)
- 컨테이너 요소에 순차적으로 접근하는 포인터 같은 객체
- begin()과 end() 사이를 순회하며 요소 접근
- const_iterator는 읽기 전용 반복자
easyfind (ex00)
- STL의 find 알고리즘을 사용하여 컨테이너에서 값 검색
- 템플릿으로 모든 정수 컨테이너에 대해 동작
- 찾지 못하면 예외 발생
Span 클래스 (ex01)
- 최대 N개의 정수를 저장하는 컨테이너
- shortestSpan: 정렬 후 인접한 요소 간 최소 차이 계산
- longestSpan: 최댓값과 최솟값의 차이 계산
- 반복자를 이용한 범위 기반 추가 지원
MutantStack (ex02)
- std::stack을 상속받아 반복자 기능 추가
- stack의 protected 멤버 c(underlying container)에 접근
- begin()과 end()를 구현하여 순회 가능한 스택 생성
- typedef로 반복자 타입 정의
주요 STL 알고리즘
- find: 값 검색
- sort: 정렬
- min_element/max_element: 최소/최대 요소 찾기
- copy: 범위 복사
- fill: 범위를 값으로 채우기
c++ -Wall -Wextra -Werror -std=c++98 *.cpp -o program각 exercise에서:
make- 반복자 유효성: 컨테이너 수정 시 반복자 무효화 주의
- 범위 검사: begin()과 end() 사이에서만 역참조
- const 정확성: const 반복자와 일반 반복자 구분
- 예외 처리: 빈 컨테이너, 범위 초과 등
- 알고리즘 선택: 적절한 STL 알고리즘 사용
- 메모리 관리: vector의 동적 할당 특성 이해
- 성능: O(n), O(log n) 등 시간 복잡도 고려