[C++ / STL] vector 분석

이 글은 완벽한 분석은 아닙니다.

평소 알고리즘 문제를 풀 때나, 개발하면서 Vector을 사용할 때 주로 사용했던 것들만 적었습니다 :)

완전한 메뉴얼은 C++ reference를 참고하시는 걸 추천합니다. 그냥 Vector를 바로 사용하고 싶은데 잘 모르는 경우 글을 한번 쭉 읽어보고 이해정도만 하시는 걸 추천드립니다.

 

함수를 하나하나 살펴보기 전에 Vector의 특성에 대해 살펴보겠습니다. (C++ reference참고했습니다.)

---

1. Vector의 특성

Vector는 크기를 변경시킬 수 있는 시퀀스 컨테이너입니다.

 

배열처럼 Vector는 원소에 연속 저장 위치를 사용하므로 원소에 대한 일반 포인터의 오프셋 []을 사용하여 배열처럼 효율적으로 원소에 액세스 할 수 있습니다. 그러나 배열과는 다르게 크기는 동적으로 변경될 수 있습니다.

 

내부적으로는 Vector는 동적으로 할당된 배열을 사용하여 요소를 저장합니다. 새 배열을 삽입할 때 크기가 커지려면 배열을 재할당해야 하는데, 이때 새 배열을 동적 할당받고 그곳으로 모든 데이터를 옮긴다고 생각하면 됩니다. (모두 복사됨) 이는 처리시간 측면에서 비교적 비싼 작업이므로 참고해야 합니다.

그래서, Vector의 크기를 안다면 미리 공간을 할당해두는 것이 합리적입니다.  이러한 내부적인 동작 때문에 push_back이 O(1) 시간에 이루어지지 않을 수도 있습니다. (amortized O(n)으로 동작. 진짜 거의 O(1)인데 가끔 O(n)이라... 고 생각하면 될 것 같아요.)

 

따라서 배열과 비교해서 Vector는 스토리지를 관리하고 효율적인 방식으로 동적으로 증가하는 기능을 가진 결과로 메모리를 더 소비합니다.

 

Random access iterator를 지원합니다. +, -, [], ++, --, -=, += 사용 가능.

 

2. Vector의 구성

Vector를 사용할 때 자주 사용했던 것들 위주로 설명하고 예를 들어 실행해보겠습니다.

 

 

2. 1) 생성자

생성자는 주로 쓰는 4가지만 소개하겠습니다. (그대로 긁어다가 실행하셔도 됩니다.)

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

int main()
{
	//(1)
	//Default 생성자
	cout <<"----------v1------------"<< '\n';
	vector<int> v1; 
	cout << "size : " << v1.size() << " capacity : " << v1.capacity()<<'\n\n';

	//(2)
	//Size를 매개변수로 넣는 생성자.... 0으로 모두 초기화됨.
	cout << "----------v2------------" << '\n';
	vector<int> v2(10);
	cout << "size : " << v2.size() << " capacity : " << v2.capacity() << '\n';
	for (int item : v2)
		cout << item << " ";
	cout << '\n\n';

	//(3)
	//Size와 원소들의 초기 값을 매개변수로 넣는 생성자.... 15칸 모두 1로 초기화
	cout << "----------v3------------" << '\n';
	vector<int> v3(15,1);
	cout << "size : " << v3.size() << " capacity : " << v3.capacity() << '\n';
	for (int item : v3)
		cout << item << " ";
	cout << '\n\n';

	//(4)
	//다른 Vector를 매개변수로 넣는 복사생성자... 
	cout << "----------v4------------" << '\n';
	vector<int> v4(v3);
	cout << "size : " << v4.size() << " capacity : " << v4.capacity() << '\n';
	for (int item : v4)
		cout << item << " ";
	cout << '\n\n';

	return 0;
}

결과

(1) 생성자

아무것도 채워지지 않은 텅 빈 Vector를 생성합니다.

 

(2) 생성자

크기를 미리 할당한 Vector를 생성합니다. 원소의 값들은 모두 0입니다.

 

(3) 생성자

선언과 동시에 15칸을 할당받고 모든 원소를 1로 초기화합니다.

 

(4) 생성자

매개변수에 들어가 있는 Vector와 똑같은 Vector를 생성합니다.

그 외 생성자 종류는 더 있습니다. Vector를 사용할 때 주로 사용했던 생성자만 나열했습니다.

 

 

2. 2) 반복자 (Iterator)

Vector는 Random access iterator를 지원하기 때문에 +, -, [], ++, --, -=, += 연산자를 사용할 수 있습니다.

 

특별한 점은 [n] 연산자를 사용해서 배열처럼 각 원소에 바로 접근할 수 있다는 점입니다.

 

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

int main()
{
	vector<int> v;
	for (int i = 1; i <= 7; ++i)
		v.push_back(i);

	cout << "---------[ ]사용---------" << '\n';
	for(unsigned int i=0; i<v.size(); ++i)
		cout << v[i] << " ";
	cout << "\n\n";

	cout << "---------반복자 사용---------" << '\n';
	//vector<int> ::iterator iter;
	for(auto iter = v.begin(); iter!= v.end(); iter++)
		cout << *iter << " ";
	cout << "\n\n";

	return 0;
}

위 코드의 결과

반복자, [] 연산자 모두 사용하여 접근 가능함을 나타내고 있습니다.

 

v의 원소들

Vector의 기본 메서드인 .begin()과  .end()가 반환하는 반복자의 위치입니다.

반복자에 ++연산자를 적용할 경우 오른쪽으로 한 칸 이동한다고 생각하시면 됩니다.

그래서 end()가 반환하는 반복자가 아닐 때까지 순회하여 값을 출력하는 형태를 나타냅니다.

 

반복자의 경우 vector<T> :: iterator 가 자료형입니다. T의 자리에는 Vector에 담긴 자료형을 나타냅니다.

처음에는 이걸 다 적으면서 사용했는데 이제는 그냥 auto를 사용하여 코드를 작성합니다.

 

잘 사용하지는 않는데 .rbegin()과 rend()가 있습니다. 이것도 그냥 ++연산자를 사용해서 처음부터 끝까지 순회하는데 역순으로 순회한다는 점이 다릅니다.

 

2. 3) Size & Capacity

Vector의 크기와 용량을 나타내는 부분입니다.

Vector의 Size는 실제 데이터가 담긴 크기, Capacity는 데이터가 있을 수도 없을 수도 있는데, 빈번한 메모리 동적 할당을 조금이나마 줄이기 위해 미리 할당받아놓은 메모리 사이즈라고 생각하면 될 것 같습니다.

 

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

int main()
{
	cout << "--------- v1 ---------" << '\n';
	vector<int> v1;
	for (int i = 1; i <= 8; ++i) {
		v1.push_back(i);
		cout << "size : " << v1.size() << " capacity : " << v1.capacity() << '\n';
	}
	for(int item : v1)
		cout << item << " ";
	cout << "\n\n";

	cout << "--------- v2 ---------" << '\n';
	vector<int> v2;
	v2.reserve(8);
	//v2[0] = 1;  -> Error!!
	v2.resize(6);
	v2[0] = 1, v2[1] = 2, v2[2] = 3, v2[3] = v2[4] = v2[5] = 0;
	cout << "size : " << v2.size() << " capacity : " << v2.capacity() << '\n';
	for(int item : v2)
		cout << item << " ";
	cout << "\n\n";

	return 0;
}

 

위 코드의 실행결과

 

위 코드의 데이터 구조

다음과 같은 형태로 나타내어져 있습니다.

 

주의 깊게 봐야 할 점은..

Push_back() 연산을 할 때 Capacity가 규칙적으로 증가하지 않고 한 번에 여러 칸을 할당받는 모습을 볼 수 있습니다.

그리고 Capacity가 할당되었다고 해서 iterator나 [] 연산자를 가지고 접근하면 에러가 날 수 있습니다.  위의 Vector에서 빈칸으로 된 부분은 데이터가 0이 아닙니다. Size를 벗어난 범위는 데이터가 존재하지 않는 영역입니다.

Size가 실제 데이터가 존재하는 크기이고 Size범위 내의 원소에만 접근이 가능합니다.

 

이 부분에서 주로 사용하는 메서드는

.size() : Vector의 Size를 반환

.resize() : Vector의 size를 재조정

    -> .resize(n) : Vector의 size를 n으로 재조정. 값은 0으로 초기화.

    -> .resize(n,x) : Vector의 size를 n으로 재조정하고 값을 x로 초기화.  

.reserve(n) : Vector의 Capacity를 n으로 조정

정도이다.

 

그외 

.empty() : 비어있는지 확인하는 메서드. Queue에서 많이 사용한다.

.shrink_to_fit() : Capacity를 Size의 크기에 맞춘다.

.capacity() : Capacity를 반환

등이 있는데 이 부분은 딱히 쓸 일이 없다.

 

 

 

2. 4) Element 접근

주로 [] 연산자를 사용해서 접근한다.

 

특별하게 

.at(index) 함수도 있는데, index번째의 원소의 값을 참조 형태로 갖고 온다. 참조 형태이므로 함수 호출과 동시에 값을 할당할 수 있다.

.front()는 첫 번째 원소를, .back()는 마지막 원소를 참조 형태로 반환한다.

front는 [0]으로 대부분 접근할 수 있는데 back()은 가끔 사용하는 것 같다. 벡터 크기가 유동적으로 변하기 때문에..

 

 

2. 5) Modifiers

여기서는 데이터를 만들고 수정하는 부분에 대해서 알아볼 것입니다.

 

여기서 주로 사용하는 부분은

push_back이 되지 않을까 싶습니다. push_back(value)은 정말 간단합니다. Vector의 마지막에 동적으로 값 value를 추가해줍니다. pop_back은 push_back의 반대 동작을 합니다. (마지막 원소 삭제)

 

 

그리고 가끔 사용할 일이 있는 메서드는

insert(), erase(), clear() 정도라고 할 수 있겠습니다.

insert와 erase는 삽입하거나 지우는 원소들의 뒷 원소들을 밀거나 당겨야 하기 때문에 시간 복잡도는 O(n)이 됩니다.

그리고 재할당이 일어나는 경우 최대 size의 크기만큼 연산을 한다고 합니다.(추가 비용)

 

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

int main()
{
	cout << "--------- v1 ---------" << '\n';
	vector<int> v1;
	for (int i = 0; i < 10; ++i)
		v1.push_back(i);

	for(int item : v1)
		cout << item << " ";
	cout << "\n\n";

	vector<int> ::iterator iter = v1.begin();
	iter++;	//[1]을 가리킴

	v1.insert(iter, 1000);
	//cout << *iter;	Error!!

	iter = v1.begin();
	iter++; //[1]을 가리킴.
	iter = v1.insert(iter, 9999);
	cout << "반환된 반복자는 : " <<*iter<<'\n';

	for (int item : v1)
		cout << item << " ";
	cout << "\n\n";
	
	return 0;
}

 

위의 코드 실행결과

여기서 중요한 부분은 iter위치에 삽입하고 다시 iter위치에 접근하려고 하면 에러가 발생한다는 점이다.

반드시 insert 후 반환된 iter를 사용해야 그 삽입한 위치의 iter를 사용할 수 있다.

 

여러 값을 삽입하고 싶을 때는 (insert 할 위치의 iter, insert 할 변수의 시작 부분의 반복자, 끝 부분의 반복자)를 사용해서 여러 값을 삽입할 수 있다.

 

erase도 마찬가지이다. iter위치의 값을 삭제할 수 있고, erase(삭제 시작 부분 반복자, 삭제 종료 부분 반복자)를 사용해서 범위 단위로 삭제를 진행할 수 있다.

 

 

그 외의 emplace_back 같은 경우는 구조체나 클래스를 삽입할 때 뭐 좀 더 빠른 속도로 할 수 있다, 복사가 일어나지 않는다 였나... (정확한 건 아닙니다.) 여하튼 단순 push_back보다 내부적으로 잘 처리한다는 것 같았습니다. 이 부분은 구글에 검색하면 나오니 찾아보시길 바랍니다. swap 같은 경우는 잘 사용하지 않았습니다. 그래도 한 번쯤은 사용해보는 걸 추천드립니다.

 

 

 

---

 마치며..

Vector는 정말 사용하기 편합니다. 동적으로 할당할 수 있다는 점이 참 매력적입니다.

그래프 관련 문제를 풀 때 인접 행렬로 나타낼걸 Vector를 사용해서 인접 리스트의 형태로 나타낼 수 있습니다. 그리고 sort함수를 사용해서 정렬하는 데에도 정말 편합니다.

다음에 정렬 방법 등을 소개하는 글을 올리도록 하겠습니다.

 

 

지적, 댓글 환영입니다. :)