C++ STL II(2025.07.30)

＊오늘 학습 내용＊

코드카타 문제 / C++ STL

1. ✅ std::unique 동작과 erase 필요성

• unique(first, last)는
  연속 중복을 제거한 유효 구간의 끝
  이터레이터(new end)를 반환.

• 실제 컨테이너 크기는 줄이지 않고
  뒤쪽은 쓰레기 값(이전 값 복사 흔적)으로 남아 있음.

v = {1,1,2,2,4,4,5};
auto it = std::unique(v.begin(), v.end());
// v = {1,2,4,5,?,?...}, it = new end
v.erase(it, v.end()); // 뒤쪽 쓰레기 구간 삭제 → 최종 중복 제거

*unique는 반드시 정렬된 상태에서 전체 중복 제거가 가능하며,
 정렬되지 않으면 연속 중복만 제거됨.

*예시코드
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

2. ✅ unique + erase vs set 성능 비교

vector + sort + unique + erase와 set은 둘 다 O(n log n)이지만,

vector는 연속 메모리라 캐시 효율이 높고
상수항이 작아 보통 더 빠름.

set은 노드 기반이라 캐시 미스와 동적 메모리 오버헤드가 큼.

다만 실시간 삽입/검색이 필요할 때는 set/unordered_set이 유리.

요약:

• 전체 중복 제거 & 순서 상관 없음
  → vector + sort + unique + erase

• 원래 순서 유지 & 중복 제거
  → unordered_set + 새 벡터 생성

• 데이터 실시간 삽입/검색
  → unordered_set(평균 O(1)) or set(O(log n))

3. ✅ lower_bound / upper_bound 개념

• lower_bound(first, last, x) → x 이상(>= x) 첫 번째 위치.

• upper_bound(first, last, x) → x 초과(> x) 첫 번째 위치.

• 정렬된 컨테이너에서 사용하며, 값 개수 계산 가능:

auto lb = std::lower_bound(v.begin(), v.end(), 4);
auto ub = std::upper_bound(v.begin(), v.end(), 4);
int count = ub - lb;

*값이 없으면 lb == ub가 되고, 그 위치가 삽입 가능한 자리.

4. ✅ pow 함수와 주의점

• std::pow(x, y)는 x의 y제곱을 반환 (헤더 ).

std::pow(5, 3); // 125.0 (double 반환)
*반환 타입은 보통 double이므로 정수 정확성이 중요한 경우 주의:

long long res = static_cast<long long>(std::llround(std::pow(5, 3)));
정수 제곱이라면 x * x가 더 빠르고 정확함.

큰 정수 거듭제곱은 직접 빠른 거듭제곱(Binary exponentiation, O(log n)) 구현하는 것이 좋음.