Reference:
- "전문가를 위한 C++" / 마크 그레고리 / 한빛 미디어
- "Optimized C++" / 커트 건서로스 / 한빛 미디어
1. 고정 크기 배열(C스타일 배열, std::array)
std::array는 C 스타일 배열의 향상된 버전. 그러나 std::array는 실제 응용 프로그램 개발에서 유용하게 사용할 수 있는 몇몇 기능을 제공하지 않는다는 단점이 있다.
- std::array의 크기는 컴파일 시간에 결정되는 상수이어야 한다. 따라서 프로그램 실행 중 변경 불가
- 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다. (고정 크기)
- std::array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용한다.
대부분의 실제 응용 프로그램에서 데이터는 동적이며 고정 크기가 아니다. 즉 데이터의 크기를 미리 알고 있기가 쉽지 않다. 그러므로 std::array를 사용하는 것은 항상 좋은 것이 아니며, 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하기도 하다.
=> std::vector로 이를 해결할 수 있다. (가변 크기)
source: https://hackingcpp.com/cpp/std/sequence_containers.html
2. std::vector
std::vector는 C 스타일 배열 또는 std::array가 가지고 있는 가장 두드러진 문제 중 하나인 '고정 크기' 문제를 해결한다. 초기화 과정에 데이터의 크기를 제공하지 않아도 된다.
// 크기가 0인 벡터 선언
std::vector<int> vec;
// 지정한 초기값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = {1, 2, 3, 4, 5};
// 크기가 10인 벡터 선언
std::vector<int> vec(10);
// 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);그 이유는 std::vector는 동적으로 크기를 조정할 수 있는 배열이기 때문이다. 배열의 항목은 벡터로 복사 생성된느 템플릿 매개변수 T의 인스턴스이며, 항목의 복사 생성자가 멤버를 위해 메모리를 할당할 수 있지만 std::vector는 항목을 내부 버퍼에 추가할 때 공간이 꽉 차서 재할당하는 경우에만 메모리 관리자를 호출한다.
만약 벡터의 크기를 명시적으로 지정하지 않거나 또는 초기값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 따른 용량을 갖는 벡터가 생성된다.
벡터의 크기는 실제로 저장된 원소의 갯수를 나타내며, 용량과는 다른 의미.
위 코드의 첫 번째 초기화의 경우, 크기는 0이지만 용량은 0 또는 작은 양수일 수 있다.
std::vector 반복자
std::vector의 반복자는 임의 접근 반복자이다. 즉 똑같은 벡터에서 두 반복자 사이의 거리를 상수 시간에 계산할 수 있음을 의미한다. 이러한 특성은 분할 정복 검색을 효율적으로 만든다(정렬되어 있다고 가정).
재할당의 성능 결과
std::vector에는 현재 벡터에 있는 요소의 개수를 나타내는 크기(size)와 요소를 저장하는 내부 버퍼의 크기를 나타내는 용량(capacity)이 있다.
크기와 용량이 같을 때 요소를 삽입하면 내부 버퍼를 재할당하고 벡터의 요소들을 새 저장 공간으로 복사한 뒤 기존 버퍼의 모든 반복자와 참조를 무효화하는 확장 작업을 수행한다. 이때 재할당 시 새 버퍼는 기존 용량의 몇 배 크기로 설정된다.
이렇게 하면 일부는 삽입하는 비용이 크지만 나머지는 그렇지 않으므로 전체적으로 비용이 일정하다는 효과를 가진다. 그럼에도 std::vector를 더 효율적으로 사용하는 방법은 reserve(size_t)를 호출해 사용 전에 용량을 예약하는 것이다.
clear()와 shrink_to_fit()
멤버 함수인 void clear()는 컨테이너의 크기를 0으로 설정하지만 내부 버퍼의 용량을 줄이기 위해 재할당한다고 보장하지 않는다. C++11의 void shrink_to_fin()은 벡터에게 용량을 현재 크기와 똑같은 값을 갖도록 줄이도록 한다.
관련 메서드
1. push_back()
push_back(val){
if size < capacity // capacity: 용량
- 마지막 원소 다음에 val 저장
- 벡터 크기를 1만큼 증가
- return;
if vector is already full // 할당된 메모리 공간이 가득 차 있는 경우
- 2*size 크기의 메모리를 새로 할당(동적)
- 새로 할당된 메모리로 기존 원소 전부를 복사/이동 (기존 메모리 공간은 이후 반환)
- 데이터 포인터를 새로 할당한 메모리 주소로 지정
- 마지막 원소 다음에 val을 저장하고, 벡터 크기 1만큼 증가맨 뒤에 원소를 삽입할 때, 뒤 쪽에 남아있는 공간이 있다면 O(1) 시간 복잡도
공간이 충분하지 않다면 O(n)의 시간 복잡도. 이러한 경우는 많지 않으므로 push_back() 연산의 평균 시간 복잡도는 O(1)에 가깝다.
2. insert()
insert() 함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있다.
지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하다. 필요한 경우 메모리를 새로 할당하는 작업도 수행된다. 원소들을 이동하는 연산 때문에 시간 복잡도는 O(n)이다.
std::vector<int> vec; // 비어있는 벡터 생성
vec.push_back(1); // 벡터 맨 뒤 1 추가 {1}
vec.push_back(2); // 벡터 맨 뒤 2 추가 {1, 2}
vec.insert(vec.begin(), 0); // 벡터 맨 앞 0 추가 {0, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4); // 원소 1 앞에 4 추가 {0, 4, 1, 2}3. pop_back()
벡터에서 맨 마지막 원소를 제거하며, 그 결과 벡터 크기는 1만큼 줄어든다.
남아있는 위치를 조정할 필요가 없으므로 매우 빠르게 동작하고, 시간 복잡도는 O(1)이다.
4. erase()
erase() 함수는 두 가지 형태로 오버로딩되어 있다.
1) 반복자 하나를 인자로 받아 해당 위치 원소를 제거.
2) 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거.
erase() 함수는 특정 위치 원소를 삭제한 후, 뒤 쪽의 원소들을 모두 앞으로 이동해야 하기에 O(n)의 시간 복잡도가 소요된다.
std::vector<int> vec = {0, 1, 2, 3, 4, 5};
vec.pop_back(); // 맨 마지막 원소 하나 제거 {0, 1, 2, 3, 4}
// 맨 처음 원소 제거
vec.erase(vec.begin()); // {1, 2, 3, 4}
// 2번째 원소부터 4번째 앞 원소까지 제거
vec.erase(vec.begin()+1, vec.begin()+3); // {1, 4}
추가 메서드
-
clear(): 모든 원소를 제거하여 완전히 비어있는 벡터로 만든다. 시간 복잡도는 O(1)이다.
-
reserve(capacity): 벡터에서 사용할 용량을 지정. 매개변수로 지정한 값이 현재 용량보다 크면 메모리를 매개변수 크기 만큼 재할당. 매개변수 값이 현재 용량보다 같거나 크면 아무런 동작을 하지 않음. 이 함수는 벡터의 용량을 변경시키는 것이지 크기를 변경하지는 않음.
-
shrink_to_fit(): 여분의 메모리 공간을 해제하는 용도로 사용. 함수 호출 시 벡터의 용량과 크기가 같게 설정됨. 벡터 크기가 더 이상 변경되지 않을 떄 사용하면 유용.
