[C++/STL] - Vector

1. Vector란

STL의 Vector는 배열과 유사한 데이터 구조체로, 메모리에 연속적으로 저장되는 동적 배열이다.

2. 특징

• Vector의 크기는 동적으로 조정이 가능하다.
• Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 요소에 바로 접근할 수 있다.
• Vector의 요소들은 메모리에 연속적으로 저장되며, 일반 배열과 같이 cache hit rate가 높아 빠른 속도로 접근이 가능하다.
• Vector는 STL에서 제공하는 다양한 함수를 사용할 수 있다.

3. 장단점

장점 :

• Vector의 크기는 동적으로 조정이 가능하다.
• Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 요소에 바로 접근할 수 있다.
• Vector의 요소들은 메모리에 연속적으로 저장되며, 일반 배열과 같이 cache hit rate가 높아 빠른 속도로 접근이 가능하다.
• Vector는 STL에서 제공하는 다양한 함수를 사용할 수 있다.
• Vector는 다차원 배열도 생성할 수 있다.

단점 :

• Vector는 크기를 동적으로 조정하기 때문에, 크기가 변경될 때마다 Vector의 요소들이 메모리에서 재배치될 가능성이 있다. 이에 따라, 크기변경이 빈번하게 일어날 경우 성능 저하가 발생할 수 있다.
• Vector는 포인터를 사용하는 구조체와는 호환성이 떨어질 수 있다. Vector는 요소들을 메모리에 연속적으로 저장하기 때문에, 포인터를 사용하는 구조체와 호환성이 떨어질 수 있다.
• Vector는 요소들을 연속된 메모리 공간으로 복사하는 것이 가능하지만, Vector의 요소들이 메모리에 연속적으로 저장되지 않을 경우 복사가 불가능하다.
• Vector는 요소들을 추가하거나 제거할 때마다 메모리를 재할당하기 때문에, 메모리 사용량이 불필요하게 증가할 수 있다.

4. 시간복잡도

1. 접근 - O(1)
   Vector의 임의 원소 접근 시간복잡도는 O(1)이다. Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 요소에 바로 접근할 수 있으며, Vector의 요소들은 메모리에 연속적으로 저장되어 있기 때문에 포인터 연산을 통해 바로 접근이 가능하다.
2. 검색 - O(n)
   Vector에서 검색의 시간복잡도는 O(n)이다. Vector는 요소들이 메모리에 연속적으로 저장되어 있기 때문에, 특정 요소를 검색하기 위해서는 요소들을 모두 순회해야 한다.
3. 삽입 및 삭제 - O(1), O(n)

• push_back(): Vector의 끝에 새로운 요소를 추가하는 경우, 시간복잡도는 O(1)이다. Vector의 끝에 요소를 추가할 때는 이미 메모리가 할당되어 있기 때문에, 추가적인 메모리 할당이 필요하지 않다.
• pop_back(): Vector의 끝에서 요소를 제거하는 경우, 시간복잡도는 O(1)이다. Vector의 끝에서 요소를 제거할 때는 메모리의 일부분만 해제하면 되기 때문에, 시간복잡도가 낮다.
• insert(): Vector의 특정 위치에 요소를 삽입하는 경우, 시간복잡도는 O(n)이다. Vector의 특정 위치에 요소를 삽입할 때는, 삽입 위치 이후의 요소들을 모두 이동시켜야 하기 때문에 시간복잡도가 높다.
• erase(): Vector에서 특정 위치 또는 범위에 있는 요소를 제거하는 경우, 시간복잡도는 O(n)이다. Vector에서 특정 위치 또는 범위에 있는 요소를 제거할 때는, 제거된 요소 이후의 요소들을 모두 이동시켜야 하기 때문에 시간복잡도가 높다.

5. 사용법

1) 초기화

vector<int> v; // 기본 생성자를 사용하여 초기화하기 
vector<int> v(5); // 크기를 지정하고 기본값으로 초기화하기
vector<int> v(5, 3); // 크기를 지정하고 특정 값으로 초기화하기
vector<int> v1 = {1, 2, 3}; vector<int> v2(v1); // 다른 Vector를 사용하여 초기화하기
vector<int> v; for (int i : {1, 2, 3}) { v.push_back(i); } // 범위 기반 for문을 사용하여 초기화하기
int arr[] = {1, 2, 3}; vector<int> v(arr, arr + sizeof(arr) / sizeof(int)); // 배열을 사용하여 초기화하기
vector<int> v {1, 2, 3}; // 초기화 리스트를 사용하여 초기화하기
vector<int> v(5); // 생성자 함수를 사용하여 초기화하기
vector<int> v; v.emplace_back(1); v.emplace_back(2); v.emplace_back(3); // emplace_back() 함수를 사용하여 초기화하기

2) 멤버 함수

Iterators
begin() : 첫 번째 원소를 가리키는 반복자를 리턴한다.
cbegin() : 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
end() : 마지막 원소를 가리키는 반복자를 리턴한다.
cend() : 마지막 원소를 가리키는 상수 반복자를 리턴한다.
rbegin() : 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
crbegin() : 역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
rend() : 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
crend() : 역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.
Element Access
at(n) : n번째 원소를 참조할 때 사용하며 범위 점검을 하므로 []보다 느리다.
operator[n] : n번째 원소를 참조할 때 사용하며 범위 점검을 안하므로 at보다 빠르다.
front() : 첫 번째 원소의 참조를 리턴한다.
back() : 마지막 원소의 참조를 리턴한다.
Capacity
empty() : 원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.
size() : 원소의 개수를 리턴한다.
max_size() : 담을 수 있는 원소의 최대 개수를 리턴한다.
resize(size, value) : vector의 크기를 변경하고 default 값이나 임의 값으로 초기화한다.
capacity() : vector에 할당된 메모리의 크기를 리턴한다.
reserve(size) : 지정한 크기 만큼의 메모리를 미리 할당한다. size가 capacity보다 클 경우만 동작
shrink_to_fit() : 사용되지 않는 capacity size를 제거한다. 즉 size() == capacity()가 된다.
Modifiers
clear() : vector의 모든 원소를 제거한다.
assign() : 기존 원소들은 모두 제거 후, 임의 값으로 n개의 원소를 할당한다.
assign(InputIterator first, InputIterator last) : first부터 last까지
assign(size_type n, const T& u) : n의 크기만큼 u로 꽉채움
insert() : 임의 위치에 임의 값을 삽입한다.
insert(iterator position, const T& x) : position에 x넣음
insert(iterator position, size_type n, const T& x) : position부터 n의 크기만큼 x를넣음
insert(iterator position, InputIterator first, InputIterator last) : position에 first부터 last까지 넣음
emplace() : 원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.
erase() : 임의 위치의 원소나 지정 범위의 원소를 삭제한다.
erase(iterator pos) : pos위치의 원소 제거
erase(iterator first, iterator last) : first부터 last까지 제거
push_back() : vector의 끝에 원소를 추가한다.
★emplace_back() : 원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 끝에 원소를 추가한다.
std::vector의 멤버 함수인 emplace_back은 C++11부터 추가된 멤버 함수로써 push_back과 같이 vector의 요소 끝에 원소를 추가하는 함수이다. 두 함수의 가장 큰 차이점은, push_back과 같은 삽입 함수들은 삽입할 객체를 받지만 emplace_back과 같은 생성 삽입 함수는 삽입할 객체의 생성자를 위한 인자들을 받아 std::vector 내에서 직접 객체를 생성하여 삽입하므로 임시 객체의 생성과 파괴, 복사(혹은 move)를 하지 않아도 되어 성능상 더 유리하다는 것이다.
pop_back() : vector의 마지막 원소를 제거한다.
swap() : v1.swap( v2 )일때 v1과 v2를 swap한다.