[C++] 벡터(Vector)
👻 STL
STL은 Standard Template Library의 약자로서 프로그래밍할 때 필요한 자료구조, 알고리즘들을 템플릿으로 제공하는 라이브러리이다. 여러가지 구성요소 중 컨테이너(Container)는 데이터를 저장하는 객체, 즉 자료구조(Data Structure)를 의미하는데, 이번 시간에는 컨테이너 중 하나인 벡터(Vector)에 대해 알아볼 것이다.
👻 벡터(Vector)
벡터(Vector)는 동적 배열을 의미한다. 동적 배열은 말 그대로 배열은 배열이지만 동적으로 변화하는 배열이다. 우리가 이제껏 사용해왔던 배열은 정적 배열로 크기가 고정되어있기 때문에 데이터를 추가로 담거나 삭제하는 등 유동적으로 관리해야 할 경우 관리가 힘들다는 단점이 있다. 이러한 단점을 보완한 것이 바로 동적 배열인 벡터이다. 사용법은 다음과 같다.
vector<[타입]> [변수명];
// ex
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
위처럼 선언하고 .을 이용해 벡터와 관련된 함수를 사용할 수 있다. 벡터를 사용할 땐 vector 라이브러리를 추가해줘야 한다.
#include <vector>
- push_back : 배열에 요소를 추가한다.
- size : 배열의 크기를 반환한다.
- 어떻게 배열을 유동적으로 사용할까?
우선, 동적 배열인 벡터는 메모리를 할당할 때 여유분을 두고 메모리를 할당한다. 여기까진 일반 배열과 별다른 차이점이 없지만, 여유분까지 꽉 찼으면 메모리를 증설한다는 차이점이 있다. 일반 배열은 한 번 설정한 배열의 크기에서 더 늘릴 수 없다.
🌱 vector의 동작 원리
벡터의 함수 중 배열의 크기를 나타내는 size와 여유분을 포함한 용량을 나타내는 capacity를 비교해보자.
- 예시 코드
vector<int> v; for (int i = 0; i < 1000; i++) { v.push_back(100); cout << v.size() << " " << v.capacity() << endl; } - 결과
..skip..
왼쪽은 size이고 오른쪽은 capacity의 결과값이다. size는 배열의 요소가 채워지면서 1씩 증가하는 걸 알 수 있고 capacity는 처음엔 1씩 늘어나다가 대략적으로 1.5배씩 증가하는 것을 알 수 있다.
우선 벡터도 배열은 배열이므로 연속된 메모리에 값이 저장되어야한다. 첫 생성 시 임의의 (여유분을 포함한) 메모리를 할당받은 후 데이터를 차곡차곡 쌓아가다가 여유분까지 모두 사용하게되어버리면 더 큰 메모리 공간으로 이사를 하게 되는 것이다. 기존에 있던 데이터들은 그대로 복사 이동된다.
잦은 복사가 이루어지면 아무래도 효율적인 측면에서 좋지 않으니 capacity를 초기에 세팅해줄 수 있는데, reserve 함수를 사용하여 설정해줄 수 있다.
v.reserve(1000);
위의 코드는 처음부터 capacity를 1000으로 설정해달라는 의미이다. 이렇게 설정하게되면 사이즈가 1000이 될 때까지 메모리를 이동하지 않아 효율적인 측면에서 좋지만 사이즈와 다르게 한 번 늘어난 용량은 다시 줄어들지 않는다. 물론 resize를 이용해 사이즈도 세팅시켜줄 수 있으며 벡터 선언과 동시에 사이즈 및 데이터를 지정해줄 수도 있다.
// resize 1000, value 0
vector<int> v(1000, 0);
- reserve :
capacity의 크기를 설정해준다.- resize :
size의 크기를 설정해준다.
이 외에도 다양한 함수들이 존재한다.
- front : 배열의 첫 요소를 출력한다.
- back : 배열의 마지막 요소를 출력한다.
- pop_back : 배열의 마지막 요소를 삭제한다.
- clear : 배열의 모든 데이터를 삭제한다.
- 늘어난
capacity도 초기화하고 싶으면swap함수를 이용한다.vector<int>().swap(v);
🌱 반복자
반복자(Iterator)는 포인터와 유사한 개념이다. 컨테이너의 원소(데이터)를 가리키고, 다음 혹은 이전 원소로도 이동이 가능하다는 특징을 가진다.
vector<int>::iterator it;
it = v.begin();
cout << (*it) << endl;
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
cout << (*it) << endl;
}
// it++ 보다 ++it이 조금 더 성능이 좋다. (Iterator ++ 연산자 오버로딩 차이)
위처럼 포인터와 유사하게 사용이 가능하다.
- begin : 배열의 첫 요소를 가리키는 Iterator를 반환한다.
- end : 배열의 마지막 요소의 다음을 가리키는 Iterator를 반환한다.
- 더 복잡해보이는데 굳이 사용을 해야할까?
👉 Iterator는 벡터 뿐 아니라, 다른 컨테이너에도 공통적으로 있는 개념이다. 다른 컨테이너는 벡터와 다르게v[i]와 같은 인덱스 접근이 안 될 수도 있다. STL 한정으로 통일성이 생기기 때문에 다른 자료구조로 넘어가기가 용이하다.
- const_iterator :
const int*와 동일한 의미. 데이터를 onlyread 할 경우에 사용한다.
vector<int>::const_iterator cit1 = v.cbegin();- reverse_iterator : 역방향으로 배열을 탐색한다.
vector<int>::reverse_iterator it = v.rbegin();
🌱 삽입과 삭제
- 중간 삽입과 삭제
배열의 중간을 건드리는 일은 상당히 비효율적이다. 중간에 새로운 값을 삽입하거나 삭제하게되면 뒤에 있는 모든 데이터가 한 칸씩 앞당겨지거나 뒤로 밀리게된다. 메모리를 많이 차지하는 배열일수록 데이터의 이동이 많아지게된다. 그래도 가능은한데 다른 함수보다 사용법이 복잡하다.
// 중간 삽입
vector<int>::iterator insertIt = v.insert(v.begin() + 2, 5);
// 중간 삭제
vector<int>::iterator eraseIt1 = v.erase(v.begin() + 2);
vector<int>::iterator eraseIt1 = v.erase(v.begin() + 2, v.begin() + 4); // 마지막은 포함 안 됨
insert와 erase로 삽입 혹은 삭제를 할 수 있다. 인자의 의미는 다음과 같다.
- insert : 삽입
- 첫 번째 인자 : 값을 추가할 위치(iterator)
- 두 번재 인자 : 추가할 값
- erase : 삭제
- 단일 인자 : 삭제할 값의 위치(iterator)
- 첫 번째 인자 : 삭제할 값의 시작 위치(iterator)
- 두 번째 인자 : 삭제할 값의 마지막 그 다음 위치(iterator)
erase는 함수 재정의가 되어있고 범위를 지정하기 위해 두 개의 인자를 받을 때, 두 번째 인자에 해당하는 값은 삭제되지 않는다.
- 처음/끝의 삽입과 삭제
처음 부분의 삽입과 삭제는 중간 삽입, 삭제와 동일한 동작을 한다. 맨 앞의 값을 추가하게되면 뒤의 모든 데이터가 한 칸씩 뒤로 밀리게 되고 맨 앞의 값을 삭제하게되면 뒤의 모든 데이터가 한 칸씩 앞당겨지게 된다. 중간 삽입, 삭제와 같이 비효율적이다.
반면, 끝의 삽입과 삭제는 편리하고 효율적이다. 그래서 함수 사용법도 간편하다.
// 끝의 삽입
v.push_back(1);
// 끝의 삭제
v.pop_back();
push_back과 pop_back으로 간편하게 배열의 끝부분에 접근할 수 있다.
🌱 임의 접근
임의 접근(Random Access)는 아무 값이나 쉽게 접근한다는 뜻으로 벡터와 같은 배열에서 지원한다. 배열은 데이터를 쉽게 찾기 위해 원소가 하나의 메모리 블록에 연속하게 저장된다는 특징이 있다. 이러한 특징이 임의 접근을 가능하게끔 해주는 것이다.
👻 글을 마치며
이번 시간에는 벡터에 대해 알아보았다. STL 문법을 다루는 첫 시간이기도하고 알고리즘 공부를 하면서 많이 봐왔던 문법이라 얼른 공부해보고 싶었는데 드디어 오늘 벡터에 대해 1부터 100까지 알 수 있었다. 확실히 개념부터 잡고 가니 응용이 쉬웠던 것 같다. 이터레이터도 동시에 공부했는데 알고리즘 때문에 벼락치기로 알았던 지식들이 하나 둘 퍼즐 맞춰지듯이 맞춰진 기분이다. 얼른 STL 마스터해야징!
Leave a comment