[C++] vector

1. vector 컨테이너

자동으로 메모리가 할당되는 배열이다.

연속적인 메모리 공간을 미리 할당한다.

원소 삽입 시 메모리 공간이 부족하다면 새 메모리 공간을 할당한 뒤 그곳에 기존 원소들을 복사한 다음 새 원소를 삽입한다.

size: 실제 원소들이 있는 공간. resize 함수로 변경할 수 있다.

capability: 벡터가 차지하고 있는 공간. reserve 함수로 변경할 수 있다.

 

2. 값 삭제

erase: 값 삭제

remove: 위치 변경

두 가지를 주로 같이 사용한다.

remove를 사용하여 해당 조건에 부합하는 원소들을 벡터의 뒤에 넣은 후, 뒤로 밀린 원소들의 시작범위를 넘겨준다. 

vector<> v;
//...
v.erase(remove(범위 시작, 범위 끝, 지우고 싶은 원소), v.end());
v.erase(remove_if(범위 시작, 범위 끝, 지우는 조건), v.end());

 

3. vector<bool>

실제 bool을 담는 것이 아니다. 프록시 패턴(어떤 객체가 하는 일을 그대로 흉내내는 객체. e.g. 스마트포인터)을 통해 bool을 담고 있는 것처럼 동작하게 한다.

실제로는 vector<bool>이 유일하게 원소 한 자리에 8비트의 비트필드를 두고 있다.

실제로 bool이 담긴 자료구조는 std::bitset, deque<bool>등이 있다.

 

4. vector vs deque

vector는 메모리가 연속적이다.

deque는 메모리가 불연속적이기 때문에 capacity와 reserve가 없다. 포인터 간 연산도 불가능하다.

 

5. vector vs list

vector는 메모리가 연속적이다. 랜덤 접근이 가능하고 중간 요소를 제거, 추가하는 데 O(n) 시간복잡도를 가진다.

llist는 메모리가 불연속적이다. 랜덤 접근이 불가능하고 이중 연결 리스트로 구현되어있다. 위치 상관없이 추가, 제거하는 데 상수 시간이 걸린다.

 

참고자료

https://invrtd-h.tistory.com/46

https://github.com/Romanticism-GameDeveloper/GameDeveloper-Client-Interview/blob/main/C%2B%2B/vector%EC%99%80%20%EA%B4%80%EB%A0%A8%ED%95%9C%20%EC%9D%B4%EC%95%BC%EA%B8%B0%EB%93%A4.md