C++ STL 정리 (2편) — 알고리즘, 이터레이터, 유틸리티

1편에서 컨테이너를 정리했습니다. 2편에서는 알고리즘, 이터레이터, 람다, 그리고 C++17/20에서 추가된 유틸리티들을 다룹니다.

---

알고리즘 — <algorithm>

STL 알고리즘은 이터레이터 범위를 받아서 동작합니다. 컨테이너에 직접 묶이지 않아서 어떤 컨테이너에도 쓸 수 있습니다.

#include <algorithm>
#include <numeric>

정렬

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};

std::sort(v.begin(), v.end());                          // 오름차순
std::sort(v.begin(), v.end(), std::greater<int>());     // 내림차순
std::sort(v.begin(), v.end(), [](int a, int b) {        // 커스텀 비교
    return a > b;
});

std::stable_sort(v.begin(), v.end());   // 동일한 원소 순서 유지

// 부분 정렬 — 앞 n개만 정렬
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// n번째 원소를 제자리에 (앞은 작은 것들, 뒤는 큰 것들)
std::nth_element(v.begin(), v.begin() + 3, v.end());

// 이미 정렬됐는지 확인
std::is_sorted(v.begin(), v.end());

탐색

// 선형 탐색
auto it = std::find(v.begin(), v.end(), 4);
if (it != v.end()) { /* 찾음 */ }

// 조건 탐색
auto it2 = std::find_if(v.begin(), v.end(), [](int x) {
    return x > 3;
});

// 이진 탐색 (정렬된 범위에서만)
bool found = std::binary_search(v.begin(), v.end(), 4);
auto lb = std::lower_bound(v.begin(), v.end(), 4);   // 4 이상 첫 번째
auto ub = std::upper_bound(v.begin(), v.end(), 4);   // 4 초과 첫 번째

// 원소 개수 세기
int cnt = std::count(v.begin(), v.end(), 1);
int cnt2 = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

// 최솟값/최댓값
auto min_it = std::min_element(v.begin(), v.end());
auto max_it = std::max_element(v.begin(), v.end());
auto [min_it2, max_it2] = std::minmax_element(v.begin(), v.end());

변환 / 복사

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);

// 복사
std::copy(src.begin(), src.end(), dst.begin());

// 조건부 복사
std::copy_if(src.begin(), src.end(), dst.begin(), [](int x) {
    return x % 2 == 0;
});

// 변환
std::transform(src.begin(), src.end(), dst.begin(), [](int x) {
    return x * 2;
});

// 두 범위 변환
std::transform(src.begin(), src.end(), dst.begin(), dst.begin(),
    [](int a, int b) { return a + b; });

// 채우기
std::fill(v.begin(), v.end(), 0);
std::fill_n(v.begin(), 3, 99);

// 생성
std::generate(v.begin(), v.end(), [n=0]() mutable { return n++; });

// 교환
std::swap(v[0], v[1]);
std::iter_swap(v.begin(), v.end() - 1);

제거 / 정리

STL의 제거 함수들은 실제로 원소를 지우지 않고 "논리적으로 제거된" 원소를 뒤로 밀고 새 끝을 반환합니다. 실제 삭제는 erase와 조합합니다.

// erase-remove 관용구
v.erase(std::remove(v.begin(), v.end(), 3), v.end());

// 조건부 제거
v.erase(std::remove_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
}), v.end());

// 중복 제거 (정렬 후)
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// 역순
std::reverse(v.begin(), v.end());

// 회전
std::rotate(v.begin(), v.begin() + 2, v.end());   // 2칸 왼쪽 회전

집합 연산 (정렬된 범위)

std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;

std::set_union(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));         // {1,2,3,4,5,6}

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));         // {3,4}

std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));         // {1,2}

수치 알고리즘 — <numeric>

#include <numeric>

std::vector<int> v = {1, 2, 3, 4, 5};

std::accumulate(v.begin(), v.end(), 0);         // 합계 = 15
std::accumulate(v.begin(), v.end(), 1,
    std::multiplies<int>());                    // 곱 = 120

std::partial_sum(v.begin(), v.end(), v.begin());   // 누적 합

std::iota(v.begin(), v.end(), 1);              // 1부터 순서대로 채우기

std::inner_product(a.begin(), a.end(), b.begin(), 0);  // 내적

---

이터레이터

종류

v.begin();    // 첫 번째 원소
v.end();      // 마지막 다음 (past-the-end)
v.rbegin();   // 역방향 첫 번째
v.rend();     // 역방향 마지막 다음
v.cbegin();   // const 이터레이터
v.cend();

이터레이터 어댑터

#include <iterator>

// back_inserter — push_back으로 삽입
std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));

// front_inserter — push_front로 삽입 (deque, list)
std::copy(src.begin(), src.end(), std::front_inserter(lst));

// istream_iterator — 입력 스트림을 이터레이터로
std::istream_iterator<int> in(std::cin), eof;
std::vector<int> v(in, eof);

// ostream_iterator — 출력 스트림을 이터레이터로
std::copy(v.begin(), v.end(),
    std::ostream_iterator<int>(std::cout, " "));

advance / distance / next / prev

auto it = v.begin();
std::advance(it, 3);              // it를 3칸 앞으로
std::distance(v.begin(), it);     // 거리 = 3
auto it2 = std::next(it, 2);      // it에서 2칸 앞 (it는 안 바뀜)
auto it3 = std::prev(it, 1);      // it에서 1칸 뒤

---

람다와 함수형

람다 기본

auto add = [](int a, int b) { return a + b; };
add(3, 4);   // 7

// 반환 타입 명시
auto div = [](double a, double b) -> double { return a / b; };

// 캡처
int x = 10;
auto add_x = [x](int a) { return a + x; };     // 값 캡처
auto add_x2 = [&x](int a) { return a + x; };   // 참조 캡처
auto add_x3 = [=](int a) { return a + x; };    // 전체 값 캡처
auto add_x4 = [&](int a) { return a + x; };    // 전체 참조 캡처

// mutable — 값 캡처한 것 수정 허용
int count = 0;
auto inc = [count]() mutable { return ++count; };

<functional>

#include <functional>

// std::function — 함수, 람다, 함수 객체를 모두 담을 수 있는 래퍼
std::function<int(int, int)> op = [](int a, int b) { return a + b; };
op(3, 4);

// std::bind — 인수 고정
auto add5 = std::bind(std::plus<int>(), std::placeholders::_1, 5);
add5(3);    // 8

// 표준 함수 객체
std::plus<int>()
std::minus<int>()
std::multiplies<int>()
std::greater<int>()
std::less<int>()
std::negate<int>()
std::logical_and<bool>()

---

유틸리티 — C++17/20

pair / tuple

#include <utility>
#include <tuple>

std::pair<int, std::string> p = {1, "hello"};
p.first;
p.second;
auto [num, str] = p;    // 구조적 바인딩 (C++17)

std::tuple<int, double, std::string> t = {1, 3.14, "hi"};
std::get<0>(t);
std::get<1>(t);
auto [a, b, c] = t;     // 구조적 바인딩

optional — 값이 없을 수 있는 타입

#include <optional>

std::optional<int> find_value(bool found) {
    if (found) return 42;
    return std::nullopt;
}

auto result = find_value(true);
if (result) {
    std::cout << *result;          // 역참조
    std::cout << result.value();   // 또는 이렇게
}
result.value_or(0);                // 없으면 기본값

null 포인터나 -1 같은 sentinel 값 대신 쓸 수 있어서 의도가 명확해집니다.

variant — 타입 안전 union

#include <variant>

std::variant<int, double, std::string> v = 42;
v = 3.14;
v = "hello";

std::get<std::string>(v);           // "hello"
std::get<int>(v);                   // bad_variant_access 예외

std::holds_alternative<std::string>(v);   // true

std::visit([](auto& val) {
    std::cout << val;
}, v);

string_view — 문자열 비소유 참조

#include <string_view>

void print(std::string_view sv) {   // 복사 없이 문자열 참조
    std::cout << sv;
}

std::string s = "Hello, World";
print(s);                           // std::string도 가능
print("literal");                   // 리터럴도 가능
print(s.substr(0, 5));             // 부분 문자열도 가능

std::string_view sv = s;
sv.substr(0, 5);                    // 복사 없이 뷰만 반환

함수 인수로 문자열을 받을 때 const std::string& 대신 std::string_view를 쓰면 불필요한 복사를 줄일 수 있습니다.

span — 배열 비소유 뷰 (C++20)

#include <span>

void process(std::span<int> data) {
    for (auto& x : data) { ... }
}

std::vector<int> v = {1, 2, 3, 4, 5};
process(v);
process(std::span(v).subspan(1, 3));   // 부분 범위

ranges — 범위 기반 알고리즘 (C++20)

#include <ranges>
#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};

// ranges 버전은 컨테이너를 직접 받음
std::ranges::sort(v);
std::ranges::find(v, 4);

// 뷰 파이프라인
auto result = v
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * 2; })
    | std::views::take(3);

for (auto x : result) { std::cout << x << " "; }

---

정리 표

알고리즘

함수	용도
sort / stable_sort	정렬
find / find_if	선형 탐색
binary_search / lower_bound	이진 탐색
count / count_if	개수 세기
transform	변환
copy / copy_if	복사
remove / remove_if + erase	제거
unique + erase	중복 제거
accumulate	합산
iota	순서대로 채우기

유틸리티

타입	용도
pair / tuple	여러 값 묶기
optional<T>	값이 없을 수 있는 타입
variant<T...>	타입 안전 union
string_view	문자열 비소유 참조
span<T>	배열 비소유 뷰
ranges:: / views::	파이프라인 알고리즘