Array, 즉 배열은 메모리 상에 원소를 연속적으로 배치한 자료구조이다. C++에서는 예를 들어, int arr[10]; 으로 배열을 선언한 뒤에 길이를 바꿀 수 없지만, STL Vector를 사용하면 배열의 길이를 가변적으로 설정할 수 있다.
배열의 성질
- O(1)에 K번째 원소를 확인, 변경할 수 있다.
- 추가적으로 소모되는 메모리의 양(=Overhead)가 거의 없다.
- Cache hit rate가 높다.
- 메모리 상에 연속된 구간을 잡아야 해서 할당에 제약이 걸린다.
첫 번째 성질은 배열은 메모리 상에 원소를 연속적으로 배치한 자료구조라서, 시작주소에서 k칸만큼 오른쪽으로 가면 k번째 원소에 바로 접근할 수 있다.
두 번째 성질은 다른 자료구조에 경우에는 포인터와 같은 추가적인 정보를 각 원소마다 저장해야 하는데, 배열은 그렇지 않다.
세 번째 성질은 메모리 상에 연속적으로 배치되어 있기 때문에 지역성(Locality)가 높다.
네 번째 성질은 하나의 연속된 큰 메모리 블록이 필요하기 때문에 제약이 걸린다.
Vector란?
C++ 표준 라이브러리(STL)에서 제공하는 동적 배열 자료구조이다. 내부적으로는 일반 배열과 동일하게 원소를 연속적인 메모리 공간에 저장하지만, 원소를 추가하거나 제거할 때 자동으로 크기를 조정하여 메모리를 효율적으로 관리한다.
Vector의 핵심 동작 원리
Vector가 크기를 늘리고 줄이는 과정은 다음과 같다.
- Size(크기)는 현재 Vector에 실제로 저장된 원소의 개수이다.
- Capacity(용량)은 현재 Vector가 전체 메모리 공간에 저장할 수 있는 최대 원소의 개수이다.
- 만약 원소를 계속 추가하여 Capacity를 넘게 된다면, 현재 Capacity보다 더 큰(일반적으로 2배) 의 새로운 메모리 공간을 할당하고, 기존 Vector를 새로운 메모리 공간으로 복사한 후, 기존 메모리를 해제하는 O(N)의 시간 복잡도를 가지는 연산을 해야한다.
Vector 멤버 함수
- Vector 선언
- vector<변수 타입> 이름: 크기를 정하지 않는다.
- vector<변수 타입> 이름(크기): Vector의 크기를 정한다.
- vector<변수 타입> 이름(크기,초기화 상수): Vector의 크기를 정하고 모든 원소를 초기화 상수로 초기화 한다.
- Vector 원소 접근
- vector[idx]: 배열처럼 idx번째 원소를 참조한다.
- vector.at(idx): idx번째 원소를 참조한다.
- vector.front(), vector.back(): Vector의 첫 번째, 마지막 원소를 참조한다.
- vector.begin(), vector.end(): iterator로 Vector의 첫 번째 원소 위치, 마지막 원소 다음의 위치를 가리킨다.
- Vector 원소 삽입/삭제
- vector.push_back(value): Vector의 맨 뒤에 원소를 삽입한다. O(1)
- vector.pop_back(): Vector의 맨 마지막 원소를 삭제한다. O(1)
- vector.insert(idx,value): Vector의 idx번째에 원소를 삽입한다. O(N)
- vector.erase(iterator): 반복자(iterator)가 가리키는 곳의 원소를 삭제한다. O(N)
- Vector 크기
- vector.size(): 현재 Vector의 원소 개수(크기)를 반환한다.
- vector.capacity(): 할당된 Vector의 원소 개수를 반환한다.
- vector.size(): Vector의 크기를 반환한다.
- vector.resize(size): 현재 Vector의 크기를 size로 변경한다.
- vector.resize(size, value): 현재 Vector의 크기를 size로 변경하고, value로 초기화한다.
- vector.empty(): Vector가 비어있으면 true, 아니면 false를 반환한다.
