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++' 카테고리의 다른 글
list vs vector (0) | 2022.06.06 |
---|---|
list, forward_list (0) | 2022.06.03 |
vector 와 array c++ (0) | 2022.06.02 |
Call by value Call by reference Call by address 정리c++ (0) | 2022.05.22 |
STL컨테이너 란 C++ (0) | 2022.05.21 |
댓글