[자료구조] vector with C++ (1)

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

std::vector

　지난 시간에 크기가 고정되는 배열 std::array에 대해 살펴보았다. 예고한 것처럼 C 스타일의 배열의 한계를 극복한 가변 크기 배열 std::vector에 대해 알아보자. 벡터는 Cpp reference에 다음과 같이 정의되어 있다.

 

출처:&nbsp;https://en.cppreference.com/w/cpp/container/vector

 

　직역하자면 연속적으로 저장되는 가변 배열이라는 의미다. 즉, 연속된 자료구조이며 크기를 늘리거나 줄여 원소를 변경할 수 있는 배열이라고 생각하면 되겠다. 이러한 벡터를 사용하기 위해서는 vector 라이브러리를 받아와서 다음과 같은 형태로 사용하면 된다.

 

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

int main()
{
    vector<int> v = { 1,2,3,4,5 }; // 크기가 5인 int형 가변 배열
    vector<int> v1(5); // 크기가 5인 int형 가변 배열
    vector<int> v2(5, 1); // 크기가 5고 모든 원소가 1인 int형 벡터
}

---

vector의 특징

　벡터의 정의에서 알 수 있듯이 크기를 자유롭게 조절할 수 있다. 여기서 '용량(capacity)'이라는 용어와 '크기(size)'라는 용어가 나오는데, 사전적 의미로 인해 어떤 사물의 양이라는 같은 의미라고 착각하기 십상이다. 하지만 벡터의 크기는 벡터에 실제로 저장된 원소 개수를 나타내는 용어이며, 용량은 벡터가 수용할 수 있는 규모로서, 메모리가 할당되어 있는 공간의 양으로 조금 다르다. 다음 코드를 통해 이해해 보자.

 

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

int main()
{
    vector<int> v;

    for (int i = 1; i <= 5; ++i)
    {
        v.push_back(i); // i를 벡터 v에 삽입
        cout << "size: " << v.size() << ' ' << "capaicity: " << v.capacity() << endl;
    } 
}

std::vector.push_back(value): vector의 맨 마지막에 새로운 원소 value값 삽입
std::vector.size(): vector의 크기 반환
std::vector.capacity(): vector의 용량 반환

 

　이 코드를 실행시켰을 때 특이한 점이 하나 있다. 벡터의 용량과 크기가 계속 같은 사이즈로 유지되다가, 크기가 5일 때 용량이 6이 된다는 것이다. 이를 그림으로 표현하면 다음과 같다.

 

　

　즉, 가변 배열이라는 이름에 걸맞게 벡터에 값이 들어갈 때마다, 내부에서 자동적으로 여유 공간을 미리 할당한다고 생각하면 된다. 이때 늘어나는 수치는 어떻게 결정되는 걸까? 벡터에 값을 1부터 90까지 할당해 규칙을 찾아보자.

 

 

　노란색 점이 찍힌 곳이 용량이 변하는 시점인데, 대략 1.5 배씩 늘어나고 있다는 것을 확인할 수 있다. 왜 하필 1.5배일까? 이는 메모리 효율성과 확장 효율성 때문이다. 원문은 여기를 참고하고, 간단하게 설명하자면 다음과 같다.

 

　크기가 T인 벡터의 사이즈를 x만큼 늘린다고 했을 때, 다음 용량을 확장할 때는 T*x가 되고, 이는 곧 T*x^2이 된다. 결국 우리의 목적은 이전에 생성된 메모리(B.M으로 이하 줄임)를 다시 사용하는 것이기 때문에, B.M의 크기가 새 메모리보다 작아야 한다. 따라서 이를 수식으로 표현하면 

 

 

다음과 같이 되고, 이는 n이 2보다 크면 안 된다는 것을 의미한다. 즉, 용량의 증가량은 2배 이하가 되어야 한다. 만약 이보다 크면 여유 공간(실제 벡터가 들어가 있는 자리와 할당할 수 있는 공간의 차이)이 많이 비기 때문에 비효율적일 것이다. 반대로 factor가 너무 작다면 재할당이 자주 발생해 비효율적일 것이다.

 

　그렇다면 2배 이하의 요소(factor) 중에 가장 적절한 수는 어떻게 정하는 것일까? 이는 시간 복잡도와 관련되어 있다. 앞서 언급한 링크를 통해 답변을 보면 수학적으로 factor와 오버헤드 사이의 황금비ϕ에 해당하는 값을 찾는 답변이 있는데, 이에 근사한 값이 1.5이고, 시간 복잡도로 O(1)이라는 의미다. 

---

std::vector의 멤버 함수

push_back(), emplace_back()

　다음은 vector의 멤버 함수를 알아보자. 가장 많이 사용하는 push_back() 함수부터 알아볼 것인데, 그전에 push_back() 함수의 실행 과정을 슈도 코드(pseudocode)로 표현하면 다음과 같다.

 

push_bakc(value):
	if size < capacity // 여유 공간이 있을 때
    	- 마지막 원소 뒤에 value 저장
        - 벡터 크기++
        - return;
    
    if vecotr is full // 없을 때
    	- 1.5 * size 메모리 할당
        - 새로 할당한 메모리로 기존 원소들 모두 이동
        - 데이터 포인터를 새로 할당한 메모리 주소로 지정
        - 마지막 원소 뒤에 value 저장
        - 벡터 크기++

 

　벡터가 가득 차있으면 모든 원소를 이동하는 과정이 발생하므로 시간 복잡도가 선형 함수(O(n))이 되고, 여유 공간이 있으면 O(1)이 된다. 하지만 평균적으로 O(1)에 가깝다고 보면 된다. 하지만 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행하므로 비효율적이다.

 

　이러한 부분을 개선한 게 C++11부터 나온 emplace_back() 또는 emplace()이다. 이 함수는 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화된 것이다. 이 경우 새 원소 위치에 곧바로 객체가 생성되므로 생성자에 필요한 매개변수를 전달해야 합니다. 이를 감안해서 사용하지 않으면 에러가 발생하는데, 여기를 참고하자.

 

　이 외에 벡터에서 맨 마지막 원소를 제거하는 pop_back() 함수, 해당 위치의 원소를 제거하거나 범위의 시작과, 끝을 나타내는 반복자를 받아 시작부터 끝 바로 원소 앞까지 제거하는 erase() 함수, 모든 원소를 제거하는 clear() 함수, 용량을 지정하는 reserve() 함수, 여분의 메모리 공간을 해제하는 shrink_to_fit() 함수 등이 있으니 적절하게 사용하면 된다.

---

　벡터의 경우 C++에서 자주 사용하는 주요한 컨테이너라서, 다음 게시글에서 할당자와 벡터의 구현을 다뤄보도록 하겠다.

---

요약

std::vector
1. 정의: 크기를 자유롭게 조절하는 연속된 자료 구조
2. 특징
　a. 크기 조절 가능
　b. 임의 접근 가능 ( ex) v[1], v[3] )
3. 용어
　a. 크기(size): 실제로 저장된 원소의 양
　b. 용량(capacity): 메모리가 할당되어 있는 규모
4. 멤버 함수
- push_back(), emplace_back(), pop_back(), erase(), clear(), reserve(), shrink_to_fit() 등