벡터 (std::vector)

벡터(vector)는 시퀀스 컨테이너(Sequence Container) 중 하나로 순서를 유지하는 선형 자료구조이다.

vector 는 배열처럼 데이터들을 메모리상에 순서대로 보관한다.

데이터들이 메모리상에 붙어있어 캐시 적중률(Cache Hit Rate) 이 높고 할당이 다소 어렵다.

vector 는 자동으로 메모리가 할당되는 동적 배열로 vector 생성 시 Heap 메모리에 동적으로 할당된다.

vector 는 기본적으로 맨 뒤에서 원소의 삽입/삭제가 가능하며, 중간에서의 원소 삽입/삭제도 가능하지만 크게 효율적이지는 않다.

vector 에 대한 일반적인 연산의 복잡도는 다음과 같다.

• 임의 접근 (Random Access) : O(1)
• 맨 뒤에서 원소 삽입/삭제 : O(1)
• 원소의 삽입/삭제 : O(N)

<aside> 💡 장점

</aside>

• 동적으로 크기를 변경할 수 있다.
• vector 의 맨 뒤에서 원소 삽입/삭제 시 효율적이다.
• 배열기반의 Container 이므로 임의 접근(Random Access)이 가능하다.

<aside> 💡 단점

</aside>

• 배열기반의 Container 이기 때문 중간 원소 삽입/삭제가 자주 수행되면 비효율적이다.

vector 의 사용

• vector 헤더파일

#include <vector>

• vector 의 선언

std::vector<Type> VectorName;

• vector 생성자 (편의상 int)

vector 의 멤버 함수

std::vector<int> v;

vector 의 size 와 capacity

vector 의 size 와 capacity 를 같은 개념으로 받아 들이면 안된다.

• size : 원소의 개수
• capacity : 할당된 공간(메모리)의 크기

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v;

	// vector의 원소를 1개씩 증가시킴
	for (int i = 0; i < 10; i++)
	{
		v.push_back(1);
		std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << std::endl;
	}

	return 0;
}

size = 1, capacity = 1
size = 2, capacity = 2
size = 3, capacity = 3
size = 4, capacity = 4
size = 5, capacity = 6
size = 6, capacity = 6
size = 7, capacity = 9
size = 8, capacity = 9
size = 9, capacity = 9
size = 10, capacity = 13

size 는 원소의 개수가 증가할 때마다 1씩 증가하는 반면, capacity는 size 가 capacity 를 초과할 때마다 약 1.5배씩 증가하였다.

vector 에 capacity 가 있는 이유는 vector 의 메모리를 새로 할당할 때 기존 메모리 영역에 이어서 할당하는 것이 아니라 새로운 메모리 영역에 메모리를 할당한 후 기존 원소들을 전부 복사하기 때문이다.

만약, vector 에 push_back 이 일어날 때마다 동적할당을 하게 된다면, 새로이 메모리 영역을 할당하고, 복사하는 비용이 많이 들어 비효율적일 것이다. 따라서 이 과정을 최대한 피하기 위해 미리 정해준 규칙에 따라 capacity 를 증가시키면서 메모리의 여유분을 확보하는 것이다.

vector 의 원소 삽입/삭제

vector 의 원소 삽입/삭제 과정을 간략히 하면 다음과 같이 진행된다.

이러한 방식으로 원소 삽입/삭제 과정이 일어나는 이유는 vector 는 원소들을 하나의 메모리 블록에 연속적으로 저장하기 때문이다.

따라서 vector 의 중간 부분에서 삽입/삭제 시에는 뒤쪽 원소들을 복사하기 때문에 비효율적이지만 벡터의 맨 뒷 부분에서 삽입/삭제 시에는 원소를 이동시키는 과정이 필요없어 효율적으로 작동한다.

vector 의 임의접근

vector 는 원소를 하나의 메모리 블록에 연속적으로 저장하기 때문에 임의 접근(Random Access) 이 가능하다. 즉, vector 의 n 번째 원소에 접근하기 위해 일일히 처음부터 원소를 세는 것이 아니라 n 번째 원소로 바로 접근할 수 있다.

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v;
	std::vector<int>::iterator it;

	// [1][2][3][4][5] vector 생성
	for (int i = 0; i < 5; i++)
		v.push_back(i + 1);

	std::cout << "원본 벡터" << std::endl;
	for (it = v.begin(); it != v.end(); ++it)
		std::cout << (*it) << " ";

	// 3번째 원소 v[2] 임의 접근
	v[2] = 0;

	// 3번째 원소 출력
	std::cout << "\\n\\n3번째 원소 v[2] = " << v[2] << std::endl;

	std::cout << "\\n임의 접근 후 벡터" << std::endl;
	for (it = v.begin(); it != v.end(); ++it)
		std::cout << (*it) << " ";

	return 0;
}

원본 벡터
1 2 3 4 5

3번째 원소 v[2] = 0

임의 접근 후 벡터
1 2 0 4 5

vector 사용 예시

reserve

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v;

	// capacity 를 미리 동적할당
	v.reserve(5);

	std::cout << "capacity : " << v.capacity() << std::endl;
	std::cout << "size     : " << v.size() << std::endl;

	// 원소 추가
	std::cout << "\\n원소 추가" << std::endl;
	for (int i = 0; i < v.capacity(); i++)
	{
		v.push_back(i);
		std::cout << v[i] << " ";
	}

	// 공간 늘어 날 때
	v.reserve(10);
	std::cout << "\\n\\n공간 늘어 날 때" << std::endl;
	std::cout << "capacity : " << v.capacity() << std::endl;
	std::cout << "size     : " << v.size() << std::endl;
	for (int i = 0; i < v.size(); i++)
	{
		std::cout << v[i] << " ";
	}

	// 공간 줄어 들 때
	v.reserve(2);
	std::cout << "\\n\\n공간 줄어 들 때" << std::endl;
	std::cout << "capacity : " << v.capacity() << std::endl;
	std::cout << "size     : " << v.size() << std::endl;
	for (int i = 0; i < v.size(); i++)
	{
		std::cout << v[i] << " ";
	}

	return 0;
}