STL::vector 클래스 개요

vector는 c++ 유저라면 많이 사용해봤을법한 클래스이다.

 

array와 같이 연속된 메모리공간을 보장하면서 stack영역이 아닌 heap영역에서 메모리를 할당 받아서 사용하는 클래스이다.

 

따라서 메모리 할당 해제가 필요하다.

 

메모리 할당 해제는 자동으로 되기도 하고, 직접 reserve()함수를 이용해서 메모리를 할당받아 놔도 상관없다.

 

#include <iostream>

#include <vector>

 

using namespace std;

 

int main() {

        //cout << "hello world" << endl;

        vector<int> v;

        v.reserve(20);

        for ( int i = 0 ; i < 50 ; i++ ) {

                v.emplace_back(10);

                cout << "start addr     \t:" << v.data() << endl;

                cout << "vector count   \t:" << v.size() << endl;

                cout << "vector capacity\t:" << v.capacity() << endl << endl;

        }

        return 0;

}

 

출력값을 확인해본다면 for문 20회 까지 reserve를 통해 잡아놓은 capacity가 20으로 고정되어있고 그 이후 capacity가 증가하는것을 확인할 수 있다.

 

vector는 시작주소가 고정되어있고 메모리 주소가 연속적이기 때문에 Random Access에 O(1)의 시간 복잡도를 갖고 있다.

 

시작주소 + offset을 통해 바로 접근하면 되기 때문이다.

 

비슷한 개념으로 push_back, emplace_back, pop_back또한 O(1)이다. 다만, front에 push, pop, emplace하는 경우 이야기가 다르다.

 

왜냐하면 시작 주소가 고정되어 있기 때문에 front에 무언가를 추가하거나 뺄경우 모든 원소를 옮기는 n번의 스왑이 필요하기 빼문에 O(n)의 시간 복잡도가 필요하다.

 

stack과 같이 사용할 경우 O(1)의 시간 복잡도로 매우 빠르게 사용할 수 있는 반면 queue처럼 사용하게 된다면 손해를 볼 수 있다. 

 

데이터 저장갯수가 가변적이고 중간데이터에 대한 삭제, 삽입이 적고, Random Access가 많이 발생하는 곳이라면 vector container가 적당하다고 생각한다.

 

https://github.com/BeomSangKim/Cpp/tree/master/VectorTEST

BeomSangKim/Cpp

 

위 주소에서 내용을 예제를 확인하고 실행해봐도 좋다.