[1. 리스트, 스택, 큐] C++ std::vector

std::array의 주요 단점
- array의 크기는 컴파일 시간에 결정되는 상수여야 한다. 프로그램 실행 중에는 변경할 수 없다.
- 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다.
- array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용한다.

-> 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다.

 

std::vector

---

std::vector는 가변 크기 배열로, 초기화 과정에 데이터의 크기를 제공하지 않아도 된다.

벡터의 초기화는 아래 코드처럼 여러 방법이 존재한다.

std::vector<int> vec; // 크기 0인 벡터
std::vector<int> vec = {1, 2, 3, 4, 5}; // 지정한 초기값으로 이루어진 크기가 5인 벡터
std::vector<int> vec(10); // 크기가 10인 벡터
std::vector<int> vec(10, 5); // 크기가 10이고 모든 원소가 5로 초기화된 벡터

 

벡터의 크기를 명시적으로 지정하지 않거나 초기값을 이용하여 크기를 유추할 수 있도록 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 따른 용량을 갖는 벡터가 생성된다. (벡터의 용량과 벡터의 크기는 다른 의미이다.)

 

원소 추가

push_back

벡터의 맨 마지막에 새로운 원소를 추가한다.

push_back의 pseudocode는 다음과 같다.

push_back(val):
	if size < capacity // 새 원소를 추가할 공간이 있는 경우
    	- 마지막 원소 다음에 val 저장
        - 벡터 크기를 1만큼 증가
        - return;
    if vector is already full // 할당된 메모리 공간이 가득 차 있는 경우
    	- 2 * size 크기의 메모리 새로 할당
        - 새로 할당한 메모리로 기존 원소 전부를 복사/이동
        - 데이터 포인터를 새로 할당한 메모리 주소로 지정
        - 마지막 원소 다음에 val 저장, 벡터 크기 증가

뒤쪽에 남아 있는 공간이 있다면 O(1)의 시간이 걸린다.

공간이 충분하지 않으면 모든 원소를 복사/이동해야하며 O(n)의 시간이 걸린다.

O(n)의 시간 동작은 n개의 원소를 추가한 후에만 발생하고, 이런 경우는 많지 않으므로 평균 시간 복잡도는 O(1)에 가깝다.

 

 

insert

원소를 삽입할 위치를 나타내는 iterator와 삽입할 원소를 받아 해당 위치에 새로운 원소를 추가한다.

원소를 이동하는 연산 때문에 O(n)의 시간이 걸린다.

 

push_back과 insert를 이용하여 다음과 같이 예제 코드를 작성할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> vec = {1, 2, 3, 4, 5};

    // 맨 앞에 0 추가
    vec.insert(vec.begin(), 0);

    vector<int> vec1;

    vec1.push_back(1);
    vec1.push_back(2);
    vec1.insert(vec1.begin(), 0);
    vec1.insert(find(vec1.begin(), vec1.end(), 0), 4); // 0 앞에 4 추가

    for(auto elem: vec1){
        cout << elem << " ";
    } // 4 0 1 2 출력

    return 0;
}

 

push_back과 insert를 사용하면 원하는 위치에 원소를 삽입할 수 있게 된다.

하지만 이들은 추가할 함수를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점에서 단점이 존재한다.

새로운 원소가 벡터 내의 추가될 위치에서 생성되는 방식으로 최적화할 수 있고, 이는 emplace_back()과 emplace() 함수를 사용하면 된다. 성능 향상에도 도움이 된다.

 

emplace_back, emplace

새 원소 위치에서 곧바로 객체가 생성된다.

생성자에 필요한 매개변수를 전달해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> vec = {1, 2, 3, 4, 5};

    vec.emplace(vec.begin(), 1);

    for(auto elem : vec){
        cout << elem << " ";
    }

    return 0;
}

 

원소 제거

pop_back

벡터에서 맨 마지막 원소를 제거하고, 벡터의 크기를 1만큼 줄인다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> vec = {1, 2, 3, 4, 5};

    vec.pop_back();

    for(auto elem : vec){
        cout << elem << " "; // 출력: 1 2 3 4
    }

    return 0;
}

가장 마지막 원소를 지우기 때문에 남아 있는 위치를 조정할 필요가 없어 매우 빠르게 동작한다.

O(1)의 시간복잡도를 가진다.

 

erase

1) 반복자 하나를 인자로 받아 해당 위치 원소를 제거한다.

vec.erase(vec.begin())

2) 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞까지 제거한다.

vec.erase(vec.begin() + 1, vec.begin() + 4)

특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 한다. 

O(n)의 시간복잡도를 가진다.

pop_back과 erase를 사용하여 예제 코드를 작성하면 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};

    vec.pop_back(); // 맨 마지막 원소 하나 제거 (1, 2, 3, 4, 5, 6, 7)

    vec.erase(vec.begin()); // 맨 앞 원소 제거 (2, 3, 4, 5, 6, 7)

    vec.erase(vec.begin() + 1, vec.begin() + 4); // 1번째 원소부터 3번째 원소까지 제거 (2, 6, 7)

    return 0;
}

 

추가적인 vector 멤버 함수

clear()

모든 원소를 제거하여 완전히 비어 있는 벡터로 만든다.

reserve(capacity)

벡터에서 사용할 용량을 지정한다.

capacity 값이 현재 용량보다 크면 메모리를 재할당하고, 작거나 같으면 아무런 동작을 하지 않는다. 

!! 벡터의 크기를 변경하는 것은 아님 !!

shrink_to_fit()

여분의 메모리 공간을 해제하는 용도로 사용한다. 

벡터의 용량과 벡터의 크기가 같게 되는데, 벡터 크기가 더 이상 변경되지 않을 때 사용한다.

 

vector 할당자

할당자를 전달하여 array의 단점을 해결할 수 있다.

사용자 정의 할당자도 사용할 수 있고, allocate(), deallocate(), construct(), destroy() 등의 함수를 제공해야 한다.

일반적인 힙 메모리 대신 자체적인 메모리 풀등을 사용해야 할 때 사용자 정의 할당자를 사용한다.