[C++ STL] std::vector (시퀀스 컨테이너)

std::vector

시퀀스 컨테이너는 객체들을 순차적으로 저장하는 컨테이너.

std::vector는 배열의 형태로 객체를 순차적으로 저장하며 가변길이(동적) 배열이다.

즉 원소의 수가 증가하면 자동으로 배열의 메모리를 늘려 데이터를 저장한다.

 

먼저 std::vector를 사용하기 위해서 vector 헤더파일을 추가해야 한다.

기본적인 생성방법.

// 동적 배열이기에 처음에 크기를 정해줄 필요가 없다.
std::vector<int> v;
//0으로 초기화 된 10개의 원소를 가지는 vector를 생성.
std::vector<int> v(10);
//5로 초기화 된 10개의 원소를 가지는 vector를 생성.
std::vector<int> v(10,5);
//v2는 v1 vector를 복사.
std::vector<int> v2(v);

STL 컨테이너는 객체를 저장하고 관리하는 템플릿 자료구조.

그렇기에 템플릿 인자로 저장할 객체의 자료형(Type)을 넘겨야 한다.

 

멤버함수를 하나씩 살펴보자. (자주 사용하는 것 위주로)

 

1. at함수

std::vector<int> vc(10,2);
int index = 4;
int& value = vc.at(index); // vector의 index번째 원소를 참조한다.

사실상 배열의 arr[index]하는것과 결과는 동일하다. 다만 직접적으로 임의접근(random access) 연산을 사용하는 것보다

한번 범위체크를 하기에 안전하다는 장점도 존재하지만 임의 접근으로 연산하는 것보다 느리다는 단점도 존재한다.

 

2. operator [] 연산자

std::vector<int> vc(10,2);
int& value = vc[5];

배열이기에 가능하다. 배열은 나란히 이어진 형태로 메모리가 저장이 되기 때문.

내부적으로 []연산자를 오버로딩 하였다. at보다 속도 빠름.

 

3. push_back 함수

std::vector<int> vc(10,2);
vc.push_back(50);

배열 요소의 맨 뒤에 요소를 추가한다. 밑과 같은 배열의 형태가 있을 때

[1][2][3][4][5][ ][ ][ ][ ][ ] -> size 5, capacity 10. (이것은 밑에서 설명)

5라는 요소의 뒤에 데이터를 추가하게 된다. 걸리는 시간은 O(1). (예외 존재. 밑에서 설명)

 

std::vector에는 push_back은 존재하지만 push_front는 존재하지 않는다.

그 이유는 배열이 데이터를 저장하는 구조를 생각해보면 왜 없는지 이해하기가 쉽다.

 

[1][2][3][4][5][ ][ ][ ][ ][ ]

위와 같은 배열의 메모리에서 맨 앞의 즉 1에 데이터를 저장한다고 생각해보면

만약 std::vector에 push_front함수가 존재했고, 사용자가 vc[0] = 5; 과 같이 데이터를 덮어 씌우는게 아니라면

사용자가 push_front를 사용했다는 의미는 맨 앞에 데이터를 추가하겠다는 의미. (기존의 데이터를 유지하면서)

 -> 이럴 경우 그 뒤에 존재하는 요소들은 한칸씩 뒤로 밀수밖에 없다.

위와 같은 배열은 요소가 5개뿐이라 금방 한칸씩 뒤로 밀고 데이터를 추가하겠지만, 데이터가 만개가 넘어간다고 생각해보면 그 시간도 무시할 수 없다. -> 시간 복잡도가 O(N).

 

그렇기에 std::vector의 멤버함수에는 push_front라는 함수를 지원하지 않는다. 물론 사용자가 위와같은 처리를 따로 해줄 수 있긴하지만 그 일이 빈번히 발생한다면 std::vector 컨테이너를 사용하지 않는게 좋다.

 

4. pop_back

std::vector<int> vc(10,2);
vc.pop_back();

의미하는 바는 맨 뒤의 요소를 제거한다.

하지만 배열에서 이미 할당된 메모리에 해당하는 원소를 실질적으로 메모리를 삭제하는게 아니다.

[1][2][3][4][5][ ][ ][ ][ ][ ]

위와 같은 형태에서 맨 뒤의 요소는 5. pop_back함수를 호출하면 현재 size는 5가 아닌 4로 바뀔 뿐이다.

 -> 여기서 vc[4]와 같이 pop_back을 하고나서 요소를 접근하면 out of range 크래시를 터트려준다.

 

pop_back도 마찬가지로 pop_front가 존재하지 않는 이유는 push_back에서 설명한 이유와 동일하다.

맨 앞의 요소를 제거한다는 것은 그 뒤의 모든 요소를 한칸씩 앞으로 옮겨야 한다. 그 시간 복잡도는 O(N)

 

5. size,capacity ★

std::vector<int> vc(10,2); 
vc.size(); // 10을 출력
std::cout << vc.capacity(); // 10 출력
vc.push_back(10); // push_back 후
std::cout << vc.capacity(); // 15 출력

vector의 핵심 개념을 이해할 수 있는 함수.

먼저 의미 부터 설명해보면 size는 현재 vector에 담긴 요소의 수. capacity는 vector의 메모리 크기를 의미한다.

 -> 메모리 크기 == 할당된 공간의 크기

vector 컨테이너는 가변길이 배열이라 했다. 즉 일반 배열처럼 크기(길이)가 정해져있지 않다는 의미.

만약 현재 할당된 크기를 넘어 데이터를 저장할려고 할 시 vector는 새로운 메모리 공간을 만들고(기존의 1.5 혹은 2배)

기존의 vector의 배열에 담긴 요소들을 복사한 뒤 기존 배열의 메모리를 해제한다.

 

그 과정을 간단하게 코드로 표현해보면 밑과 같다. (간단하게 하기위해 int형으로 고정)

class Vector
{
public:
    Vector() : m_capacity(1), m_size(0), m_arr(new int[m_capacity]()) { }
    void push_back(int item)
    {
        m_arr[m_size++] = item;
        if (m_size >= m_capacity)
        {
            const unsigned int newSize = m_capacity * 2;
            m_capacity = newSize;
            int* newVector = new int[newSize]();
            unsigned int len = m_size * 4;
            ::CopyMemory(newVector, m_arr, len); // CopyMemory는 1바이트단위 복사
            delete[] m_arr; // 지우고
            m_arr = newVector; // 새로운 버퍼 가리킴.
            std::cout << "메모리 증설! capacity : " << m_capacity << std::endl;
        }
    }
    int& operator[](unsigned int pos)
    {
        return m_arr[pos];
    }
private:
    unsigned int  m_capacity;
    unsigned int  m_size;
    int*          m_arr;
};

100개의 데이터를 넣고 확인해보면

Vector클래스의 데이터를 저장하는 버퍼가 capacity를 넘어가면 크기를 2배씩 키운 후 데이터를 이어서 저장하는 구조.

std::vector도 이와 똑같은 구조다.

 

당연히 빈번한 메모리 증설은 오버헤드가 발생하고 속도저하의 원인이 된다. 그렇기에 vector를 사용할때에는 최대한 이러한 메모리 증설을 피하는게 좋다.

 

6. reserve함수 ★

위에서 벡터의 요소가 추가될 때 발생할 수 있는 메모리 증설은 최대한 피하는게 좋다고 했다.

그러한 메모리 증설을 막기 위해 자주 사용하는게 reserve함수.

reserve함수는 인자로 넘겨준 크기만큼 미리 메모리를 동적할당 시킨다.

처음에 벡터 컨테이너를 생성하고 데이터를 추가해보면 capacity는 1.

이러면 데이터를 조금만 추가해도 몇번이나 메모리 증설이 일어난다. 여기서 reserve함수를 사용하면.

위와같이 미리 메모리를 넘겨준 크기만큼 할당하기에 빈번한 메모리 증설을 막을 수 있다.

참고로 미리 메모리를 동적할당시킬뿐 어떤 요소를 채워넣는다던지등은 하지 않는다. -> resize가 이런일을 한다

 

reserve함수는 불필요한 재할당을 막기위해 vector를 생성한 직후 이 함수를 호출하는 습관을 들이는게 좋다.

 

7. resize 함수

std::vector<int> v;
v.resize(100);
std::cout << v.size() << " " << v.capacity();

resize는 정확히 벡터의 크기(size)를 변경하는 함수.

인자로 넘겨준 크기가 기존 vector의 크기보다 작으면 넘어가는 크기들의 메모리는 제거된다.

또한 인자로 넘겨준 크기가 기존 vector의 용량보다 크면 메모리 재할당이 일어난다.

 

인자로 100을 넘겨주었는데. 인자값을 하나만 넘겼을 시 100개의 요소를 vector에 0값으로 집어넣는다.

인자를 하나 더 넣게되면

해당 인자값으로 벡터에 요소를 채워넣는다.

여기서 더 작은 값을 줘버리면 (50)

size값만 줄어든다. 당연한거지만 size크기를 늘리기 위해서 capacity. 즉 메모리를 증설할 필요는 있지만, 다시 더 작은 크기로 줄인다해서 기존의 메모리를 부수고 더 작은 메모리 크기로 재할당할 필요는 없기때문.

 

8. swap 함수

std::vector<int> scores;  // 10 20 30 40
std::vector<int> scores2; // 60 70 80
 
scores.swap(scores2);  // 스왑 시
// scores  : 60 70 80
// scores2 : 10 20 30 40

말 그대로 두 벡터를 바꾸는 일을 한다. (같은 자료형)

swap함수는 서로의 벡터가 가지는 버퍼의 포인터,size,capacity만을 바꾸면 되므로 그리 비싼 연산은 아니다.

 

9. clear

std::vector<int> scores;  // 10 20 30 40
scores.reserve(20);
for (int i = 0; i < 20; ++i)
{
    scores.push_back(i + 1);
}
scores.clear(); // size를 0으로 만든다.

clear함수는 크기(size)를 0으로 바꾸고 용량은 변하지 않는다.

하지만 알듯이 실제 메모리에 있는 값이 삭제되거나 없어지는게 아니다.

그렇기에 해당 벡터의 size를 넘어가는 임의접근 연산을 하면 내부적으로 안전하게 크래시를 터트리게끔 설계되었다.

물론 꼼수로 가져오는 방법이 존재하지만 그렇게 사용은 X

 

10. empty

std::vector<int> scores; 
scores.empty();

해당 벡터의 크기가 0이라면 true를 반환 아니라면 false.

 -> capacity와는 관계가 없고 size와만 관계가 있다. (벡터 요소의 수)

 

11. begin,end,rbegin,rend

std::vector<int> scores;  // 10 20 30 40
scores.reserve(20);
for (int i = 0; i < 20; ++i)
{
    scores.push_back(i + 1);
}
auto beginIter = scores.begin(); 
auto endIter   = scores.end();
auto rBeginIter = scores.rbegin();
auto rEndIter = scores.rend();
 

begin,end,rbegin,rend함수는 벡터 컨테이너의 해당 요소를 가리키는 반복자(Iterator)를 반환한다.

 -> 단순히 해당 컨테이너의 요소(해당 자료형포함)를 가리키는 포인터.

이러한 반복자는 vector에서는 임의접근연산자가 있기에 많이 사용되지는 않지만 다른 컨테이너에서는 많이 쓰인다.

1. begin함수

 -> 벡터 컨테이너의 첫번째 요소를 가리키는 반복자를 반환한다.

2. end함수.

 -> 벡터 컨테이너의 제일 마지막 요소의 뒤(다음)를 가리킨다.

3. rbegin함수

 -> reverse begin의 줄임말. 벡터의 마지막요소를 첫번째 요소로 가리킨다.

4. rend함수

 -> reverse end의 줄임말. 벡터의 첫번째 앞(이전)의 요소를 마지막 요소로 가리킨다.

 

사용 방법

auto beginIter = scores.begin(); 
auto endIter   = scores.end();
for (;beginIter != endIter; ++beginIter)
{
    std::cout << *beginIter << " ";
}
std::cout << std::endl;
auto rBeginIter = scores.rbegin();
auto rEndIter = scores.rend();
for (; rBeginIter != rEndIter; ++rBeginIter)
{
    std::cout << *rBeginIter << " ";
}

결과 확인

 

 

vector 컨테이너의 장점

- 순서에 상관없이 임의접근 연산자를 이용하여 O(1)속도로 접근 가능.

- vector의 크기(size)의 뒤. 즉 마지막 위치에 요소를 삽입 및 삭제하는것은 빠르다.

 

vector 컨테이너의 단점

- 중간 및 처음에 요소 삽입 및 삭제는 느리다.

- 메모리 재할당 비용이 존재한다.