C++ 컨테이너를 공부하면 흔히 이런 기준을 먼저 외우게 됩니다.
“중간 삽입과 삭제가 많으면 std::list, 빠른 인덱스 접근이 필요하면 std::vector를 사용한다.”
복잡도 표만 보면 맞는 말처럼 보이지만, 실무에서 컨테이너를 고를 때는 이것만으로 부족합니다.
메모리 배치, 캐시 지역성, 탐색 비용, iterator 안정성까지 함께 봐야 실제 성능과 코드 구조를 판단할 수 있습니다.
중간 삽입이 O(1)이라는 이유만으로 list를 선택하면 안 됩니다. 삽입 위치를 찾는 비용과 메모리 접근 비용까지 포함해 판단해야 합니다.
이번 글에서는 std::vector와 std::list의 차이를 코드로 비교하고, 대부분의 상황에서 vector가 기본 선택인 이유와 list가 필요한 조건을 정리해보겠습니다.
1. vector와 list는 무엇이 다른가?
std::vector는 원소를 연속된 메모리 공간에 저장하는 동적 배열입니다.
반면 std::list는 각 원소가 이전 노드와 다음 노드를 가리키는 이중 연결 리스트입니다.
두 컨테이너 모두 원소를 순서대로 보관하지만 내부 구조는 완전히 다릅니다.
| 구분 | std::vector | std::list |
| 메모리 배치 | 원소가 연속해서 배치됨 | 각 노드가 개별적으로 할당될 수 있음 |
| 인덱스 접근 | O(1) | 지원하지 않음 |
| 순차 탐색 | O(n), 캐시 친화적 | O(n), 포인터를 따라 이동 |
| 중간 삽입 | O(n) | 위치를 알고 있으면 O(1) |
| 추가 메모리 | capacity 여유 공간 | 노드마다 이전·다음 포인터 |
| iterator 안정성 | 재할당이나 삽입 위치에 따라 무효화 | 해당 원소를 삭제하지 않으면 대체로 유지 |
표에서 가장 자주 오해하는 부분은 list의 중간 삽입 O(1)입니다.
이 복잡도는 이미 삽입 위치를 가리키는 iterator를 가지고 있을 때만 적용됩니다.
값을 검색해서 위치를 찾아야 한다면 탐색에 O(n)이 필요합니다.
2. 메모리 구조로 이해하기
vector와 list의 성능 차이를 이해하려면 메모리 구조를 먼저 봐야 합니다.
vector는 원소가 연속되어 있어 CPU가 다음 원소를 예측하고 캐시에 가져오기 쉽습니다.
list는 노드가 메모리 곳곳에 흩어질 수 있고, 다음 원소로 이동할 때 포인터를 따라가야 합니다.
시간 복잡도가 둘 다 O(n)인 순회라도 실제 실행 시간은 같지 않을 수 있습니다.
vector는 연속 메모리와 작은 원소당 오버헤드 덕분에 순회에서 유리한 경우가 많습니다.
list는 각 노드에 링크 정보가 필요하고 개별 할당 비용도 발생할 수 있습니다.
따라서 Big-O는 알고리즘의 증가 추세를 보여주지만, 캐시 미스와 메모리 할당 비용까지 설명하지는 않습니다.
3. 같은 중간 삽입을 코드로 비교하기
다음 코드는 vector와 list의 두 번째 위치에 99를 삽입합니다.
결과는 같지만 내부에서 수행하는 작업은 다릅니다.
#include <iostream>
#include <list>
#include <vector>
template <typename Container>
void print(const Container& values) {
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
int main() {
std::vector<int> vectorValues{10, 20, 30, 40};
std::list<int> listValues{10, 20, 30, 40};
vectorValues.insert(vectorValues.begin() + 1, 99);
auto listPosition = listValues.begin();
++listPosition;
listValues.insert(listPosition, 99);
print(vectorValues);
print(listValues);
}
실행 결과
10 99 20 30 40
10 99 20 30 40
vector는 99가 들어갈 공간을 만들기 위해 뒤쪽 원소를 이동해야 합니다.
capacity가 부족하면 더 큰 메모리 공간을 할당하고 기존 원소 전체를 이동하거나 복사할 수도 있습니다.
list는 삽입 위치의 앞뒤 링크를 변경하고 새 노드를 연결합니다.
이미 listPosition을 알고 있으므로 이 삽입 자체는 O(1)입니다.
4. list의 O(1) 삽입에 숨은 조건
실무에서는 삽입 위치를 처음부터 알고 있지 않은 경우가 많습니다.
특정 값을 찾은 다음 그 앞에 새 값을 넣는다고 생각해보겠습니다.
#include <algorithm>
#include <iostream>
#include <list>
int main() {
std::list<int> values{10, 20, 30, 40};
auto position = std::find(values.begin(), values.end(), 30);
if (position != values.end()) {
values.insert(position, 99);
}
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
실행 결과
10 20 99 30 40
`insert` 호출만 보면 O(1)이지만, 값 30을 찾기 위한 std::find는 O(n)입니다.
따라서 전체 작업은 O(n)입니다.
반복적으로 같은 위치 근처를 수정하고 iterator를 계속 보관하는 구조라면 list의 장점이 살아날 수 있습니다.
반대로 매번 처음부터 위치를 검색한다면 복잡도 측면에서도 vector보다 압도적으로 유리하다고 말하기 어렵습니다.
5. vector가 순회에서 유리한 이유
컨테이너 전체를 자주 순회한다면 메모리 접근 패턴이 중요합니다.
CPU는 현재 읽은 메모리 주변의 데이터를 캐시 라인 단위로 가져옵니다.
vector 원소는 연속되어 있으므로 다음 원소가 이미 캐시에 들어올 가능성이 높습니다.
list는 다음 노드가 멀리 떨어져 있을 수 있어 노드를 이동할 때마다 캐시 미스가 발생할 가능성이 커집니다.
| 작업 | vector에서 기대할 수 있는 특성 | list에서 기대할 수 있는 특성 |
| 전체 순회 | 연속 접근으로 캐시 활용이 좋음 | 포인터 추적과 캐시 미스 가능성 |
| 인덱스 접근 | 즉시 접근 가능 | 처음부터 노드를 따라가야 함 |
| 메모리 할당 | 큰 연속 공간을 묶어서 관리 | 노드별 할당이 발생할 수 있음 |
| 원소 이동 | 삽입·재할당 시 발생 가능 | 기존 노드는 이동하지 않음 |
원소가 단순한 숫자나 작은 객체이고 읽기 작업이 많다면 vector의 장점은 더 커질 수 있습니다.
실제 성능은 원소 크기, 할당자, 데이터 수, 접근 패턴, 하드웨어에 따라 달라지므로 중요한 경로는 실제 데이터로 측정해야 합니다.
다만 측정 전 기본 선택이 필요하다면 일반적으로 vector부터 검토하는 편이 합리적입니다.
6. iterator 무효화는 어떻게 다른가?
성능만큼 중요한 차이가 iterator 안정성입니다.
vector가 재할당되면 기존 원소가 새로운 메모리 공간으로 이동하므로 모든 pointer, reference, iterator가 무효화됩니다.
재할당이 없더라도 중간에 삽입하거나 삭제하면 그 위치 이후를 가리키던 iterator가 무효화될 수 있습니다.
list는 특정 원소를 삽입해도 기존 원소를 가리키는 iterator가 유지됩니다.
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
int main() {
std::vector<int> vectorValues{10, 20, 30};
const std::size_t savedIndex = 1;
vectorValues.push_back(40);
std::cout << "vector value: "
<< vectorValues[savedIndex] << '\n';
std::list<int> listValues{10, 20, 30};
auto savedIterator = std::next(listValues.begin());
listValues.push_back(40);
std::cout << "list value: "
<< *savedIterator << '\n';
}
실행 결과
vector value: 20
list value: 20
vector 예제는 기존 iterator 대신 논리적 위치인 index를 보관하고 수정 후 다시 접근합니다.
push_back 과정에서 재할당이 발생했는지는 구현 상태에 따라 달라질 수 있으므로 기존 iterator를 계속 사용하면 안 됩니다.
list의 savedIterator는 다른 원소를 추가해도 기존 20 노드를 계속 가리킵니다.
안정적인 iterator를 장기간 유지해야 하는 알고리즘이라면 이 차이가 컨테이너 선택의 핵심이 될 수 있습니다.
7. reserve로 vector 재할당 줄이기
vector의 재할당 비용이 걱정된다면 예상 원소 수를 알고 있을 때 reserve를 사용할 수 있습니다.
reserve는 size를 늘리지 않고 capacity만 미리 확보합니다.
#include <iostream>
#include <vector>
int main() {
std::vector<int> values;
values.reserve(5);
for (int value = 10; value <= 50; value += 10) {
values.push_back(value);
}
std::cout << "size: " << values.size() << '\n';
std::cout << "capacity is enough: "
<< std::boolalpha
<< (values.capacity() >= 5) << '\n';
}
실행 결과
size: 5
capacity is enough: true
표준은 capacity가 정확히 5가 된다고 보장하지 않지만, 최소 5개 원소를 담을 공간은 확보하도록 보장합니다.
이 범위 안에서 push_back을 수행하면 capacity 증가로 인한 재할당은 발생하지 않습니다.
다만 reserve를 과도하게 크게 잡으면 사용하지 않는 메모리가 늘어날 수 있으므로 실제 예상 크기를 기준으로 사용해야 합니다.
8. 자주 하는 오해
오해 1. 중간 삽입이 있으면 무조건 list가 빠르다
삽입 위치를 찾는 비용, 노드 할당 비용, 순회 중 캐시 미스를 함께 봐야 합니다.
삽입 횟수가 적고 읽기와 순회가 많다면 vector가 더 적합할 수 있습니다.
오해 2. O(n)이면 실제 성능도 비슷하다
같은 O(n)이라도 연속 메모리를 읽는 것과 포인터를 따라 흩어진 노드를 읽는 것은 실행 특성이 다릅니다.
Big-O만으로 캐시 지역성, 할당 횟수, 원소 이동 비용을 비교할 수는 없습니다.
오해 3. vector는 원소가 많아지면 위험하다
vector는 크기가 커질 때 자동으로 저장 공간을 확장합니다.
문제는 확장 자체가 아니라 재할당 시 iterator와 reference가 무효화될 수 있다는 점입니다.
예상 크기를 안다면 reserve로 재할당 횟수를 줄일 수 있습니다.
오해 4. list는 원소를 이동하지 않으므로 항상 메모리 효율적이다
list의 각 노드는 원소 외에도 이전·다음 포인터를 저장합니다.
노드별 할당을 관리하기 위한 추가 비용도 있으므로 작은 원소를 많이 저장할 때 메모리 사용량이 커질 수 있습니다.
9. 실무에서는 무엇을 선택할까?
특별한 요구사항이 없다면 std::vector를 기본 선택으로 두는 것이 좋습니다.
연속 메모리, 빠른 순회, 인덱스 접근, 비교적 작은 메모리 오버헤드가 일반적인 애플리케이션에 잘 맞기 때문입니다.
std::list는 아래 조건이 실제로 필요할 때 검토할 수 있습니다.
- 기존 원소를 가리키는 iterator를 삽입 후에도 안정적으로 유지해야 한다.
- 삽입·삭제 위치를 가리키는 iterator를 이미 가지고 있다.
- 원소 이동이나 복사가 매우 비싸고 노드 기반 구조가 알고리즘에 자연스럽다.
- splice처럼 노드를 복사하지 않고 리스트 사이에서 옮기는 기능이 필요하다.
컨테이너 선택은 이름이나 복잡도 한 줄로 결정하기보다 실제 작업 비율을 기준으로 해야 합니다.
읽기와 순회가 대부분인지, 삽입 위치를 어떻게 찾는지, iterator를 오래 보관하는지, 원소 이동 비용이 큰지를 먼저 확인해야 합니다.
성능이 중요한 코드라면 실제 데이터와 배포 환경에서 benchmark를 수행하는 것이 최종 판단 기준입니다.
10. 정리
- vector는 연속 메모리를 사용해 순회와 인덱스 접근에 유리합니다.
- list의 삽입 O(1)은 삽입 위치 iterator를 이미 알고 있을 때의 복잡도입니다.
- 같은 O(n) 순회라도 캐시 지역성과 포인터 추적 때문에 실제 성능은 달라질 수 있습니다.
- vector는 재할당과 중간 삽입 시 iterator 무효화를 주의해야 합니다.
- 특별한 iterator 안정성이나 노드 이동 요구가 없다면 vector를 먼저 검토하는 것이 좋습니다.
컨테이너의 시간 복잡도는 선택의 출발점이지 결론이 아닙니다.
메모리 배치와 실제 접근 패턴까지 이해해야 실무에 맞는 선택을 할 수 있습니다.