vector란 무엇 일까? c++

Vector란 무엇 일까? 

cppreference.com 에 검색을 해보자

 std::vector is a sequence container that encapsulates dynamic size arrays.

vector는 동적 사이즈 배열을 캡슐화하는 연속된 컨테이너입니다.라고 설명하고 있다

 

동적 사이즈 배열이란?

정적 배열처럼 크기가 정해진 배열이 아니라 요소를 추가하거나 제거할 수 있는 임의 액세스 가변 크기 목록 데이터 구조이다.

 

동적인 배열을 사용할 때 vector를 쓰는구나라고 유추할 수 있다.

 

자 그럼 동적 사이즈 배열을 연속되게 사용하는 것을 vector를 사용하지 않고 코드를 작성해 보자

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int* numsPtr = new int[5];
    
	for (int i = 0; i < 5; i++)
	{
		numsPtr[i] = i;
	}
	delete numsPtr;
	
	return 0;
}

그럼 벡터를 사용하면 어떨까?

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> vec{1,2,3,4,5};
	
	return 0;
}

한 눈에 보기에도 훨씬 가독성이 좋아졌다. 그런데 장점은 이뿐 만이 아니다

int* 를 사용해서 만든 동적 배열은 new를 사용하여

Heap에 메모리를 생성하고 그 주소 값을 리턴하는 동작 방식을 가지기에

delete로 메모리 해제를 시켜야지만 메모리 누수가 발생하지 않는다.

 

이러한 작업에서 나올 수 있는 실수를

 

vector는 알아서 처리해 주기 때문에 위 같은 실수가 발생하지 않아 사용에 용의 하다.

 

벡터가 대충 어떻게 동작하는지 숙지 했다면 벡터의 Time Complexity(시간 복잡도를 알아보자)

마찬가지로 cppreference.com 에서 vector의 time complexity를 찾아 본다.

Random access - constant o(1)

Insertion or removal of elements at the end - amortized constant o(1)

Insertion or removal of elements -linear in the distance to the end of the vector  O(n)

 

Random access o(1)

어떤 랜덤한 원소에 접근 할때는 o(1)의 time complexity를 가진다 그 이유는 

vector는 이러한 연속된 배열에 가장 첫 번째 배열을 가리키고 있다.

만약 5번째 배열에 접근하고 싶다면 첫 번째 배열에서 + 4를 통해 접근하는 방식이기에

o(1)의 time complexity를 가진다.

 

Insertion or removal of elements at the end - amortized constant o(1)도 마찬가지이다.

 

배열을 끝 부분을 나타내기에 amortized constant o(1) o(1)의 time complexity를 가진다.

 (amortized constant o(1)는 O(n)인데)

(1/n확률로 O(n) 연산이, 나머지에선 O(1) 연산이 이루어져 평균적으로o(1)time complexity를 가진다는 말이다.)

ex) emplace.back(),pop_back()

Insertion or removal of elements -linear in the distance to the end of the vector  O(n)

마지막 공간이 아닌 다른 곳에 원소를 삽입하거나 지울 때 O(n)의 Time Complexity를 가진다.

그 이유는 첫 번째 공간에 원소를 추가하기 위해서 기존에 있던 원소를

한칸 씩 오른쪽으로 move를 해주어야하기 때문이다.

마찬가지로 erase()를 사용할 때에도 한 칸씩 다시 당겨 와야 하기에 O(n)의 time complexity를 가진다.

 

그런데 Insertion or removal of elements at the end  - amortized constant o(1) 많은 경우에

O(1)의 time complexity를 가지지만 종종 o(n)의 time complexity 지니게 된다.

Capacity 때문이다.

size와 capacity의 크기가 동일함을 확인할 수 있다.

nums에 6이라는 원소를 추가해보자

그러자 size와 capacity의 값이 달라진 것 을 확인할 수 있다

그 이유는 capacity는 확보된 메모리이고  size는 원소의 수를 나타내기 때문이다.

capacity는 원소처럼 하나씩 늘어나지 않고 어느 정도의 공간을 확보하고 그 공간이 다 차면

어느 정도의 공간을 다시 확보한다 이러한 과정이 생기면 emplace_back 또한 o(n)의 time complexity를 지니게 된다.

 

이러한 것을 예방하기 위해 우리는  reserve()를 통해 메모리를 확보하는 것이 좋다.

nums.reserve(1000); 를 하면  1000번째까지의 메모리를 확보하게 된다.

그럼 time complexity를 o(1) 로 유지 할 수 있다.

 

 

 

capacity의 값의 증가는 컴파일러,플랫폼,버전마다 알아서 구연되어 있어 증가 값이 다르다.

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문