C++ std::copy·copy_if·copy_backward: 목적지 크기, 겹치는 범위, back_inserter
이 글의 핵심
std::copy는 목적지 공간을 확보해 주지 않기 때문에 빈 벡터에 그대로 복사하면 정의되지 않은 동작이 됩니다. 겹치는 범위에서 copy_backward가 필요한 이유, std::copy와 memcpy의 관계, reserve로 재할당을 줄이는 방법과 C++17 병렬 복사까지 다뤄 상황에 맞는 복사 알고리즘을 고를 수 있게 합니다.
복사 알고리즘이란?
<algorithm>의 복사 알고리즘은 한 범위의 원소를 다른 곳으로 복사하거나, 조건에 맞는 원소만 골라 복사하는 함수들입니다. 손으로 쓴 루프와 하는 일은 같지만, 의도가 함수 이름에 드러나고 경계 실수가 줄어듭니다.
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
// 손으로 쓴 루프
for (std::size_t i = 0; i < src.size(); ++i) dst.push_back(src[i]);
// 같은 일을 하는 알고리즘
std::copy(src.begin(), src.end(), std::back_inserter(dst));
모든 복사 알고리즘은 목적지로 출력 반복자를 받고, 그 반복자에 값을 대입하며 전진할 뿐입니다. 목적지 컨테이너의 크기를 늘려 주지 않는다는 점이 이 글에서 다룰 함정 대부분의 출발점입니다.
| 알고리즘 | 하는 일 |
|---|---|
copy(first, last, out) | 범위 전체 복사 |
copy_if(first, last, out, pred) | 조건이 참인 원소만 복사 |
copy_n(first, n, out) | 앞에서부터 n개 복사 |
copy_backward(first, last, d_last) | 끝에서부터 거꾸로 복사 (오른쪽으로 겹치는 경우) |
move(first, last, out) | 원소를 이동 |
move_backward(first, last, d_last) | 끝에서부터 이동 |
remove_copy(first, last, out, value) | 특정 값을 뺀 나머지 복사 |
remove_copy_if(first, last, out, pred) | 조건이 참인 원소를 뺀 나머지 복사 |
반환값은 모두 마지막으로 쓴 위치의 다음을 가리키는 출력 반복자입니다(copy_backward와 move_backward는 마지막으로 쓴 위치, 즉 목적지 구간의 시작). 이 반환값으로 실제로 몇 개가 쓰였는지 알 수 있습니다.
copy, copy_if, copy_n
세 함수는 입력 범위를 어떻게 정하느냐가 다릅니다.
std::vector<int> src = {1, 2, 3, 4, 5, 6};
std::vector<int> a, b, c;
std::copy(src.begin(), src.end(), std::back_inserter(a)); // 1 2 3 4 5 6
std::copy_if(src.begin(), src.end(), std::back_inserter(b),
[](int x) { return x % 2 == 0; }); // 2 4 6
std::copy_n(src.begin(), 3, std::back_inserter(c)); // 1 2 3
copy_if는 원본을 바꾸지 않고 조건에 맞는 원소만 새 시퀀스로 모읍니다. 같은 원본에서 합격자 목록과 불합격자 목록을 따로 만드는 식으로 여러 번 쓸 수 있습니다. 두 목록을 한 번에 나누고 싶다면 std::partition_copy가 원소마다 조건을 한 번만 평가합니다.
struct LogEntry {
std::string level;
std::string message;
};
std::vector<LogEntry> logs = /* ... */;
std::vector<LogEntry> errors;
std::copy_if(logs.begin(), logs.end(), std::back_inserter(errors),
[](const LogEntry& e) { return e.level == "ERROR"; });
copy_n은 끝 반복자 없이 개수만 지정하므로, 끝을 미리 알 수 없는 입력 반복자에서 앞부분만 가져올 때 씁니다. 다만 입력에 실제로 n개가 있어야 하고, 모자라면 정의되지 않은 동작입니다. 파일에서 헤더 512바이트를 읽는 경우처럼 입력 길이를 보장할 수 없다면, copy_n보다 read로 읽고 실제로 읽은 바이트 수를 확인하는 편이 안전합니다.
std::ifstream file("data.bin", std::ios::binary);
std::vector<char> header(512);
file.read(header.data(), header.size());
if (file.gcount() != static_cast<std::streamsize>(header.size())) {
// 파일이 512바이트보다 짧음
}
목적지 크기
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(3);
// dst에는 원소가 3개뿐: 4번째부터 범위 밖에 씀 (정의되지 않은 동작)
// std::copy(src.begin(), src.end(), dst.begin());
// 1: 목적지를 먼저 같은 크기로
dst.resize(src.size());
std::copy(src.begin(), src.end(), dst.begin());
// 2: back_inserter로 넣을 때마다 push_back
std::vector<int> dst2;
dst2.reserve(src.size()); // 재할당 방지
std::copy(src.begin(), src.end(), std::back_inserter(dst2));
dst.begin()은 이미 존재하는 원소를 가리키는 반복자이므로, 그 뒤로 원소가 모자라면 할당되지 않은 메모리에 씁니다. 빈 벡터에 std::copy(..., dst.begin())을 하는 실수가 가장 흔하고, 이때는 크래시 없이 조용히 메모리를 덮어쓸 수도 있어 찾기 어렵습니다. AddressSanitizer(-fsanitize=address)를 켜면 이 범위 초과를 바로 잡아 줍니다. 반면 libc++의 하드닝 디버그 모드는 copy 목적지 범위 초과를 잡지 못했습니다(아래 실측 참고).
reserve는 용량만 늘리고 원소 수(size)는 그대로입니다. reserve 후 dst.begin()에 copy하는 것은 여전히 정의되지 않은 동작이므로, reserve는 back_inserter와 함께 쓰고 resize는 begin()과 함께 씁니다. 크기를 알고 같은 타입이라면 사실 std::vector<int> dst(src.begin(), src.end());나 dst.assign(src.begin(), src.end());가 가장 간단합니다.
같은 벡터를 자기 자신 뒤에 이어 붙이려고 std::copy(v.begin(), v.end(), std::back_inserter(v))를 쓰면, 복사 도중 push_back이 재할당을 일으켜 읽고 있던 v.begin()~v.end() 반복자가 무효화됩니다. back_inserter 방식이라면 먼저 reserve(2 * v.size())로 재할당이 일어나지 않게 해 두면 원래 끝까지만 정확히 복사됩니다. 반면 v.insert(v.end(), v.begin(), v.end())는 reserve와 상관없이 표준이 금지하는 호출입니다(삽입할 범위가 자기 자신의 반복자이면 안 된다는 전제 조건). 이 경우는 복사본을 만들어 붙이는 것이 안전합니다.
겹치는 범위와 copy_backward
std::copy는 앞에서부터 차례로 대입합니다. 원본과 목적지가 같은 버퍼에서 겹치는데 목적지가 오른쪽으로 밀려 있으면, 아직 읽지 않은 원본을 먼저 덮어쓸 수 있습니다. 그래서 표준은 목적지 시작 위치가 원본 범위 [first, last) 안에 있으면 copy의 동작을 정의하지 않습니다.
std::vector<int> v = {1, 2, 3, 4, 5};
// 목적지 v.begin()+1이 원본 [begin, begin+3) 안에 있음: 정의되지 않은 동작
// std::copy(v.begin(), v.begin() + 3, v.begin() + 1);
// 오른쪽으로 밀 때는 copy_backward: 세 번째 인자는 목적지 구간의 끝
std::copy_backward(v.begin(), v.begin() + 3, v.begin() + 4);
// v: 1 1 2 3 5
// 왼쪽으로 당길 때는 copy로 충분
std::vector<int> w = {1, 2, 3, 4, 5};
std::copy(w.begin() + 2, w.end(), w.begin());
// w: 3 4 5 4 5
잘못된 copy가 실제로 어떤 결과를 내는지는 구현에 따라 다릅니다. 원소를 하나씩 대입하는 구현이라면 {1, 1, 1, 1, 5}처럼 같은 값이 번져 나가고, int처럼 트리비얼한 타입에 대해 memmove로 바꾸는 구현이라면 우연히 올바른 결과가 나옵니다. 어느 쪽이든 표준이 보장하지 않으므로, 컴파일러나 최적화 옵션을 바꿨을 때 결과가 달라질 수 있습니다.
copy_backward는 끝 원소부터 거꾸로 복사하므로, 오른쪽으로 밀 때 원본을 덮어쓰기 전에 읽습니다. 세 번째 인자가 목적지의 시작이 아니라 끝(마지막 원소 다음)이라는 점이 헷갈리기 쉽습니다. 이동 버전인 move_backward도 같은 규칙입니다. 방향이 헷갈리면 std::rotate처럼 겹침을 알아서 처리하는 알고리즘을 쓰거나 임시 버퍼를 거치는 것도 방법입니다.
move 알고리즘
<algorithm>의 std::move(first, last, out)는 원소를 하나씩 이동 대입합니다. 인자 하나를 받는 <utility>의 std::move(캐스팅)와 이름은 같지만 다른 함수입니다.
std::vector<std::string> src = {"a fairly long string that does not fit SSO", "another long string here"};
std::vector<std::string> dst;
dst.reserve(src.size());
std::move(src.begin(), src.end(), std::back_inserter(dst));
// dst에 두 문자열이 옮겨짐. src는 여전히 원소 2개를 갖지만 각 값은 지정되지 않음
std::string을 복사하면 원소마다 새 버퍼를 할당하고 내용을 복사하지만, 이동하면 버퍼 포인터와 길이만 넘기고 원본은 보통 빈 문자열이 됩니다. 그래서 차이는 바이트 수보다 힙 할당 횟수에서 나옵니다. 짧은 문자열은 SSO(Small String Optimization)로 객체 안에 저장되어 원래 힙 할당이 없으므로 복사와 이동의 차이가 거의 없습니다.
| 타입 | copy | move |
|---|---|---|
int, double | 값 복사 | 값 복사 (같음) |
짧은 std::string (SSO) | 객체 내부 버퍼 복사 | 거의 같음 |
긴 std::string | 힙 할당 + 내용 복사 | 포인터·길이만 이동 |
std::vector<T> | 힙 할당 + 원소 전체 복사 | 포인터 3개 이동 |
이동 후 원본 원소는 “유효하지만 값이 지정되지 않은 상태”입니다. 소멸시키거나 새 값을 대입하는 것은 안전하지만, 값을 읽어 어떤 값일 거라고 가정하면 안 됩니다. 원본 컨테이너의 원소 수도 그대로이므로, 다 옮긴 뒤 필요 없다면 src.clear()로 비웁니다.
원소가 const이면 std::move 알고리즘은 컴파일 에러 없이 조용히 복사합니다. const std::string&&는 이동 생성자가 아니라 복사 생성자에 바인딩되기 때문입니다. const std::vector<std::string>&로 받은 범위를 옮기려고 할 때 성능이 전혀 나아지지 않는다면 이 경우입니다.
함수에서 지역 벡터를 반환할 때는 알고리즘을 쓸 필요가 없습니다. return temp;는 컴파일러가 복사를 생략(NRVO)하거나, 생략하지 못해도 자동으로 이동합니다.
remove_copy와 remove_copy_if
remove_copy는 특정 값을 뺀 나머지를 목적지에 복사하고, 원본은 바꾸지 않습니다. remove_copy_if는 값 대신 조건을 받습니다.
std::vector<int> src = {1, 2, 3, 2, 4, 2, 5};
std::vector<int> dst;
std::remove_copy(src.begin(), src.end(), std::back_inserter(dst), 2);
// dst: 1 3 4 5, src는 그대로
std::vector<std::string> lines = {"hello", "", "world", "", "C++"};
std::vector<std::string> non_empty;
std::remove_copy_if(lines.begin(), lines.end(), std::back_inserter(non_empty),
[](const std::string& s) { return s.empty(); });
// non_empty: hello world C++
remove_copy_if(pred)는 copy_if(!pred)와 같은 결과입니다. 어느 쪽을 쓸지는 조건을 “남길 것”으로 표현하는 게 자연스러운지, “뺄 것”으로 표현하는 게 자연스러운지로 고르면 됩니다.
출력 반복자
목적지로는 컨테이너 반복자 외에 삽입 반복자와 스트림 반복자를 쓸 수 있습니다.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <set>
#include <vector>
std::vector<int> src = {1, 2, 3};
std::vector<int> v1;
std::copy(src.begin(), src.end(), std::back_inserter(v1)); // 1 2 3 (push_back)
std::vector<int> v2 = {10, 20};
std::copy(src.begin(), src.end(), std::inserter(v2, v2.begin())); // 1 2 3 10 20 (insert)
std::list<int> l;
std::copy(src.begin(), src.end(), std::front_inserter(l)); // 3 2 1 (push_front, 역순)
std::set<int> s;
std::copy(src.begin(), src.end(), std::inserter(s, s.end())); // set은 insert로만 넣을 수 있음
std::copy(src.begin(), src.end(), std::ostream_iterator<int>(std::cout, " ")); // 1 2 3
| 반복자 | 호출하는 멤버 | 쓸 수 있는 컨테이너 |
|---|---|---|
back_inserter | push_back | vector, deque, list, string |
front_inserter | push_front | deque, list, forward_list |
inserter | insert(pos, value) | 대부분의 컨테이너 (set, map 포함) |
ostream_iterator | operator<< | 스트림 |
inserter는 넣을 때마다 위치 반복자를 넣은 원소 다음으로 옮기므로 원래 순서대로 들어갑니다. vector 중간에 inserter로 n개를 넣으면 매번 뒤 원소를 미는 O(n·m) 작업이 되므로, 이 경우는 v.insert(pos, first, last)로 한 번에 넣는 편이 훨씬 빠릅니다.
성능
std::copy와 memcpy
libstdc++, libc++, MSVC STL은 원소 타입이 트리비얼하게 복사 가능하고(int, double, 트리비얼한 구조체) 반복자가 연속 메모리를 가리키면 std::copy를 내부적으로 memmove로 바꿉니다. 그래서 std::vector<int> 복사에서 std::copy를 std::memcpy로 바꿔도 대개 이득이 없습니다. 표준이 이 최적화를 요구하지는 않으므로 핫패스라면 생성된 코드나 프로파일로 확인하는 것이 맞습니다.
반대로 std::string, std::vector처럼 트리비얼하게 복사할 수 없는 타입에 memcpy를 쓰면 정의되지 않은 동작입니다. 내부 포인터가 그대로 복사되어 두 객체가 같은 버퍼를 소유하게 되고, 둘 다 소멸할 때 이중 해제가 일어납니다. std::is_trivially_copyable_v<T>로 컴파일 시점에 확인할 수 있습니다.
reserve
back_inserter로 n개를 넣으면 용량이 찰 때마다 재할당과 원소 이동이 일어납니다. 분할상환으로 보면 여전히 O(n)이지만 할당 횟수와 이동 비용이 붙으므로, 개수를 알면 reserve로 한 번에 확보합니다.
병렬 복사 (C++17)
#include <execution>
std::vector<int> dst(src.size());
std::copy(std::execution::par, src.begin(), src.end(), dst.begin());
실행 정책을 받는 오버로드는 순방향 반복자 이상을 요구하므로 back_inserter와 함께 쓸 수 없고, 목적지를 미리 resize해야 합니다. 단순 복사는 계산이 아니라 메모리 대역폭에 묶이는 작업이라 스레드를 늘려도 빨라지는 폭이 작고, 작은 범위에서는 스레드 관리 비용 때문에 오히려 느려집니다. GCC의 libstdc++에서 병렬 정책을 쓰려면 Intel TBB를 링크해야 한다는 점도 확인해야 합니다.
C++20 ranges
std::ranges::copy(src, dst.begin())처럼 범위 버전을 쓰면 반복자 쌍을 따로 넘기지 않아 begin과 end를 다른 컨테이너에서 가져오는 실수가 사라집니다. 반환값은 입력과 출력의 끝 위치를 함께 담은 구조체(in_out_result)입니다.
이 맥에서 직접 실행해 확인한 결과
환경은 Apple clang 21.0.0(libc++), macOS arm64, -std=c++20입니다. GCC·MSVC는 이 환경에 없어 확인하지 못했습니다. 시간은 -O2로 여러 번 돌려 가장 빠른 값을 적었고, 다른 프로세스가 도는 맥이라 순서와 대략의 배율만 참고하세요.
결과가 글과 같았던 것
copy_backward:{1,2,3,4,5}에서 앞 3개를 한 칸 오른쪽으로 밀면1 1 2 3 5였고, 왼쪽으로 당기는copy는3 4 5 4 5였습니다. 반환 반복자는copy가 끝 쪽(인덱스 5),copy_backward가 구간 시작 쪽(인덱스 3)이었습니다.- 출력 반복자:
back_inserter는1 2 3,inserter(v2, v2.begin())는1 2 3 10 20,front_inserter는3 2 1,set에inserter는1 2 3이었습니다. std::ranges::copy: 반환값의in은 입력의 끝,out은 쓴 구간의 끝(인덱스 6)이었습니다.- 트리비얼 여부:
is_trivially_copyable_v는int가true,std::string과std::vector<int>가false였습니다. const원본에std::move: 원본 원소가 그대로 42바이트로 남아 조용히 복사됐습니다.
겹치는 범위의 정의되지 않은 copy
같은 오른쪽 이동을 copy로 하면 vector<int>는 -O0, -O2 모두 1 1 2 3 5로 우연히 맞았습니다. memmove로 바뀌기 때문입니다. 반면 vector<std::string>({"a","b","c","d","e"})은 a a a a e로 앞 값이 번졌습니다. 글의 “트리비얼한 타입은 우연히 맞고 아닌 타입은 번진다”가 그대로 재현된 것입니다.
목적지 크기와 범위 초과 (ASan = -fsanitize=address,undefined, 하드닝 = -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG)
| 코드 | ASan | libc++ 하드닝 |
|---|---|---|
원소 3개짜리 dst에 5개 copy(…, dst.begin()) | heap-buffer-overflow(WRITE 20바이트, 12바이트 영역 바로 뒤) | 못 잡고 done 출력 |
빈 dst에 copy(…, dst.begin()) | SEGV on unknown address 0x0 | 못 잡음(출력 없이 종료) |
reserve(5)만 한 dst에 copy(…, dst.begin()) | container-overflow(크기 0 컨테이너에 씀) | size=0, 값은 쓰였지만 크기는 0 |
copy_n(src.begin(), 8, …)(입력은 5개) | heap-buffer-overflow(READ) | 못 잡고 8개를 복사, 마지막 값 0 |
글에서 디버그 모드로 범위 초과를 “대부분 바로 잡아 준다”고 한 부분은 libc++ 하드닝으로는 위 표처럼 잡히지 않았습니다. 이 맥에서는 ASan이 잡았습니다. -D_GLIBCXX_DEBUG와 MSVC 디버그 반복자는 확인하지 못했으므로 해당 문장은 “도구에 따라 다르다”로 고쳤습니다.
자기 자신 뒤에 이어 붙이기 ({1,2,3,4,5})
| 방법 | 결과 |
|---|---|
copy(…, back_inserter(v)), reserve 없음 | ASan heap-use-after-free. ASan 없이 실행하면 1 2 3 4 5 1 0 3 0 0처럼 값이 깨져 나옴 |
reserve(10) 후 같은 호출 | 1 2 3 4 5 1 2 3 4 5 |
v.insert(v.end(), v.begin(), v.end()) | 표준은 금지하지만 이 libc++에서는 reserve 유무와 상관없이 1 2 3 4 5 1 2 3 4 5로 맞게 동작 |
마지막 줄은 “되니까 써도 된다”가 아니라 “구현이 우연히 처리해 줄 수 있다”는 뜻입니다. 표준이 보장하지 않으므로 이식 코드에서는 복사본을 만들어 붙이세요.
move 알고리즘
긴 문자열 3개(42, 24, 5바이트)를 std::move로 옮긴 뒤 원본은 크기가 모두 0으로 남았고 원소 수는 3 그대로였습니다. 5바이트 짧은 문자열도 libc++에서는 비워졌으므로 “원본은 보통 빈 문자열” 정도로만 이해하는 것이 맞습니다. 값이 지정되지 않은 상태라는 점은 같습니다.
성능 (-O2, operator new 호출 횟수는 직접 센 값)
- 100MB(
int2,500만 개) 복사:std::copy2.3ms,memcpy2.3ms, 손으로 쓴 루프 2.32.5ms,2.4ms로 사실상 같았습니다. 컴파일된 코드에assign2.3std::copy가memmove호출로 바뀌어 있는 것도 확인했습니다. back_inserter로 1,000만 개 넣기:reserve없이 4.34.9ms(할당 25회),2.8ms(1회), 범위 생성자 0.9~1.2ms(1회)였습니다.reserve후 2.7reserve를 해도back_inserter는push_back경로를 타서 범위 생성자보다 느렸습니다.std::string20만 개(각 64바이트): 복사 3.2ms(할당 200,001회),move0.24ms(할당 1회)로 약 13배 차이였습니다. 8바이트(SSO) 문자열은 복사 0.21ms,move0.23~0.25ms로 차이가 없었습니다.vector앞에 2만 개 넣기(기존 2만 개):copy+inserter(v, v.begin())19~20ms,v.insert(v.begin(), first, last)0.005ms였습니다. 글의 “한 번에 넣는 편이 훨씬 빠르다”가 큰 폭으로 확인됐습니다.- 병렬 복사: 이 환경의 libc++에는
std::execution::par가 없어no member named 'par' in namespace 'std::execution'컴파일 에러가 났습니다. 본문의 병렬 복사 예제는 실행해 보지 못했고, 사용 가능 여부는 표준 라이브러리마다 다릅니다.