pkglog
EN

C++ STL 알고리즘 자주 쓰는 함수 20개: sort·lower_bound·accumulate·remove_if

작성 · · 17분 읽기 · 수정 초급 튜토리얼

이 글의 핵심

sort·find·lower_bound·accumulate·transform·remove_if·next_permutation 등 자주 쓰는 STL 알고리즘 20개를 예제로 정리합니다. remove가 실제로 요소를 지우지 않는 이유(erase-remove 관용구), 정렬되지 않은 범위에 binary_search를 쓰는 실수, 람다 캡처 문제 같은 함정도 함께 짚습니다.

STL 알고리즘 20선

<algorithm>의 함수들은 거의 모두 (first, last) 이터레이터 쌍을 받아 반열린 구간 [first, last) 에 대해 동작합니다. last는 마지막 원소 “다음” 위치이므로 v.end()를 넘기면 전체가 대상이 되고, “찾지 못함”도 보통 last를 반환하는 것으로 표현합니다. 이 규칙 하나만 머릿속에 넣어 두면 아래 20개 함수의 반환값을 해석하는 방법이 모두 같아집니다. 또 한 가지 공통점은 알고리즘이 컨테이너가 아니라 이터레이터만 본다는 점입니다. 그래서 sort는 vector든 일반 배열이든 동작하지만, 컨테이너 크기를 바꾸는 일(원소 삭제·추가)은 스스로 하지 못합니다. 뒤에서 볼 remove가 원소를 “지우지 않는” 이유도 여기에 있습니다.

sort - 정렬

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

vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());  // 오름차순
sort(v.begin(), v.end(), greater<int>());  // 내림차순

sort는 임의 접근 이터레이터가 필요해서 std::list에는 쓸 수 없고(list.sort() 멤버 함수를 씁니다), 같은 값끼리의 원래 순서를 보장하지 않습니다. 비교 함수를 직접 넘길 때는 “a가 b보다 앞에 와야 하면 true”라는 엄격한 약순서를 지켜야 합니다. [](int a, int b) { return a <= b; }처럼 같은 값에 true를 반환하면 정의되지 않은 동작이 되고, 원소가 많을 때 구간 밖을 읽다가 크래시가 나는 경우도 있습니다. 결과가 “대체로 맞는데 가끔 이상하다”면 비교 함수부터 의심해 보세요.

find - 검색

auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "찾음: " << *it << endl;
}

find는 앞에서부터 하나씩 비교하는 선형 탐색이라 O(n)입니다. 같은 컨테이너에서 검색을 반복한다면 정렬 후 이진 탐색을 하거나 set/unordered_set으로 바꾸는 편이 낫습니다. 반환된 이터레이터를 end()와 비교하지 않고 바로 *it로 역참조하는 것이 가장 흔한 실수이며, 값이 없을 때 정의되지 않은 동작이 됩니다. 조건으로 찾고 싶다면 find_if(v.begin(), v.end(), 조건)을 씁니다.

binary_search - 이진 탐색

sort(v.begin(), v.end());  // 정렬 필수
bool found = binary_search(v.begin(), v.end(), 3);

binary_search는 bool만 돌려주기 때문에 “있는지”만 알 수 있고 위치는 알 수 없습니다. 위치가 필요하면 바로 아래의 lower_bound를 쓰는 편이 한 번의 탐색으로 두 가지를 다 얻는 방법입니다.

lower_bound / upper_bound

auto it = lower_bound(v.begin(), v.end(), 3);  // >= 3인 첫 위치
auto it2 = upper_bound(v.begin(), v.end(), 3);  // > 3인 첫 위치

두 함수를 함께 쓰면 정렬된 구간에서 특정 값의 개수를 O(log n)에 셀 수 있습니다. upper_bound(...) - lower_bound(...)가 3의 개수이고, equal_range는 이 두 이터레이터를 한 번에 pair로 돌려줍니다. 값이 없으면 lower_bound는 “그 값을 삽입해도 정렬이 유지되는 위치”를 반환하므로, it != v.end() && *it == 3까지 확인해야 실제로 찾았다고 판단할 수 있습니다. std::set이나 std::map에서는 전역 lower_bound 대신 s.lower_bound(3) 멤버 함수를 써야 합니다. 전역 버전은 트리 이터레이터가 임의 접근이 아니라서 O(n)으로 동작하는데, 컴파일은 문제없이 되기 때문에 성능 문제로만 드러납니다.

count - 개수 세기

int cnt = count(v.begin(), v.end(), 1);  // 1의 개수

accumulate - 합계

#include <numeric>
int sum = accumulate(v.begin(), v.end(), 0);

accumulate는 <algorithm>이 아니라 <numeric>에 있습니다. 더 중요한 함정은 초기값의 타입이 결과 타입을 결정한다는 점입니다. vector<double>을 accumulate(v.begin(), v.end(), 0)으로 더하면 누적 변수가 int가 되어 매 단계 소수점이 잘려 나갑니다. 컴파일 경고도 없이 결과만 틀리기 때문에 찾기 어려운 버그인데, 실수 합계라면 0.0, 큰 정수 합계라면 0LL처럼 초기값 타입을 명시해야 합니다. 인자로 이항 함수를 넘기면 곱이나 문자열 연결 같은 다른 누적도 할 수 있습니다.

max_element / min_element

auto maxIt = max_element(v.begin(), v.end());
auto minIt = min_element(v.begin(), v.end());
cout << "최댓값: " << *maxIt << endl;

이 함수들은 값이 아니라 이터레이터를 돌려줍니다. 빈 컨테이너라면 end()가 반환되므로 *maxIt는 정의되지 않은 동작입니다. 최댓값의 위치(인덱스)가 필요하면 maxIt - v.begin()으로 구할 수 있습니다. 최댓값이 여러 개일 때 max_element는 가장 앞의 것을 가리킵니다.

reverse - 역순

reverse(v.begin(), v.end());

unique - 중복 제거

sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());

unique는 인접한 중복만 제거하므로 앞에서 정렬하는 단계가 빠지면 {1, 2, 1}의 두 1이 그대로 남습니다. 그리고 remove와 마찬가지로 크기를 줄이지 않고 “유지할 원소를 앞으로 모은 뒤 새 끝 위치”를 돌려줄 뿐이라 erase가 뒤따라야 합니다. 정렬 순서를 바꾸면 안 되는 데이터에서 중복을 제거하려면 unordered_set에 이미 본 값을 기록하며 걸러 내는 방식을 씁니다.

fill - 값 채우기

fill(v.begin(), v.end(), 0);  // 모두 0으로

copy - 복사

vector<int> v2(v.size());
copy(v.begin(), v.end(), v2.begin());

copy는 대상 구간에 공간이 이미 있다고 가정하고 덮어쓰기만 합니다. vector<int> v2;처럼 빈 벡터에 v2.begin()으로 복사하면 존재하지 않는 원소에 쓰게 되어 메모리가 망가집니다. 크기를 미리 잡거나, copy(v.begin(), v.end(), back_inserter(v2))처럼 push_back을 호출해 주는 삽입 이터레이터를 써야 합니다(<iterator> 헤더). 단순히 컨테이너 전체를 복사하는 것이라면 vector<int> v2 = v;가 가장 간단합니다.

transform - 변환

transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });

세 번째 인자가 출력 위치이며, 위처럼 입력과 같은 위치를 주면 제자리에서 변환합니다. 다른 컨테이너에 결과를 담는다면 역시 크기를 미리 잡거나 back_inserter를 써야 합니다. 두 입력 구간을 받는 버전(transform(a.begin(), a.end(), b.begin(), out, 이항함수))도 있어서 원소별 덧셈 같은 작업에 편리한데, 이때 b가 a보다 짧으면 구간 밖을 읽습니다.

for_each - 각 요소에 함수 적용

for_each(v.begin(), v.end(), [](int x) { cout << x << " "; });

remove / remove_if

auto it = remove(v.begin(), v.end(), 3);  // 3 제거
v.erase(it, v.end());

auto it2 = remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
v.erase(it2, v.end());

C++20부터는 std::erase(v, 3)과 std::erase_if(v, 조건)이 vector, string, deque 등에 추가되어 이 두 줄을 한 줄로 쓸 수 있습니다. 컴파일러가 C++20을 지원한다면 erase-remove 관용구를 잊어버릴 위험이 없는 쪽을 권합니다. std::list는 노드를 직접 떼어 낼 수 있어 멤버 함수 list.remove(3)이 실제로 삭제까지 합니다.

replace - 치환

replace(v.begin(), v.end(), 1, 10);  // 1을 10으로

next_permutation - 순열

vector<int> v = {1, 2, 3};
do {
    for (int x : v) cout << x;
    cout << " ";
} while (next_permutation(v.begin(), v.end()));

next_permutation은 현재 순열의 “사전순 다음” 순열로 바꾸고, 더 이상 다음이 없으면(내림차순 상태) 처음 순열로 되돌리면서 false를 반환합니다. 그래서 모든 순열을 보려면 오름차순으로 정렬된 상태에서 시작해야 합니다. {3, 1, 2}에서 시작하면 그보다 사전순으로 뒤인 순열만 나오고 앞의 것은 빠집니다. 중복 원소가 있으면 같은 순열은 한 번씩만 생성되므로, 직접 백트래킹을 짤 때처럼 중복 처리를 따로 할 필요가 없다는 것도 장점입니다.

partition - 분할

partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

partition은 조건을 만족하는 원소를 앞쪽으로 모으고 경계 이터레이터를 반환하지만, 각 그룹 안의 원래 순서는 보장하지 않습니다. 순서를 유지해야 하면 stable_partition을 쓰는데, 추가 메모리를 쓰거나(가능할 때) 더 느린 알고리즘으로 동작한다는 비용이 있습니다.

merge - 병합

vector<int> result(v1.size() + v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

merge는 두 입력이 이미 같은 기준으로 정렬되어 있다고 가정하고 선형 시간에 합칩니다. 정렬되지 않은 입력을 넣어도 에러 없이 그냥 정렬되지 않은 결과가 나옵니다. 중복을 없애며 합치려면 set_union, 공통 원소만 필요하면 set_intersection을 씁니다.

all_of / any_of / none_of

bool allPositive = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool hasNegative = any_of(v.begin(), v.end(), [](int x) { return x < 0; });
bool noZero = none_of(v.begin(), v.end(), [](int x) { return x == 0; });

빈 구간에서의 결과는 논리학 규칙을 따릅니다. all_of와 none_of는 true, any_of는 false입니다. “모든 원소가 양수인가”를 검사하는 코드가 빈 입력에서 true를 돌려주는 것이 원하는 동작이 아닐 수 있으므로, 빈 입력을 따로 처리해야 하는지 한 번 생각해 볼 필요가 있습니다. 세 함수 모두 결과가 정해지는 순간 순회를 멈춥니다.

minmax_element - 최소/최대 동시

auto [minIt, maxIt] = minmax_element(v.begin(), v.end());
cout << "최소: " << *minIt << ", 최대: " << *maxIt << endl;

min_element와 max_element를 따로 호출하면 비교를 약 2n번 하지만, minmax_element는 원소를 두 개씩 묶어 처리해 약 1.5n번으로 끝냅니다. 위 코드의 auto [minIt, maxIt]는 C++17 구조적 바인딩 문법입니다.

실전 예시

예시 1: 데이터 정제 파이프라인

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

int main() {
    vector<int> data = {5, -2, 8, -1, 3, 0, 7, -3, 2, 8, 5};
    
    cout << "원본: ";
    for (int x : data) cout << x << " ";
    
    // 1. 음수 제거
    auto it = remove_if(data.begin(), data.end(), [](int x) { return x < 0; });
    data.erase(it, data.end());
    
    // 2. 정렬
    sort(data.begin(), data.end());
    
    // 3. 중복 제거
    auto it2 = unique(data.begin(), data.end());
    data.erase(it2, data.end());
    
    cout << "\n정제 후: ";
    for (int x : data) cout << x << " ";
    
    // 4. 통계
    int sum = accumulate(data.begin(), data.end(), 0);
    double avg = (double)sum / data.size();
    
    cout << "\n합계: " << sum << endl;
    cout << "평균: " << avg << endl;
    cout << "최댓값: " << *max_element(data.begin(), data.end()) << endl;
    
    return 0;
}

설명: 여러 알고리즘을 조합하여 데이터를 정제하는 파이프라인입니다. 단계의 순서에도 이유가 있습니다. 음수를 먼저 제거하면 뒤따르는 정렬이 더 적은 원소를 다루고, unique는 인접 중복만 지우므로 반드시 정렬 뒤에 와야 합니다. 이 순서를 바꿔 unique를 먼저 호출하면 떨어져 있는 두 8과 두 5가 그대로 남습니다.

실제로 이런 파이프라인을 짤 때 조심할 부분은 마지막 통계 단계입니다. 입력이 모두 음수였다면 이 시점에 data가 비어 있어서 sum / data.size()는 0으로 나누기(double이므로 NaN)가 되고, *max_element(...)는 end()를 역참조하는 정의되지 않은 동작이 됩니다. 테스트 데이터로는 드러나지 않다가 실제 입력에서 터지는 전형적인 경우라, 필터링 뒤에는 if (data.empty()) 검사를 넣는 습관을 들이는 것이 좋습니다.

예시 2: 학생 정렬 시스템

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int score;
    int id;
};

int main() {
    vector<Student> students = {
        {"Alice", 85, 1003},
        {"Bob", 92, 1001},
        {"Charlie", 85, 1002},
        {"David", 78, 1004}
    };
    
    // 점수 내림차순, 같으면 ID 오름차순
    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    });
    
    cout << "=== 성적 순위 ===" << endl;
    for (int i = 0; i < students.size(); i++) {
        cout << (i+1) << "등: " << students[i].name 
             << " (" << students[i].score << "점)" << endl;
    }
    
    // 80점 이상 학생 수
    int count = count_if(students.begin(), students.end(), 
                          [](const Student& s) { return s.score >= 80; });
    cout << "\n80점 이상: " << count << "명" << endl;
    
    // 평균 점수
    int totalScore = accumulate(students.begin(), students.end(), 0,
                                 [](int sum, const Student& s) { return sum + s.score; });
    cout << "평균: " << (double)totalScore / students.size() << "점" << endl;
    
    return 0;
}

설명: 복잡한 정렬 조건과 집계 함수를 활용한 실무 패턴입니다. 비교 람다가 const Student&로 받는 이유는 sort가 비교를 n log n번 호출하기 때문입니다. 값으로 받으면 호출마다 string이 복사됩니다. “점수가 다르면 점수로, 같으면 ID로”라는 조건은 tie(b.score, a.id) < tie(a.score, b.id)처럼 std::tie(<tuple>)로도 쓸 수 있는데, 내림차순 필드는 a와 b의 자리를 바꿔 넣는다는 점이 헷갈리기 쉬워 위처럼 풀어 쓰는 편이 읽기 좋을 때도 있습니다.

accumulate에 이항 람다를 넘겨 구조체의 특정 필드만 더하는 방식도 자주 쓰입니다. 첫 번째 매개변수가 지금까지의 누적값, 두 번째가 현재 원소이며, 초기값 0의 타입(int)이 람다의 첫 매개변수 타입과 맞아야 합니다. 동점자 처리 순서가 중요하지 않고 원래 입력 순서만 유지하면 된다면 ID 비교 대신 stable_sort를 쓰는 방법도 있습니다.

예시 3: 문자열 처리

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

int main() {
    string text = "Hello World 123";
    
    // 대문자로 변환 (unsigned char로 받아야 음수 char에서 안전)
    transform(text.begin(), text.end(), text.begin(),
              [](unsigned char c) { return static_cast<char>(toupper(c)); });
    cout << text << endl;  // HELLO WORLD 123
    
    // 숫자만 추출
    string numbers;
    copy_if(text.begin(), text.end(), back_inserter(numbers),
            [](unsigned char c) { return isdigit(c) != 0; });
    cout << "숫자: " << numbers << endl;  // 123
    
    // 공백 제거
    auto it = remove(text.begin(), text.end(), ' ');
    text.erase(it, text.end());
    cout << "공백 제거: " << text << endl;
    
    // 회문 체크
    string original = "level";
    string reversed = original;
    reverse(reversed.begin(), reversed.end());
    
    if (original == reversed) {
        cout << original << "은 회문입니다" << endl;
    }
    
    return 0;
}

설명: 문자열 변환과 필터링에 STL 알고리즘을 활용한 예제입니다. string도 문자들의 연속 컨테이너이므로 벡터와 똑같이 알고리즘을 적용할 수 있습니다.

대소문자 변환에 ::toupper를 그대로 넘기는 코드가 인터넷에 많이 퍼져 있지만, 이 예제에서는 람다로 감쌌습니다. toupper와 isdigit는 인자가 unsigned char로 표현 가능한 값이거나 EOF여야 한다고 규정되어 있는데, char가 부호 있는 타입인 플랫폼(x86의 GCC/MSVC 등)에서 UTF-8 한글 바이트처럼 128 이상인 문자는 음수가 되어 정의되지 않은 동작이 됩니다. MSVC 디버그 빌드에서는 실제로 assertion 창이 뜨기도 합니다. 또 <locale>을 함께 include하면 std::toupper가 오버로드된 템플릿 버전과 겹쳐 함수 이름만 넘기는 코드가 no matching function 에러로 깨질 수 있는데, 람다는 이런 문제도 피합니다. 마지막으로 이 함수들은 바이트 단위로 동작하므로 한글 같은 멀티바이트 문자의 대소문자나 문자 분류를 처리하지 못한다는 한계도 알아 두세요.

자주 발생하는 문제

문제 1: remove는 실제로 삭제하지 않음

증상: remove 후에도 벡터 크기가 그대로

원인: remove는 요소를 뒤로 이동만 하고 erase가 실제 삭제

해결법:

// ❌ 잘못된 사용
vector<int> v = {1, 2, 3, 2, 4};
remove(v.begin(), v.end(), 2);
cout << v.size();  // 5 (그대로!)

// ✅ 올바른 사용 (erase-remove idiom)
vector<int> v = {1, 2, 3, 2, 4};
auto it = remove(v.begin(), v.end(), 2);
v.erase(it, v.end());
cout << v.size();  // 3

remove가 이렇게 설계된 이유는 알고리즘이 컨테이너를 모르고 이터레이터만 받기 때문입니다. 이터레이터로는 원소 값을 읽고 쓸 수는 있지만 컨테이너의 크기를 바꿀 방법이 없으므로, remove는 남길 원소를 앞으로 당겨 채우고 “새로운 끝”을 알려 주는 데서 멈춥니다. 새 끝 뒤에 남은 원소들의 값은 규정되어 있지 않아서(이동된 뒤의 값일 수도 있음), 크기만 확인하지 않고 전체를 출력해 보면 1 3 4 2 4처럼 이상한 값이 보이기도 합니다. [[nodiscard]]가 붙은 표준 라이브러리 구현(GCC 최신 버전 등)에서는 반환값을 버리면 경고가 나오므로 경고 옵션을 켜 두는 것도 도움이 됩니다.

증상: binary_search가 잘못된 결과 반환

원인: 이진 탐색은 정렬된 데이터에서만 동작

해결법:

// ❌ 잘못된 코드
vector<int> v = {3, 1, 4, 1, 5};
bool found = binary_search(v.begin(), v.end(), 3);  // 잘못된 결과

// ✅ 올바른 코드
vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());  // 정렬 먼저!
bool found = binary_search(v.begin(), v.end(), 3);  // OK

정렬되지 않은 입력에 대한 이진 탐색은 에러를 내지 않고 조용히 틀린 답을 돌려줍니다. 위 예에서는 우연히 맞게 나올 수도 있다는 점이 오히려 위험합니다. 비교 기준도 일치해야 하는데, greater<int>()로 내림차순 정렬했다면 binary_search(v.begin(), v.end(), 3, greater<int>())처럼 같은 비교 함수를 넘겨야 합니다. 이걸 빠뜨리는 실수는 코딩 테스트에서 특히 흔합니다. 한 번 검색하려고 매번 정렬하는 것은 O(n log n)이라 find보다 오히려 느리므로, 정렬 한 번에 검색을 여러 번 할 때만 의미가 있습니다. MSVC의 디버그 빌드는 이터레이터 디버깅 기능으로 정렬되지 않은 구간을 감지해 알려 주기도 합니다.

문제 3: 람다에서 외부 변수 캡처

증상: 람다 내부에서 외부 변수 사용 시 컴파일 에러

원인: 캡처를 명시하지 않음

해결법:

// ❌ 컴파일 에러
int threshold = 10;
auto it = find_if(v.begin(), v.end(), [](int x) {
    return x > threshold;  // 에러! threshold 캡처 안 됨
});

// ✅ 값 캡처
auto it = find_if(v.begin(), v.end(), [threshold](int x) {
    return x > threshold;
});

// ✅ 참조 캡처
auto it = find_if(v.begin(), v.end(), [&threshold](int x) {
    return x > threshold;
});

// ✅ 모두 캡처
auto it = find_if(v.begin(), v.end(), [=](int x) {  // 값으로 모두
    return x > threshold;
});

auto it = find_if(v.begin(), v.end(), [&](int x) {  // 참조로 모두
    return x > threshold;
});

위 코드는 네 가지 방식을 나란히 보여 주려고 같은 이름 it을 여러 번 선언했으므로, 실제로는 하나만 골라 써야 컴파일됩니다. 어느 캡처 방식을 고를지는 람다가 얼마나 오래 사는지로 판단합니다. find_if처럼 호출이 끝나면 바로 사라지는 람다라면 참조 캡처가 복사 비용 없이 안전합니다. 반대로 람다를 std::function에 저장하거나 다른 스레드에 넘겨 나중에 실행한다면, 참조로 캡처한 지역 변수가 그 시점에 이미 사라져 있어 댕글링 참조가 됩니다. [&]는 편하지만 무엇을 캡처했는지 코드에 드러나지 않으므로, 오래 사는 람다에서는 캡처할 변수를 명시하는 편이 버그를 줄입니다.

FAQ

Q1: sort는 어떤 알고리즘을 사용하나요?

A: 표준은 구체적인 알고리즘을 정하지 않고 복잡도만 요구합니다. C++11부터는 최악의 경우에도 O(n log n) 비교를 보장해야 하므로, libstdc++·libc++·MSVC 모두 퀵소트로 시작해 재귀가 너무 깊어지면 힙소트로 전환하고 작은 구간은 삽입 정렬로 마무리하는 Introsort 계열을 사용합니다. 불안정 정렬이라는 점은 공통입니다.

Q2: stable_sort는 언제 사용하나요?

A: 같은 값의 상대적 순서를 유지해야 할 때 사용합니다. 예를 들어 이미 이름순으로 정렬된 목록을 점수순으로 다시 정렬하면서 동점자는 이름순을 유지하고 싶을 때입니다. 보통 병합 정렬로 구현되어 추가 메모리를 사용하고 sort보다 약간 느립니다.

vector<pair<int,int>> v = {{1,1}, {2,1}, {1,2}};
stable_sort(v.begin(), v.end());  // {1,1}, {1,2}, {2,1}

Q3: for_each vs 범위 기반 for?

A: 대부분 범위 기반 for가 더 간단합니다.

// for_each
for_each(v.begin(), v.end(), [](int x) { cout << x; });

// 범위 기반 for (더 간단)
for (int x : v) cout << x;

for_each가 여전히 의미 있는 경우는 일부 구간에만 적용할 때, 또는 C++17의 실행 정책(std::execution::par)과 함께 병렬로 돌릴 때 정도입니다.

Q4: 왜 algorithm을 사용해야 하나요?

A: 가장 큰 이유는 의도가 이름에 드러난다는 점입니다. for 루프 여섯 줄을 읽어야 알 수 있는 “조건에 맞는 원소 개수”가 count_if 한 줄로 표현되고, 경계 조건(<와 <=, 빈 컨테이너) 실수가 끼어들 여지도 줄어듭니다. 표준 라이브러리 구현은 오랫동안 검증되었고 sort처럼 직접 짜기 어려운 최적화가 들어가 있지만, 단순한 루프를 알고리즘으로 바꾼다고 항상 빨라지는 것은 아닙니다. 성능보다는 정확성과 가독성의 이점으로 보는 것이 정확합니다.

Q5: 커스텀 비교 함수는 어떻게 만드나요?

A: 람다, 함수 객체, 함수 포인터 모두 가능합니다.

// 람다
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

// 함수 객체
struct Greater {
    bool operator()(int a, int b) const { return a > b; }
};
sort(v.begin(), v.end(), Greater());

// 함수 포인터
bool descending(int a, int b) { return a > b; }
sort(v.begin(), v.end(), descending);

함수 포인터 예제의 이름을 greater로 지으면 using namespace std; 환경에서 std::greater와 충돌해 reference to 'greater' is ambiguous 에러가 납니다. 이 글의 예제들처럼 using namespace std를 쓴다면 표준 라이브러리에 있는 이름(greater, count, distance 등)을 피해야 합니다. 성능 면에서는 람다와 함수 객체가 유리합니다. 각 람다는 고유한 타입이라 컴파일러가 비교 호출을 인라인할 수 있지만, 함수 포인터는 간접 호출로 남는 경우가 많습니다.

Q6: 성능이 중요한 경우 팁은?

A: 먼저 알고리즘 선택을 확인합니다. 루프 안에서 find를 반복한다면 O(n²)이므로 정렬 후 lower_bound나 해시 컨테이너로 바꾸는 것이 가장 큰 개선입니다. 상위 k개만 필요하면 전체 sort 대신 partial_sort, k번째 값 하나만 필요하면 평균 O(n)의 nth_element를 씁니다. 결과를 back_inserter로 쌓는다면 reserve()로 재할당 횟수를 줄이고, 구조체를 비교·누적하는 람다는 const&로 받아 복사를 피합니다.

같이 보면 좋은 글