C++ Vector Container

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

 

0. 개요

---

vector는 C++에서 자주 사용되는 STL의 연속 컨테이너입니다. 카테고리로 묶어 설명하자면 string, dequem list와 마찬가지로 표준 STL 시퀀스 컨테이너 입니다.

 

제가 진행해온 프로젝트 경험에서는 vector가 가진 이점 때문에 플레이어, 몬스터, 환경체 등 현재 Scene에 있는 모든 오브젝트를 SceneMgr에서 vector로 관리하도록 만들었습니다.

사용할 때 큰 불편함이 없었지만, vector로 관리하는게 얼마나 효율적인 관리인지는 잘 모르겠습니다.

 

vector에 대한 간략한 소개를 마쳤으니 보다 자세히 살펴봅시다.

 

1. Vector Container란?

---

vector 컨테이너는 기존 배열(Array)와 다르게 자동으로 크기가 커지는 동적 배열입니다.

배열(Array)처럼 쓰지만 배열처럼 최대 크기가 정해져 있는 것이 아닌, 필요에 따라 유동적으로 확장되는 점이 큰 차이점 입니다.

이러한 이유 때문에 배열의 크기를 지정해주기 어려운 상황일 때 (예를 들어 SceneMgr에서 이번 Scene에 생성된 모든 오브젝트를 관리한다고 생각할 때, 배열을 사용하려면 배열의 최대 크기를 지정해 주어야 하는데, Scene에 얼마만큼의 오브젝트가 생성될지 모르기 때문에 배열을 사용하기가 까다롭습니다. 이럴 때 vector를 사용해주면 문제를 해결할 수 있습니다.) 배열보다 vector가 메모리를 효율적으로 사용할 수 있습니다.

이러한 요소 수가 증가함에 따라 크기가 커지는 것은 자동으로 메모리를 관리해주기 때문에 사용이 편리합니다.

뿐만 아니라 vector는 클래스 템플릿으로 만들어져 있습니다. 때문에 어떠한 자료형도 vector container 안에 넣어줄 수 있습니다.

vector와 배열의 공통적인 특징은 선형 배열로 저장된 요소가 연속된 메모리 공간에 위치한다는 점입니다.

또한 배열과 마찬가지로 저장된 임의의 요소에 쉽게 접근이 가능하다는 장점을 가지고 있습니다.

 

vector에도 단점은 존재하는데, 우선 메모리를 할당 받아 사용하기 때문에 시간이 추가적으로 걸리게 된다.

뿐만 아니라 vector에 데이터를 추가해 동적할당을 새로 받을 때, 단순히 메모리 공간을 늘리는 것이 아니라 새로운 메모리를 할당 받은 뒤, 해당 메모리에 데이터를 옮겨주는 작업을 거칩니다.

 

또 vector의 중간에 요소를 삽입하거나 삭제하면, 기존 데이터부터 끝까지의 데이터를 한 칸씩 뒤로 밀어주는 데이터 이동이 발생합니다. 때문에 가장 뒤에 있는 데이터를 지우거나 push_back()함수로 데이터를 추가할 때는 상수시간이 걸리지만, 중간에 데이터를 삽입하고 지우는 과정은 선형시간이 걸립니다.

 

이러한 이유 때문에 vector는 임의의 원소에 접근, 가장 뒤 원소에 대한 삽입, 삭제에는 유리 하지만 vector의 중간에서의 삽입, 삭제, 크기를 넘어 재할당하는 부분에서는 다른 STL에 비해 불리한 점이 있습니다.

 

정리하면 다음과 같습니다.

vector 컨테이너는 추가되는 요소 수에 따라 자동으로 메모리를 할당받아 배열의 크기가 커지는 동적 배열이다.
vector는 배열과 마찬가지로 저장된 요소가 연속된 메모리 주소를 갖는 선형 배열이다.
vector는 클래스 템플릿으로 만들어졌다.
때문에 vector는 어떠한 자료형도 담을 수 있는 컨테이너이다.
vector는 배열과 마찬가지로 저장된 임의의 요소에 쉽게 접근할 수 있다.
vector의 마지막 데이터를 삭제하거나, 추가할때 상수시간이 걸린다.
vector의 크기를 키울 때, 메모리를 새로 할당받아 데이터를 옮기기 때문에 시간 소요가 있다.
vector의 중간에서 삽입, 삭제 작업이 발생하면, 이후의 데이터들을 뒤로 밀어주어야 하기 때문에 선형시간이 걸린다.

 

2. Vector Container의 구조

---

기본적으로 배열과 비슷한 형태임을 알 수 있습니다. (위처럼 저장된 요소는 연속적인 메모리 공간을 갖습니다.)

C에서는 포인터로 배열의 값에 접근 및 수정을 할 수 있지만, vector는 iterator를 사용합니다.

 

3. Vector Container의 사용법

---

우선 vector를 사용하기 위해서 <vector> 헤더파일을 포함해주어야 합니다.

GNU 컴파일러를 사용한다면 <bits/stdc++.h> 헤더파일이 있어 편하다고 합니다.

vector도 namespace가 std에 있기 때문에 std::를 붙여 사용하거나, using namespace를 이용해 사용하면 됩니다.

#include <vector>
using namespace std;

void main()
{
    // vector의 선언
    vector<int> vec_num = {};
    
    // vector의 다양한 초기화 방법
    vector<int> vec_num2(10);
    vector<int> vec_num3(10, -1);
    vector<int> vec_num_Cp(vec_num2);
    
    return;
}

vector의 선언은 vector<데이터 타입> 변수이름; 입니다.

 

변수 선언뿐 아니라 초기화도 함께 진행할 수 있는데,

◈ vector<int> vec_num = {}; 은 비어있는 vector를 생성해 줍니다.

 

◈ vector<int> vec_num2(10); 은 0으로 초기화된 크기 10의 vector를 생성해 줍니다.

 

◈ vector<int> vec_num3(10, -1); 은 -1로 초기화된 크기 10의 vector를 생성해 줍니다.

 

◈ vector<int> vec_num_Cp(vec_num2);는 vec_num2를 복사한 vector를 생성해 줍니다.

 

이러한 선언과 초기화 방법을 이용해 vector 2차 행렬도 선언및 초기화 해줄 수 있습니다.

 

vector의 멤버 함수

vector는 지원하는 멤버함수가 매우 많아 유용하고, 다양한 활용이 가능합니다.

 

◈ v[idx];

    vector v의 idx번째 위치의 데이터를 참조합니다. (이는 배열의 사용감과 동일하도록 연산자 오버로딩되어 있습니다.)

 

◈ v.at(idx);

    vector v의 idx번째 위치한 데이터를 참조합니다.

    v[idx]보다 느린 방법이지만, 범위 초과를 방지하는 점검을 거친다는 차이가 있습니다.

 

◈ v.front();

    vector v의 첫 번째 데이터를 참조합니다.

 

◈ v.back();

    vector v의 마지막 데이터를 참조합니다.

 

◈ v.begin();

    vector v의 첫 번째 데이터를 가리킵니다.

    front()와 다르게 반환 타입이 iterator입니다.

 

◈ v.end();

    vector v의 마지막 데이터 다음을 가리킵니다.

    begin()과 마찬가지로 반환 타입은 iterator입니다.

    주의 할 점은 end()는 해당 vector의 마지막 데이터가 아닌, 완전 끝 이라는 점입니다.

 

◈ v.rbegin();

    vector v의 begin()과 반대로 뒤에서 첫 데이터 즉, 가장 마지막 데이터를 가리킵니다.

    back()과 마찬가지의 데이터이지만 반환타입은 iterator입니다.

 

◈ v.rend();

    vertor의 end()와 반대인 첫 데이터의 이전 위치를 가리킵니다.

    마찬가지로 반환 타입은 iterator입니다.

 

◈ v.push_back(data);

    vector의 마지막 데이터 뒤에 데이터를 삽입합니다.

    이때 vector의 공간이 부족하다면 다시 공간을 늘려 데이터를 삽입합니다.

 

◈ v.pop_back();

    vector의 마지막 원소를 제거합니다.

 

◈ v.clear();

    vector의 모든 원소를 제거합니다.

 

◈ v.reserve(n);

    n개의 데이터를 저장할 수 있는 공간으로 vector를 다시 동적할당 합니다.

 

◈ v.resize(n);

    vector의 크기를 n으로 변경합니다.

    원래 크기보다 작아지는 경우에는 뒤에서부터 지워지고, 원래 크기보다 커지는 경우엔 빈자리를 0으로 초기화합니다.

 

◈ v.resize(n, 5);

    vector의 크기를 n으로 변경하고 새로 추가된 빈 공간은 5로 초기화합니다.

    원래 크기보다 작아지는 경우에는 뒤에서부터 지워지고, 원래 크기보다 커지는 경우엔 빈자리를 5로 초기화합니다.

 

◈ v.size();

    vector의 데이터 갯수를 반환합니다.

 

◈ v.capacity();

    vector가 할당 받은 공간의 크기를 반환합니다.

 

◈ v2.swap(v1);

    v1과 v2의 모든것을 서로 바꾼다.

 

◈ v.insert(5, 2);

    5번째 위치에 2를 삽입한다.

 

◈ v.erase(iter);

    iterator iter가 가리키는 데이터를 삭제합니다.

    데이터가 삭제 되었으므로 vector의 size는 감소합니다.

    데이터가 삭제되면, 빈 공간이 생기는 것이 아니라 뒤의 데이터들이 앞쪽으로 땡겨지게 됩니다.

 

◈ v.erase(iter1, iter2);

    iter1부터 iter2이전까지의 데이터를 삭제합니다.

 

◈ v.empty();

    vector가 비어있으면 true, 비어있지 않는다면 false를 반환합니다.

    size가 0일때는 true가 반환됩니다.

 

보다 더 많은 함수에 대해서는 MSDN을 확인해 보시는것을 추천드립니다.

 

vector는 자동으로 크기가 필요한 만큼 늘어나는 배열이라고 볼 수 있지만, 동적할당에 시간이 걸리기 때문에 많은 메모리량이 필요한 것이 확실하다면 v.reserve(n) 함수로 필요한 만큼 미리 할당해놓을 수 있다.

 

4. size()와 capacity()의 차이점

---

vector의 내장 함수인 size()와 capacity()는 차이가 있다.

capacity()는 그저 vector에 할당되니 메모리를 의미하고, size()는 그 메모리 중에서도 데이터가 저장되어 있는 메모리량을 의미한다.

void main()
{
    vector<int> vec_num;

    for (size_t i = 0; i < 5; ++i)
    {
        vec_num.push_back(i);
    }

    int icapacity = vec_num.capacity();
    int isize = vec_num.size();
    
    return;
}

반복문을 이용해 vec_num에 0 ~ 4까지의 수를 저장해주고 두 함수를 확인해보았다.

capacity()의 결과로 6이 나오고, size()의 결과로 5가 나오는 것을 확인할 수 있다.

 

때문에 size()와 capacity()를 혼동하면 안된다.

 

예를들어 vector에 데이터를 넣어두고 for문을 이용해 순회하고자 한다면 capacity()를 사용하면 데이터가 들어있지 않은 공간에도 접근해 오류가 발생한다.

void main()
{
    vector<int> vec_num;

    for (size_t i = 0; i < 5; ++i)
    {
        vec_num.push_back(i);
    }

    for (size_t j = 0; j < vec_num.capacity(); ++j)
    {
        cout << vec_num[j] << endl;
    }

	return;
}

해당 코드를 실행해보면 vec_num에는 0 ~ 4의 수가 0 ~ 4의 index로 저장되어 있다.

하지만 중단점을 걸어 디버깅을 해 살펴보면 vec_num의 5번 index에는 아직 데이터가 저장되어 있지 않아 index 5에 접근하면 에러가 발생하게 된다.

 

이처럼 vector를 순회할 때는 size()를 사용하여 오류가 발생하지 않게 주의해야한다.

 

5. resize()와 reserve()의 차이

---

reserve()의 경우 배열을 만들때 int iarray[크기]를 선언하는 것과 동일하게 공간만 늘려준다. 즉, 초기화 처럼 데이터를 넣어주지는 않는다.

때문에 vector에 앞으로 데이터를 많이 넣을 것 같다면, reserve()를 이용해서 미리 공간을 늘려두면, 데이터가 다 차기 전까지 재할당을 받지 않아 성능을 향상시킬 수 있다.

뿐만 아니라 reserve()를 사용하는 것으로는 이미 할당받은 메모리 크기를 줄일 수 없다는 것이다.

즉, capacity가 64인 상태에서 reserve(2)를 한다고해서 capacity가 2로 줄지 않는다는 것이다.

 

resize()의 경우 공간을 늘리고, 해당 공간에 0이라는 초기 데이터를 넣어준다. 때문에 resize()로 공간을 키우고, push_back()을 하게되면 초기값이 들어가있는 공간 뒤에 데이터가 삽입되므로 주의해야 한다.

 

정리해보면, reserve()는 capacity를 늘려주고, resize()는 size를 늘려준다고 보면 편하다.

 

6. vector의 capacity

---

reserve()로는 이미 할당 받은 capacity를 줄일 수 없다는 것을 알 수 있었다.

erase()와 clear()를 사용해도 마찬가지로 저장된 데이터를 지워 size에만 영향이 있고, capacity에는 영향이 없다.

 

그렇다면 이 capacity 즉, 너무 크게 할당 받은 메모리 공간은 어떻게 줄일 수 있을까?

 

예전에 WinAPI를 이용해 게임을 만들 때 프레임이 떨어져 사용되는 메모리 공간을 조금 줄여보면 어떨까라는 호기심에 검색을 해보게 되었었다.

(프레임이 떨어지는 문제는 해당 문제는 아니었다.)

 

바로 swap() 함수를 이용해 데이터를 옮겨주면 된다.

 

swap()을 해주면 해당 vector와 데이터를 서로 바꾸기 때문에 capacity도 이에 맞게 받을 수 있다.

 

7. 반복자 Iterator

---

3번 항목에서 vector의 내장 함수들을 살펴볼 때 iterator로 반환해주는 함수들이 있었다.

그렇다면 이 iterator는 무엇일까?

 

Iterator(반복자)는 포인터와 상당히 비슷한 객체로 컨테이너에 저장되어 있는 원소들을 참조할 때 사용된다.

Iterator는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다.

뿐만아니라 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할도 한다.

알고리즘마다 다른 방식으로 컨테이너를 순회할 수 있기 때문에 컨테이너마다 Iterator도 여러 종류가 있다.

Iterator는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있어야 한다.

Iterator는 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 한다.

Iterator의 선언

Iterator는 일반적으로 다음과 같이 선언합니다.

container::iterator 변수명;

여기서는 vector를 설명하고 있으니, vector로 예시를 들면 다음과 같다.

vector<int>::iterator iter

보통 STL의 컨테이너 마다 begin()과 end()가 존재한다.

여기서 중요한 것은 begin()과 end()의 범위인데, 순차열의 시작은 begin() 끝은 end()이다.

end()는 실제 원소의 끝이 아닌 끝을 표시하는 원소이다.

 

이러한 방식은 2가지 장점이 있다.

◈ 원소를 순회하는 반복문을 간단히 할 수 있다. (end()에 다다르지 않으면 계속해서 반복문이 동작한다.)

◈ 비어있는 범위에 대해 다른 코딩을 할 필요가 없다. (빈 컨테이너일 경우 begin()과 end()는 동일하다.)

 

1번의 이유로 반복문은 다음과 같이 작성할 수 있다.

void main()
{
    vector<int> vec_num;
	
    vector<int>::iterator iter = vec_num.begin();
    for (; iter != vec_num.end(); ++iter)
    {
        cout << *iter << endl;
    }

    return;
}

!= 연산을 사용하면 된다. 이 연산은 모든 컨테이너에서 동일하게 사용이 가능하다.

random access 반복자일 경우 비교 연산 (<, >)등을 할 수 있다.

반복문에서 반복자를 증가시킬 때 후위(postfix)보다는 전위 연산자를 사용한다.

후위 연산자를 사용하면 반복자의 이전 값을 반환하기 때문에 임시로 객체가 생겨 성능이 늦어진다.

(클래스에서 증가연산자 overloading과 관련이 있다.)

 

iterator는 ++, --연산자를 사용해 증가, 감소 할 수 있다.

또 포인터를 사용하는 것과 비슷한 사용감으로 *를 이용해 역참조하는 것 처럼 iterator가 가리키는 객체를 반환받을 수 도 있다.

iter[3]을 이용해 iter + 3번째 원소(객체)를 반환받을 수 도 있다.

iter += 2 는 현재 iter 위치에서 2개 뒤의 원소(객체)로 접근한다.

 

반복자의 종류

◈ 입력 반복자 (input iterator) : 현 위치의 원소를 한 번만 읽을 수 있는 반복자 (istream)

◈ 출력 반복자 (output iterator) : 현 위치의 원소를 한 번만 쓸 수 있는 반복자 (ostream)

◈ 순방향 반복자 (forward iterator) : 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자

◈ 양방향 반복자 (bidirectional iterator) : 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자, !=, ==, ++, -- 연산이 가능하다. (list, set, multiset, map, multimap의 iterator)

◈ 임의 접근 반복자(random access iterator) : 양방향 반복자 기능에 +, -, ++, --, +=, -=, [], <, >, <=, >=, !=, == 연산이 가능한 반복자. (vector, deque의 iterator)

 

모든 컨테이너는 양방향 반복자 이상을 제공한다.

배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다.

 

참고 문헌

vector 클래스

[C++ vector] 사용법

[C++] Iterator에 대해서