C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
sort, find/find_if, accumulate, transform만 익혀도 직접 짜던 반복문의 상당 부분을 대체할 수 있습니다. 이 글은 이 기본 알고리즘들의 사용법과, 실제로 자주 틀리는 지점(remove 뒤 erase 누락, accumulate 초기값 타입, 비교자 규칙)을 함께 다룹니다. 13-1 vector와 함께 보면 좋습니다.
들어가며: 직접 짠 반복문의 문제
정렬은 이중 루프, 검색은 선형 탐색, 합계는 for로 누적하는 식으로 매번 반복문을 직접 쓰면 코드가 길어지고, 인덱스 범위·경계 조건·반복자 무효화에서 버그가 생기기 쉽습니다. STL 알고리즘은 <algorithm>·<numeric>에 정의된 함수들로, 반복자 범위 [begin, end)와 동작(함수/람다)만 넘기면 정렬·검색·변환·집계를 한 줄로 표현합니다. 이름만 보고도 “무엇을 하는 코드인지”가 드러나고, 경계 처리는 이미 검증된 구현이 맡습니다.
예를 들어 다음 코드는 정렬·검색·합계를 모두 직접 구현합니다.
// 수동 정렬·검색·합계
std::vector<int> vec = {5, 2, 8, 1, 9};
for (size_t i = 0; i < vec.size(); ++i) {
for (size_t j = i + 1; j < vec.size(); ++j) {
if (vec[i] > vec[j]) std::swap(vec[i], vec[j]);
}
}
int target = 8;
int index = -1;
for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i] == target) { index = i; break; }
}
int sum = 0;
for (size_t i = 0; i < vec.size(); ++i) sum += vec[i];수동 정렬은 O(n²)이고, 검색에서는 size_t인 i를 int index에 대입하는 부호 변환도 숨어 있습니다. 같은 동작을 STL 알고리즘으로 쓰면 다음과 같습니다.
#include <algorithm>
#include <numeric>
std::vector<int> vec = {5, 2, 8, 1, 9};
std::sort(vec.begin(), vec.end());
auto it = std::find(vec.begin(), vec.end(), 8);
int index = (it != vec.end()) ? std::distance(vec.begin(), it) : -1;
int sum = std::accumulate(vec.begin(), vec.end(), 0);sort와 다중 조건 비교 함수
std::sort 기본 사용법
std::sort는 반개구간 [begin, end) 에 있는 원소를 기본적으로 오름차순으로 정렬합니다. 내부적으로 보통 퀵소트/인트로소트 계열을 사용하며, O(n log n)입니다.
// g++ -std=c++17 -o sort_basic sort_basic.cpp && ./sort_basic
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9};
std::sort(vec.begin(), vec.end());
for (int x : vec) std::cout << x << " "; // 1 2 5 8 9
std::cout << "\n";
std::sort(vec.begin(), vec.end(), std::greater<int>());
for (int x : vec) std::cout << x << " "; // 9 8 5 2 1
std::cout << "\n";
return 0;
}sort(vec.begin(), vec.end())는 기본적으로 오름차순(less)으로 정렬합니다. 세 번째 인자로 std::greater<int>()를 넘기면 내림차순이 됩니다. <algorithm> 헤더가 필요합니다.
커스텀 비교 함수 (구조체 정렬)
원소가 구조체나 클래스일 때는 “어떤 기준으로 순서를 정할지” 비교 함수로 넘겨야 합니다.
#include <algorithm>
#include <vector>
#include <string>
struct Person {
std::string name;
int age;
};
int main() {
std::vector<Person> people = {
{"Alice", 25},
{"Bob", 30},
{"Charlie", 20}
};
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return a.age < b.age;
});
// Charlie(20), Alice(25), Bob(30)
}a.age < b.age면 나이 오름차순. “a가 b보다 앞에 오려면” true를 반환할 조건을 넣습니다. 내림차순은 a.age > b.age 또는 std::greater 활용.
완전한 sort 예제: 다중 조건 정렬
#include <algorithm>
#include <vector>
#include <string>
#include <tuple>
struct Student {
std::string name;
int score;
int id;
};
int main() {
std::vector<Student> students = {
{"Alice", 90, 1},
{"Bob", 85, 2},
{"Charlie", 90, 3},
{"David", 85, 4}
};
// 점수 내림차순, 점수 같으면 id 오름차순
std::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;
});
}<tuple>의 std::tie로 비교하면 return std::tie(b.score, a.id) < std::tie(a.score, b.id) 같은 형태로도 가능합니다. 다중 조건은 먼저 비교할 기준을 정하며, 같으면 다음 기준으로 비교합니다.
find, find_if와 정렬된 범위의 이진 검색
std::find: 값으로 검색
std::find는 값이 같은 첫 번째 원소를 찾아 그 위치를 가리키는 반복자를 반환합니다. 없으면 end()를 반환하므로, 반환값이 end()인지 꼭 확인한 뒤 사용해야 합니다.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
std::cout << "Found at index: " << std::distance(vec.begin(), it) << "\n";
std::cout << "Value: " << *it << "\n";
} else {
std::cout << "Not found\n";
}
}find(begin, end, value)는 값과 같은 첫 원소의 반복자를 반환하며, 없으면 end()를 반환합니다. it != vec.end()로 있는지 확인한 뒤, distance(vec.begin(), it)로 인덱스를 구할 수 있습니다. 정렬이 없어도 되지만 선형 O(n)입니다.
std::find_if: 조건으로 검색
특정 값이 아니라 “짝수”, “이름이 A로 시작”처럼 조건을 만족하는 첫 원소를 찾을 때는 std::find_if를 씁니다.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find_if(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; });
if (it != vec.end()) {
std::cout << "First even: " << *it << "\n"; // 2
}
}find_if는 predicate(참/거짓을 반환하는 람다)를 받아, 조건을 만족하는 첫 원소의 반복자를 반환합니다. 없으면 역시 end()를 반환합니다.
정렬된 범위: lower_bound / binary_search
범위가 이미 정렬되어 있을 때는 이진 검색이 O(log n)으로 유리합니다.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 정렬되어 있어야 함
if (std::binary_search(vec.begin(), vec.end(), 3)) {
std::cout << "Found\n";
}
auto lower = std::lower_bound(vec.begin(), vec.end(), 3);
auto upper = std::upper_bound(vec.begin(), vec.end(), 3);
std::cout << "Count of 3: " << std::distance(lower, upper) << "\n";
}binary_search는 “값이 존재하는지”만 true/false로 반환합니다. lower_bound는 “이 값 이상인 첫 위치”, upper_bound는 “이 값보다 큰 첫 위치”를 반환합니다. 같은 값이 여러 개일 때 [lower, upper) 구간이 그 값들 전체입니다.
count_if와 accumulate로 집계하기
std::count / count_if
std::count는 지정한 값과 같은 원소의 개수를 반환하며, std::count_if는 조건을 만족하는 원소의 개수를 반환합니다.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
int count = std::count(vec.begin(), vec.end(), 2);
std::cout << "Count of 2: " << count << "\n"; // 3
int evenCount = std::count_if(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; });
std::cout << "Even count: " << evenCount << "\n"; // 4
}count(begin, end, value)는 값과 같은 원소 개수를, count_if(begin, end, predicate)는 조건을 만족하는 원소 개수를 반환합니다. O(n)이며 정렬 여부와 관계없이 쓸 수 있습니다.
std::accumulate: 합산·곱셈·문자열 연결
std::accumulate는 범위를 왼쪽부터 하나씩 접어 나가는(fold) 연산입니다. 세 번째 인자는 초기값이고, 기본 동작은 합입니다.
#include <numeric>
#include <vector>
#include <string>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0);
std::cout << "Sum: " << sum << "\n"; // 15
int product = std::accumulate(vec.begin(), vec.end(), 1,
[](int a, int b) { return a * b; });
std::cout << "Product: " << product << "\n"; // 120
std::vector<std::string> words = {"Hello", " ", "World"};
std::string concat = std::accumulate(words.begin(), words.end(), std::string(),
[](const std::string& a, const std::string& b) {
return a + b;
});
std::cout << concat << "\n"; // Hello World
}accumulate(begin, end, 초기값)은 기본적으로 초기값 + 원소들의 합을 반환합니다. 네 번째 인자로 이항 함수를 주면 곱셈(초기값 1), 문자열 연결 등 다른 집계도 할 수 있습니다. <numeric> 헤더가 필요합니다. 빈 범위면 초기값이 그대로 반환됩니다.
transform으로 원소 변환과 두 컨테이너 결합
std::transform: 각 원소 변환
std::transform은 범위의 각 원소에 함수(또는 람다)를 적용한 결과를 다른 범위에 씁니다. 출력을 입력과 같은 범위로 주면 제자리(in-place) 변환이 됩니다.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
std::transform(vec.begin(), vec.end(), result.begin(),
[](int x) { return x * 2; });
// result: {2, 4, 6, 8, 10}
std::transform(vec.begin(), vec.end(), vec.begin(),
[](int x) { return x * 2; });
// vec: {2, 4, 6, 8, 10} (제자리 변환)
}transform(입력시작, 입력끝, 출력시작, 단항함수)는 각 원소에 람다를 적용한 결과를 출력 범위에 씁니다. 출력을 vec.begin()으로 주면 제자리에서 vec 자체가 바뀝니다. 출력 범위 크기가 미리 충분해야 합니다.
두 컨테이너 결합
transform에 입력 반복자를 두 쌍 주면, 두 시퀀스의 같은 위치 원소를 한 번에 받는 이항 함수를 쓸 수 있습니다.
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> result(a.size());
std::transform(a.begin(), a.end(), b.begin(), result.begin(),
[](int x, int y) { return x + y; });
// result: {5, 7, 9}
}두 범위의 같은 위치 원소를 (x, y) -> x + y 형태로 결합해 result에 씁니다. 처리 길이는 첫 번째 범위 [a.begin(), a.end())가 정하고, 두 번째 범위는 시작 반복자만 받으므로 최소한 그만큼 길다고 가정합니다. b가 a보다 짧으면 범위 밖을 읽는 미정의 동작이 되므로, 길이가 다를 수 있다면 호출 전에 확인해야 합니다.
로그 집계, 점수 통계, 필터링 예제
예제 1: 로그 데이터 정렬·검색·집계
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <string>
#include <vector>
#include <iostream>
struct LogEntry {
int64_t timestamp;
std::string message;
};
int main() {
std::vector<LogEntry> logs = {
{1000, "start"},
{500, "init"},
{1500, "done"}
};
std::sort(logs.begin(), logs.end(),
[](const LogEntry& a, const LogEntry& b) {
return a.timestamp < b.timestamp;
});
auto it = std::find_if(logs.begin(), logs.end(),
[](const LogEntry& e) { return e.message == "done"; });
if (it != logs.end()) {
std::cout << "Found at " << it->timestamp << "\n";
}
int64_t sum = std::accumulate(logs.begin(), logs.end(), int64_t(0),
[](int64_t acc, const LogEntry& e) {
return acc + e.timestamp;
});
std::cout << "Sum of timestamps: " << sum << "\n";
}예제 2: 점수 통계 (평균·최대·최소)
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> scores = {85, 92, 78, 90, 88};
int sum = std::accumulate(scores.begin(), scores.end(), 0);
double avg = static_cast<double>(sum) / scores.size();
std::cout << "Average: " << avg << "\n";
auto [minIt, maxIt] = std::minmax_element(scores.begin(), scores.end());
std::cout << "Min: " << *minIt << ", Max: " << *maxIt << "\n";
int above90 = std::count_if(scores.begin(), scores.end(),
[](int x) { return x >= 90; });
std::cout << "Above 90: " << above90 << "\n";
}예제 3: 문자열 벡터 변환 (대소문자·접두사)
#include <algorithm>
#include <cctype>
#include <iterator>
#include <string>
#include <vector>
int main() {
std::vector<std::string> words = {"Hello", "World", "C++"};
std::vector<std::string> upper;
upper.reserve(words.size());
std::transform(words.begin(), words.end(), std::back_inserter(upper),
[](const std::string& s) {
std::string r = s;
for (char& c : r) c = std::toupper(static_cast<unsigned char>(c));
return r;
});
}예제 4: 조건 필터링 + 변환 (copy_if + transform)
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
// 방법 1: copy_if로 짝수만 복사 후, transform으로 제곱
std::vector<int> evens;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(evens),
[](int x) { return x % 2 == 0; });
std::vector<int> evenSquared(evens.size());
std::transform(evens.begin(), evens.end(), evenSquared.begin(),
[](int x) { return x * x; });
// evenSquared: {4, 16, 36}
// 방법 2: 조건과 변환을 한 루프에서 (중간 벡터 없음)
std::vector<int> result;
for (int x : vec) {
if (x % 2 == 0) result.push_back(x * x);
}
}copy_if로 조건에 맞는 원소만 새 벡터로 복사한 뒤 transform으로 변환하면 각 단계의 의도는 분명하지만 중간 벡터가 하나 생깁니다. 이 정도 조합이라면 방법 2처럼 루프 하나로 쓰는 편이 오히려 간단할 수 있습니다. C++20 ranges를 쓰면 vec | std::views::filter(is_even) | std::views::transform(square)처럼 중간 컨테이너 없이 파이프라인으로 표현할 수 있습니다.
예제 5: accumulate로 구조체 집계
#include <numeric>
#include <vector>
#include <iostream>
struct Sale {
double amount;
int quantity;
};
int main() {
std::vector<Sale> sales = {{100.0, 2}, {50.0, 5}, {200.0, 1}};
double totalAmount = std::accumulate(sales.begin(), sales.end(), 0.0,
[](double acc, const Sale& s) {
return acc + s.amount * s.quantity;
});
std::cout << "Total: " << totalAmount << "\n"; // 100*2 + 50*5 + 200*1 = 650
}예제 6: stable_sort vs sort (같은 값 순서)
#include <algorithm>
#include <string>
#include <vector>
struct Task {
int priority;
std::string name;
};
int main() {
std::vector<Task> tasks = {
{1, "A"}, {2, "B"}, {1, "C"}, {2, "D"}
};
std::stable_sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) { return a.priority < b.priority; });
// priority 1: A, C (원래 순서 유지)
// priority 2: B, D (원래 순서 유지)
}예제 7: 필터 → 정렬 → 상위 N개 합계 (주문 데이터)
“완료된 주문만 골라 → 금액순으로 정렬하고 → 상위 5개 금액을 합친다”처럼 여러 알고리즘을 한 흐름으로 이어 쓰는 경우입니다.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <vector>
struct Order {
int id;
std::string status; // "pending", "completed", "cancelled"
double amount;
};
int main() {
std::vector<Order> orders = {
{1, "completed", 150.0}, {2, "pending", 80.0}, {3, "completed", 200.0},
{4, "completed", 90.0}, {5, "cancelled", 50.0}, {6, "completed", 120.0},
};
// 1. 완료된 주문만 추리기
std::vector<Order> completed;
std::copy_if(orders.begin(), orders.end(), std::back_inserter(completed),
[](const Order& o) { return o.status == "completed"; });
// 2. 상위 N개만 필요하므로 전체 정렬 대신 partial_sort
const std::size_t topN = std::min<std::size_t>(5, completed.size());
std::partial_sort(completed.begin(), completed.begin() + topN, completed.end(),
[](const Order& a, const Order& b) { return a.amount > b.amount; });
// 3. 상위 N개 금액 합계 (초기값을 0.0으로 줘야 double로 누적됨)
double total = std::accumulate(completed.begin(), completed.begin() + topN, 0.0,
[](double sum, const Order& o) { return sum + o.amount; });
std::cout << "Top " << topN << " completed total: " << total << "\n"; // 560
}완료된 주문이 4개뿐이라 topN은 4가 되고 합계는 560입니다. topN을 min으로 자르지 않으면 completed.begin() + 5가 범위를 벗어납니다. 또 상위 N개만 필요할 때는 전체를 sort하는 대신 partial_sort(또는 순서가 필요 없으면 nth_element)를 쓰면 정렬할 원소 수가 줄어듭니다.
STL 알고리즘 분류 다이어그램
flowchart TB
subgraph sort[정렬]
S1[sort]
S2[stable_sort]
S3[partial_sort]
end
subgraph search[검색]
F1[find / find_if]
F2[binary_search]
F3[lower_bound / upper_bound]
end
subgraph transform[변환]
T1[transform]
T2[copy_if]
end
subgraph agg[집계]
A1[accumulate]
A2[count / count_if]
A3[all_of / any_of / none_of]
end
input["(begin, end) 반복자 범위"] --> sort
input --> search
input --> transform
input --> agg
STL 알고리즘은 모두 반복자 범위 [begin, end)를 받아 동작합니다. 정렬·검색·변환·집계로 분류되며, 람다와 함께 사용하면 복잡한 조건도 표현할 수 있습니다.
accumulate 동작 흐름
flowchart LR
I["초기값 0"] --> A1["+ vec[0]"]
A1 --> A2["+ vec[1]"]
A2 --> A3["+ vec[2]"]
A3 --> A4[...]
A4 --> R["최종 결과"]
accumulate(vec.begin(), vec.end(), 0)은 ((0 + vec[0]) + vec[1]) + vec[2] + ... 형태로 합을 구합니다. 네 번째 인자로 이항 함수를 주면 곱셈, 문자열 연결 등 다른 집계도 가능합니다.
end() 비교 누락, remove 후 erase 누락, accumulate 초기값 실수
에러 1: find 반환값을 end()와 비교하지 않음
find는 값을 찾지 못하면 end()를 반환합니다. end()는 마지막 원소의 다음 위치라 역참조하면 미정의 동작이고, 결과는 크래시일 수도 있고 쓰레기 값일 수도 있습니다.
// 잘못된 사용
auto it = std::find(vec.begin(), vec.end(), 99);
int value = *it; // 없으면 end() 역참조 → UB
// 올바른 사용
auto it = std::find(vec.begin(), vec.end(), 99);
if (it != vec.end()) {
int value = *it;
}에러 2: remove만 쓰고 erase 안 함
std::remove를 호출해도 vec.size()는 그대로입니다. remove는 반복자만 받으므로 컨테이너 크기를 바꿀 수 없고, 남길 원소를 앞으로 모은 뒤 새 논리적 끝을 반환할 뿐입니다.
// 잘못된 사용
std::remove(vec.begin(), vec.end(), 2);
// vec.size()는 그대로!
// 올바른 사용 (erase-remove idiom)
vec.erase(std::remove(vec.begin(), vec.end(), 2), vec.end());에러 3: transform 출력 범위 크기 부족
transform은 출력 반복자 위치에 그대로 쓰기만 하고 컨테이너를 늘려 주지 않습니다. 출력 범위가 입력보다 작으면 범위 밖에 쓰게 되므로, 크기를 미리 맞추거나 back_inserter를 써야 합니다.
// 잘못된 사용
std::vector<int> result(vec.size() - 1); // 작음
std::transform(vec.begin(), vec.end(), result.begin(), ...);
// 올바른 사용
std::vector<int> result(vec.size());
std::transform(vec.begin(), vec.end(), result.begin(), ...);
// 또는 back_inserter (결과 크기 미리 모를 때)
std::vector<int> result;
result.reserve(vec.size());
std::transform(vec.begin(), vec.end(), std::back_inserter(result), ...);에러 4: accumulate 곱셈에서 초기값 0
곱셈 누적의 초기값을 0으로 주면 첫 단계부터 0 * x = 0이 되어 결과가 항상 0입니다. 곱셈의 항등원인 1을 줘야 합니다.
// 잘못된 사용
int product = std::accumulate(vec.begin(), vec.end(), 0,
[](int a, int b) { return a * b; });
// 항상 0
// 올바른 사용
int product = std::accumulate(vec.begin(), vec.end(), 1,
[](int a, int b) { return a * b; });에러 5: 정렬된 범위에 find 사용
이미 정렬된 큰 배열에서 검색을 반복한다면 find의 O(n) 선형 탐색은 낭비입니다. 정렬된 범위에서는 lower_bound로 O(log n)에 찾을 수 있고, 찾은 위치의 값이 실제로 같은지 한 번 더 확인해야 합니다.
// 잘못된 사용 (정렬된 범위에서)
auto it = std::find(vec.begin(), vec.end(), target);
// 올바른 사용
auto it = std::lower_bound(vec.begin(), vec.end(), target);
if (it != vec.end() && *it == target) {
// 찾음
}에러 6: 비교자에서 strict weak ordering 위반
std::sort의 비교자는 strict weak ordering을 만족해야 합니다. cmp(a, a)는 항상 false여야 하고, cmp(a, b)와 cmp(b, a)가 동시에 true가 되면 안 됩니다. <=를 쓰면 같은 값에서 이 규칙이 깨지고, 구현이 경계 검사를 생략한 분할 루프에서 범위 밖을 읽어 크래시가 날 수 있습니다.
// 잘못된 사용
std::sort(vec.begin(), vec.end(),
[](int a, int b) { return a <= b; }); // a==b일 때 문제
// 올바른 사용
std::sort(vec.begin(), vec.end(),
[](int a, int b) { return a < b; });에러 7: 빈 벡터에서 accumulate
평균을 구할 때 빈 벡터면 vec.size()가 0이라 0으로 나누게 됩니다. 또 int / size_t는 정수 나눗셈이라 소수점이 버려지므로 double로 변환한 뒤 나눠야 합니다.
// 잘못된 사용
int sum = std::accumulate(vec.begin(), vec.end(), 0);
double avg = sum / vec.size(); // 정수 나눗셈이라 소수점 버림, vec가 비면 0으로 나누기(UB)
// 올바른 사용
int sum = std::accumulate(vec.begin(), vec.end(), 0);
double avg = vec.empty() ? 0.0 : static_cast<double>(sum) / vec.size();에러 8: 반복자 무효화 — 순회 중 컨테이너 수정
순회 중에 erase나 push_back으로 벡터를 수정하면, 순회에 쓰던 반복자가 무효화되어 미정의 동작이 됩니다.
// 잘못된 사용
for (auto it = vec.begin(); it != vec.end(); ++it) {
if (*it == 0) vec.erase(it); // it 무효화
}
// 올바른 사용
vec.erase(std::remove(vec.begin(), vec.end(), 0), vec.end());
// 또는 erase 반환값 사용
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it == 0) it = vec.erase(it);
else ++it;
}에러 9: 정렬되지 않은 범위에 lower_bound
lower_bound·binary_search는 범위가 정렬되어 있다고 가정하고 반씩 건너뛰므로, 정렬되지 않은 범위에서는 에러 없이 의미 없는 결과를 돌려줍니다.
// 잘못된 사용
std::vector<int> vec = {5, 2, 8, 1, 9}; // 정렬 안 됨
auto it = std::lower_bound(vec.begin(), vec.end(), 5);
// 올바른 사용
std::sort(vec.begin(), vec.end());
auto it = std::lower_bound(vec.begin(), vec.end(), 5);에러 10: 문자열 accumulate에서 초기값
accumulate로 문자열을 연결하면서 초기값으로 ""를 넘기면 컴파일 에러가 납니다. 누적 타입이 초기값의 타입인 const char*로 정해지는데, const char* + std::string의 결과인 std::string을 다시 const char* 누적값에 대입할 수 없기 때문입니다.
// 잘못된 사용
std::string result = std::accumulate(words.begin(), words.end(), "");
// 올바른 사용
std::string result = std::accumulate(words.begin(), words.end(), std::string());에러 11: 정렬되지 않은 두 범위를 merge
std::merge 결과가 정렬되어 있지 않습니다. merge는 두 입력 범위가 이미 같은 기준으로 정렬되어 있다고 가정하고 앞에서부터 하나씩 비교해 내보낼 뿐입니다. 입력이 정렬되지 않았으면 결과도 정렬되지 않으며, 에러는 나지 않습니다.
std::vector<int> a = {5, 1, 9}, b = {8, 2, 6};
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::vector<int> out;
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 1 2 5 6 8 9에러 12: 입력과 겹치는 위치로 copy
같은 vector 안에서 원소를 오른쪽으로 밀려고 copy를 썼더니 값이 같은 숫자로 덮여 버립니다. std::copy는 앞에서부터 복사하므로, 출력 시작 위치가 입력 범위 안(입력보다 뒤쪽)에 있으면 아직 읽지 않은 원소를 먼저 덮어씁니다. 표준은 이 경우를 미정의 동작으로 둡니다.
std::vector<int> v = {1, 2, 3, 4, 5};
// 잘못: v[0..2]를 v[2..4]로 밀기: 출력이 입력과 겹침
// std::copy(v.begin(), v.begin() + 3, v.begin() + 2);
// 올바름: 뒤에서부터 복사하는 copy_backward (출력 범위의 끝을 넘김)
std::copy_backward(v.begin(), v.begin() + 3, v.end()); // v = 1 2 1 2 3반대로 원소를 왼쪽으로 당길 때(출력 시작이 입력 시작보다 앞)는 std::copy가 안전합니다. std::move/std::move_backward도 같은 규칙을 따릅니다.
에러 13: partition 반환값의 의미를 반대로 이해
조건을 만족하는 원소 개수를 잘못 셉니다. std::partition은 조건이 참인 원소를 앞으로 모으고, 조건이 거짓인 첫 원소를 가리키는 반복자를 돌려줍니다. [begin, 반환값)이 참인 구간, [반환값, end)가 거짓인 구간입니다. 참인 원소 수는 std::distance(v.begin(), 반환값)입니다. 원래 순서를 유지해야 하면 stable_partition을 씁니다.
성능: 수동 루프와 비교하면
| 작업 | 수동 for | STL 알고리즘 |
|---|---|---|
| 정렬 | 흔히 짜는 이중 루프는 O(n²) | sort는 O(n log n) |
| 검색 (비정렬) | O(n) | find도 O(n) |
| 검색 (정렬) | 직접 이진 검색을 짜지 않으면 O(n) | lower_bound는 O(log n) |
| 개수·합계·변환 | O(n) | count_if·accumulate·transform도 O(n) |
선형 작업(검색·집계·변환)은 같은 루프를 알고리즘 함수 안에서 돌리는 것이라, 최적화 빌드에서는 손으로 쓴 루프와 성능 차이가 거의 없습니다. 차이가 크게 나는 것은 정렬처럼 직접 짜면 더 나쁜 복잡도의 알고리즘을 고르기 쉬운 경우, 그리고 정렬된 데이터에서 이진 검색을 쓰느냐 마느냐입니다. STL 알고리즘을 쓰는 주된 이유는 속도보다 의도가 이름에 드러나고 경계 실수가 줄어든다는 점입니다.
nth_element와 partial_sort: 전체 정렬이 필요 없을 때
k번째 값 하나만 필요하면 nth_element가 평균 O(n)으로 충분합니다. 호출 뒤 v[k]에는 정렬했을 때 그 자리에 올 값이 들어가고, 앞쪽은 그보다 작거나 같은 값, 뒤쪽은 크거나 같은 값이 순서 없이 놓입니다.
std::nth_element(v.begin(), v.begin() + k, v.end());
int kth = v[k]; // 중앙값 등을 구할 때상위 k개를 순서대로 원하면 partial_sort를 씁니다. 비용은 O(n log k)라 k가 n보다 훨씬 작을 때 전체 정렬보다 유리합니다. vec.size()가 10보다 작으면 vec.begin() + 10이 범위를 벗어나므로 앞의 예제 7처럼 min으로 잘라야 합니다.
std::partial_sort(vec.begin(), vec.begin() + 10, vec.end(), std::greater<int>());알고리즘 선택 가이드
| 요구사항 | 추천 알고리즘 | 대안 |
|---|---|---|
| 전체 정렬 | sort | stable_sort(순서 유지), partial_sort(상위 k개) |
| 값 검색 (비정렬) | find, find_if | - |
| 값 검색 (정렬) | lower_bound, binary_search | - |
| 조건 만족 개수 | count_if | count(값 일치) |
| 합·곱·연결 | accumulate | - |
| 각 원소 변환 | transform | for_each(부수 효과만) |
| 조건 제거 | erase + remove_if | - |
| 중복 제거 | sort + unique + erase | - |
| 최대/최소 | max_element, min_element | minmax_element(둘 다) |
| 조건 분할 | partition | stable_partition(순서 유지) |
| 두 정렬 범위의 합·교·차집합 | set_union, set_intersection, set_difference | set_symmetric_difference |
| 제자리 수정 | fill, generate, replace, reverse, rotate | replace_if |
집합 연산과 제자리 수정 알고리즘
위 표 아래 두 줄은 앞 장에서 다루지 않은 계열입니다. 집합 연산은 두 입력이 모두 정렬되어 있다는 전제로 한 번씩만 훑어서(O(n + m)) 결과를 만듭니다. 정렬 안 된 입력을 넣으면 에러 없이 틀린 결과가 나오므로, 입력이 std::set이 아니라 vector라면 앞에 sort가 있는지 먼저 확인하세요.
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> out;
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 1 2 3 4 5 6 7
out.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 3 4 5
out.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // 1 2제자리 수정 알고리즘은 새 컨테이너를 만들지 않고 범위 안의 값을 바꿉니다. rotate는 “가운데 지점을 맨 앞으로” 옮기는 연산이라 리스트에서 원소 하나를 다른 위치로 옮기는 UI 로직(드래그 정렬)에 자주 쓰입니다.
std::vector<int> v = {1, 2, 3, 4, 5};
std::fill(v.begin(), v.end(), 0); // 0 0 0 0 0
std::iota(v.begin(), v.end(), 1); // 1 2 3 4 5 (<numeric>)
std::replace(v.begin(), v.end(), 3, 99); // 1 2 99 4 5
std::reverse(v.begin(), v.end()); // 5 4 99 2 1
std::rotate(v.begin(), v.begin() + 2, v.end()); // 99 2 1 5 4자주 쓰는 조합
정렬된 벡터에서 중복 제거 (sort + unique + erase)
unique는 인접한 같은 값만 하나로 줄이므로, 먼저 정렬해서 같은 값을 붙여 놓아야 합니다. remove와 마찬가지로 크기는 바꾸지 않으므로 erase가 필요합니다.
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());조건부 합계 (accumulate + 람다)
struct Metric {
std::string name;
double value;
};
double totalByCategory(const std::vector<Metric>& metrics, const std::string& cat) {
return std::accumulate(metrics.begin(), metrics.end(), 0.0,
[&cat](double acc, const Metric& m) {
return m.name == cat ? acc + m.value : acc;
});
}C++20 std::erase_if로 erase-remove를 한 줄로
C++20부터는 remove_if 뒤에 erase를 붙이는 관용구를 std::erase_if(v, pred) 한 줄로 쓸 수 있고, 지운 개수도 돌려받습니다. vector·deque·string뿐 아니라 list·map·unordered_map에도 오버로드가 있어, 컨테이너 종류가 바뀌어도 같은 코드를 쓸 수 있습니다.
std::vector<int> v = {1, 2, 3, 4, 5, 6};
auto removed = std::erase_if(v, [](int x) { return x % 2 == 0; }); // v = {1, 3, 5}, removed = 3C++17 이하 환경이라면 같은 동작을 하는 작은 헬퍼(c.erase(std::remove_if(c.begin(), c.end(), pred), c.end()))를 하나 만들어 두고 쓰면 erase 누락을 막을 수 있습니다.
STL 알고리즘 실무 주의점
개발 시 주의사항
- 한 번만 찾을 거면 정렬하지 마세요. 정렬(O(n log n)) 후
binary_search(O(log n))는 여러 번 검색할 때만 이득입니다. 검색이 한 번뿐이면find(O(n))가 더 쌉니다. “검색이니까 정렬부터”라는 습관은 오히려 코드를 느리게 만들 수 있습니다. accumulate초기값의 타입이 결과 타입입니다.double벡터를0으로 시작하면 매 단계int로 잘려서 합이 틀립니다.0.0(또는0LL)처럼 원하는 결과 타입으로 적으세요.std::vector<double> prices = {1.5, 2.5, 3.5}; auto wrong = std::accumulate(prices.begin(), prices.end(), 0); // 6 (int로 잘림) auto right = std::accumulate(prices.begin(), prices.end(), 0.0); // 7.5- 출력 범위는 알고리즘이 늘려 주지 않습니다.
transform·copy의 출력 반복자가 빈vector의begin()이면 범위 밖에 씁니다. 크기를 미리 맞추거나std::back_inserter를 넘기세요.
디버깅 방법
- 디버그 모드 반복자 검사: MSVC Debug 빌드나 GCC의
-D_GLIBCXX_DEBUG를 켜면 범위 밖 접근, 정렬 안 된 범위에binary_search같은 실수를 런타임에 잡아 줍니다. - 중간 결과 출력: 알고리즘을 여러 개 연결했다면 단계마다
for (auto x : v) std::cout << x << ' ';로 찍어 보면 어느 단계에서 틀어졌는지 바로 보입니다. - 비교자 검증: 정렬이 이상하면
std::is_sorted(v.begin(), v.end(), cmp)로 결과를 확인하고, 비교자가a < a에true를 돌려주지 않는지(strict weak ordering) 점검합니다.
참고 자료
이전 글: C++ vector 기초 | 초기화·연산·용량 관리와 실전 패턴
다음 글: C++ STL 고급 알고리즘: partition·merge·집합 연산·힙 연산