서론
C++에서 데이터를 저장할 때는 다양한 방식의 배열들을 사용할 수 있다. C-Style 배열부터 array, vector, list, deque 등 C++에서 제공하는 여러 배열(시퀀스 컨테이너)들은 각각의 특성과 용도에 따라 선택적으로 사용된다. 이번 글에서는 이러한 배열들의 특징과 차이점에 대해 알아보자.
C-Style 배열
C++을 처음 배울 때 가장 먼저 접하게 되는 배열로, 별도의 STL 없이도 사용할 수 있는 C++의 가장 기본적인 배열 형태이다. Primitive array라고도 불리며, 가장 빠르고 리소스를 적게 사용하는 반면, 제공하는 기능은 매우 제한적이다.
배열의 크기를 정해놓고 사용하거나, 동적 할당을 통해 런타임에 크기를 지정할 수도 있다. new를 사용한 동적 할당 시에는 반드시 delete 또는 delete[]를 통해 명시적으로 메모리를 해제해주어야 하며, 그렇지 않을 경우 메모리 누수가 발생할 수 있다.
사용 예시
#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5}; // 정적 배열
for (int i = 0; i < 5; ++i)
cout << arr[i] << " ";
cout << endl;
int* dynArr = new int[5]; // 동적 배열
for (int i = 0; i < 5; ++i)
dynArr[i] = i * 10;
for (int i = 0; i < 5; ++i)
cout << dynArr[i] << " ";
cout << endl;
delete[] dynArr; // 동적 메모리 해제
return 0;
}
std::array
std::array는 C++11에서 도입된 고정 크기 배열이다. C-Style 배열과 달리 STL이 제공하는 타입이기 때문에 반복자(iterator), 범위 기반 for문, .at() 메서드 등의 다양한 기능을 지원한다. 다만 크기가 컴파일 타임에 결정되며, 동적으로 변경할 수는 없다.
특징
- 크기는 고정 (템플릿 파라미터로 지정)
- 배열처럼 빠르며 STL 컨테이너처럼 편리
- std::sort와 같은 알고리즘과 함께 사용 가능
예시
#include <array>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
array<int, 5> arr = {5, 3, 1, 4, 2};
sort(arr.begin(), arr.end());
for (int val : arr)
cout << val << " ";
return 0;
}
std::vector
가장 많이 쓰이는 동적 배열이다. 크기를 자유롭게 조절할 수 있으며 메모리가 연속적으로 저장되어 내부적으로 메모리를 재할당하면서 요소를 저장한다. push_back()으로 원소를 추가할 수 있고, 메모리를 자동으로 관리해주기 때문에 메모리 해제에 신경 쓸 필요가 없다.
특징
- 동적 크기 조절 가능
- 메모리 재할당을 통한 확장
- 반복자, 알고리즘 사용 가능
예시
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> vec;
for (int i = 0; i < 5; ++i)
vec.push_back(i * 2);
for (int val : vec)
cout << val << " ";
return 0;
}
std::list
list는 이중 연결 리스트(doubly linked list)로 구성된 컨테이너로, 중간 삽입/삭제가 빠르다. 하지만 랜덤 접근이 불가능하고, 메모리 사용량이 많아지는 단점이 있다.
특징
- 빠른 삽입/삭제
- 순차 접근만 가능
- 메모리 오버헤드가 있음
예시
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> lst = {10, 20, 30};
lst.push_front(5);
lst.push_back(40);
for (int val : lst)
cout << val << " ";
return 0;
}
std::deque
deque는 양쪽 끝에서의 삽입과 삭제가 모두 빠른 컨테이너이다. 내부적으로 여러 블록의 배열을 조합하여 구현되어 있으며, vector보다 앞뒤 삽입/삭제가 효율적이다.
특징
- 앞/뒤 모두 빠른 삽입/삭제
- 랜덤 접근 가능
- 메모리 구조는 복잡하지만 성능은 우수
예시
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(10);
dq.push_front(5);
dq.push_back(15);
for (int val : dq)
cout << val << " ";
return 0;
}
배열 컨테이너별 시간 복잡도
| C-style 배열 | std::array | std::vector | std::deque | std::list | |
| 랜덤 접근 | O(1) | O(1) | O(1) | O(1) | ❌ (불가능) |
| 끝 삽입 | ❌ / O(1)* | ❌ | O(1) (amortized) | O(1) | O(1) |
| 앞 삽입 | ❌ / O(n) | ❌ | O(n) | O(1) | O(1) |
| 중간 삽입 | ❌ / O(n) | O(n) | O(n) | O(n) | O(1) (iterator 필요) |
| 끝 삭제 | ❌ / O(1)* | ❌ | O(1) | O(1) | O(1) |
| 앞 삭제 | ❌ / O(n) | ❌ | O(n) | O(1) | O(1) |
| 중간 삭제 | ❌ / O(n) | O(n) | O(n) | O(n) | O(1) (iterator 필요) |
| 메모리 재할당 | ❌ | ❌ | O(n) (필요 시) | O(n) (일부 상황) | ❌ (연결리스트 방식) |
❌: 지원하지 않거나 직접 구현이 필요
*: 정적 배열일 경우 크기 고정, 동적 할당일 경우 new/delete 사용에 따라 다름
**: vector의 push_back()은 대부분 상수 시간(O(1))에 수행되지만, 내부적으로 메모리를 동적으로 관리하기 때문에 일정 용량을 초과하면 더 큰 메모리 공간을 새로 할당하고 기존 데이터를 복사하는 작업이 필요하다. 이 과정에서는 시간 복잡도가 O(n)으로 증가할 수 있다. 즉, 평균적으로는 O(1)이지만, 최악의 경우 O(n)이 발생하는 것을 amortized O(1) 이라고 한다.
올바른 컨테이너 선택 방법
이 표만 보았을때 vector와 deque를 비교하면 deque가 vector보다 기능도 많고 시간복잡도도 오히려 나은 경우가 있어 vector를 사용할 이유가 없어보인다. 하지만 deque를 앞, 끝 원소를 빈번하게 삭제나 삽입을 해야하는 특수한 경우에만 사용하는 까닭은 시간 복잡도가 같은 O(1), O(n)이라도 컨테이너마다 차이가 있고 그것이 결코 작지 않다는 점이다.
예시로 다음과 같이 vector와 decue의 100만개의 원소에 순차적으로 접근하는 코드를 만들어 보았다.
#include <iostream>
#include <vector>
#include <deque>
#include <chrono>
#include <cstdlib> // rand
using namespace std;
using namespace chrono;
const int N = 10'000'000; // 원소 개수
const int TEST_COUNT = 1'000'000; // 접근 횟수
int main() {
vector<int> v(N);
deque<int> d(N);
// 데이터 초기화
for (int i = 0; i < N; ++i) {
v[i] = d[i] = rand();
}
// 벡터 랜덤 접근 테스트
long long sum_v = 0;
auto start_v = high_resolution_clock::now();
for (int i = 0; i < TEST_COUNT; ++i) {
int idx = rand() % N;
sum_v += v[idx];
}
auto end_v = high_resolution_clock::now();
auto duration_v = duration_cast<milliseconds>(end_v - start_v).count();
// 덱 랜덤 접근 테스트
long long sum_d = 0;
auto start_d = high_resolution_clock::now();
for (int i = 0; i < TEST_COUNT; ++i) {
int idx = rand() % N;
sum_d += d[idx];
}
auto end_d = high_resolution_clock::now();
auto duration_d = duration_cast<milliseconds>(end_d - start_d).count();
// 결과 출력
cout << "vector sum: " << sum_v << ", duration: " << duration_v << " ms" << endl;
cout << "deque sum: " << sum_d << ", duration: " << duration_d << " ms" << endl;
return 0;
}
결과는 다음과 같다:
이런 결과가 나오는 이유는 앞서 언급했듯이, vector는 메모리를 연속적으로 할당하는 반면, deque는 여러 개의 메모리 블록으로 나누어 데이터를 저장한다. 두 컨테이너 모두 접근 시간 복잡도는 O(1) 이지만, 실제 성능 차이는 CPU의 캐시 메모리 구조와 관련이 있다. vector는 데이터가 연속적으로 저장되어 있어 캐시 적중률(cache hit rate) 이 매우 높으며, 이는 반복 접근에서 큰 속도 향상을 가져온다. 반면 deque는 분산된 메모리 블록에 접근해야 하기 때문에 캐시 미스(cache miss) 가 더 자주 발생하고, 이로 인해 성능이 떨어지게 된다. (이에 대해서는 이전에 작성한 캐시 메모리에서 자세히 다뤘으니, CPU 캐시의 원리나 캐시 미스가 발생하는 구조를 더 알고 싶다면 참고하면 좋을 것이다.)