[C++] vector와 list

vector는 array 기반, list는 Linked List 기반으로 value를 저장하는 자료구조입니다.

---

vector

 

• vector는 array이므로, 연속적인 메모리 공간에 할당합니다.
• capacity와 size를 기준으로 스스로 확장, 축소하는 Dynamic Array입니다.
• iterator 및 index로 접근이 가능하고, array 기반이므로 list에 비해 임의 접근 속도가 O(1)입니다.
• 삽입, 삭제 또한 O(1)이나, 컨테이너 끝이 아닌 경우 모든 요소를 밀고 삽입해야 하므로 O(N)의 시간 복잡도를 갖습니다.

---

list

• list는 Linked List를 기반으로 하기 때문에, 연속된 공간이 아닌 요소가 다음 요소를 가리키는 포인터를 가지는 방식으로 구현되어 있습니다.
• 이로 인해 index 접근은 불가하며, 임의 접근이 O(N)의 시간 복잡도를 가집니다.
• 하지만 삽입, 삭제 시 포인터 간 관계를 끊고 재연결하므로, O(1)의 시간 복잡도를 가집니다.

---

단순하게도 search가 잦은 경우 vector, insert / delete가 잦은 경우 list를 사용합니다.

하지만 vector를 사용하는 데엔 약간의 주의가 필요합니다.

잠시 언급했지만, vector는 Dynamic Array를 구현하기 위해 내부적으로 capacity과 size 개념을 사용합니다.

우선 capacity만큼 공간을 할당하고, 사용자에게 길이가 무한인 배열처럼 제공합니다.
사용자가 사용 중인 크기인 size가 capacity에 거의 도달하면,
capacity를 증가시킨 후 새 배열을 할당하고, 내용을 복사해넣습니다. (기존 배열은 해제합니다.)

이렇게 vector는

1. capacity와 size의 차이로 인한 불필요한 공간 낭비
2. 배열 해제, 복사, 할당에 따른 오버헤드가 개발자의 의도와는 상관없이 발생

할 수 있으므로, 주의해서 사용해야 합니다.

(2)오버헤드를 감수하여 (1)불필요한 공간 낭비를 해소하기 위한 vector의 함수를 소개합니다.

• vector::shrink_to_fit (

void shrink_to_fit() // reduce capacity 
{ 
	if (size() < capacity()) // worth shrinking, do it 
	{ 
   		_Myt _Tmp(*this); swap(_Tmp); 
	} 
} 

// capacity를 size만큼 줄인 배열을 생성하고, swap하여 옮겨넣습니다.

https://www.cplusplus.com/reference/vector/vector/shrink_to_fit/

vector::shrink_to_fit - C++ Reference