[C++][STL Container] 시퀀스 컨테이너 #1. 벡터(vector)

시퀀스 컨테이너란?

• 시퀀스 컨테이너(Sequence Container)는 C++에서 제공하는 STL 컨테이너 종류(시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어뎁터) 중 하나로, 원소들을 순차적으로 저장하는 컨테이너이다.

 

시퀀스 컨테이너의 종류

• 벡터(vector) - [현재 글]
• 리스트(list, forward_list)
• 데크(deque)
• 배열(array)

---

벡터(vector)란?

벡터 구조

• 벡터는 C++ 스타일의 동적 할당하는 가변 길이 배열이다.
• 임의의 위치에 대한 데이터 접근이 빠르다. (시간복잡도 O(1))
• “맨 끝”에 원소를 삽입 / 삭제하는 작업이 빠르다. (시간복잡도 amortized O(1))
• “임의의 위치”에 원소를 삽입 / 삭제하는 작업이 상대적으로 느리다. (시간복잡도 O(N))
  • 삽입 / 삭제 시 해당 원소 뒤에 있는 원소들을 한 칸씩 이동

---

벡터 멤버 함수

 

원소 접근 관련(Element access)

at()	i번째 원소에 접근 (범위 검사 O)
operator []	i번째 원소에 접근 (범위 검사 X)
front()	첫번째 원소에 접근
back()	마지막 원소에 접근
data()	vector의 시작 주소를 반환 ( &v[0]과 동일 )

 

 

수정 관련(Modifiers)

push_back()	맨 끝에 원소 삽입
pop_back()	맨 끝에 원소 삭제
insert()	지정한 위치에 원소 삽입
erase()	지정한 위치에 원소 삭제
clear()	vector를 비운다.
resize()	vector의 크기(size)를 재조정한다.
emplace()	지정한 위치에 원소 삽입 (insert와 유사. 사용 추천 X)
emplace_back()	맨 끝에 원소 삽입 (push_back과 유사. 사용 추천 X)
swap()	지정한 vector와 swap한다.

 

 

크기 관련(Capacity)

empty()	vector의 size가 0인지 확인한다.(bool 타입 반환)
size()	vector의 크기(원소의 개수) 반환
max_size()	가능한 최대 size 반환
reserve()	capacity를 지정. 메모리 공간을 미리 할당(예약)한다.
capacity()	vector가 할당한 실제 메모리 크기 반환(capacity ≥ size)
shrink_to_fit()	capacity와 size를 같게 만든다. (메모리 절약 효과. 거의 안 쓴다)

 

 

더 자세한 내용은 아래 링크 참조

https://en.cppreference.com/w/cpp/container/vector

std::vector - cppreference.com

 

---

알아두어야 할 점

capacity 초과 시 발생하는 복사 비용

capacity 초과 시 발생하는 복사 과정

• vector는 실제 메모리에서 연속적인 메모리(contiginous memory) 블록을 가지므로, 여러 가지 이유(메모리 단편화, 다른 메모리 영역 침범 등)로 인해 같은 메모리 블록에서 크기를 계속해서 늘릴 수 없다.
• 그래서 vector는 원소 개수(size)가 미리 할당해 둔 메모리 크기(capacity)를 초과할 때마다 1) 큰 메모리 공간을 새롭게 할당하고, 2) 기존 원소를 복사해온다음, 3) 기존 메모리를 해제하는 방식으로 동작한다.
  • 컴파일러마다 다르지만 새로운 메모리 공간으로 이사 갈 때마다 capacity 크기를 2배로 늘린다.
• 이사를 갈 때 발생하는 복사 작업은 n개의 원소를 모두 복사하는 방식이므로 O(N)의 시간복잡도를 가진다.
• 따라서, 대부분의 경우 맨 끝에 원소 삽입시(push_back) O(1)의 시간복잡도를 가지지만, 매우 드물게 복사 작업이 발생하면 O(N)의 시간복잡도를 가진다. 이러한 push_back은 amortized O(1)의 시간복잡도를 가진다.

armortized란?
armortized는 분할상환이라는 뜻으로, 최악의 경우가 가끔 발생해도 전체적인 평균 비용이 낮은 경우를 말한다.
따라서 amortized O(1)은 가끔 성능이 크게 떨어지지만 전체적인 평균 시간복잡도가 O(1)이라는 의미가 된다.

• 이러한 복사 비용이 발생하는 것을 피하기 위해 reserve()를 사용해 메모리를 미리 넉넉하게 할당해두기도 한다.

 

capacity와 관련된 기타 내용

• clear()를 사용해도 capacity는 줄어들지 않는다.
  • 메모리 해제 비용이 크기 때문에 사용해던 메모리를 해제하지 않고 그냥 내버려 둔다.
  • 그래서 만약 clear 이후에 index를 통해 vector 범위를 벗어난 메모리에 접근한다면, 지워지지 않은 이전 값이 그대로 남아있을 수 있다. (이러한 접근에 대한 결과는 Undefined Behavior이므로 하지 않는 것이 좋다.)
• resize()를 통해 size를 재조정하면 이에 맞춰 capacity도 자동으로 늘어난다.
  • 만약 resize 이후에 push_back을 하면 조정된 size뒤에 원소가 추가된다.

vector<int> v1;
v1.resize(5); // [0][0][0][0][0]
v1.push_back(25); // [0][0][0][0][0][25]

 

 

emplace, emplace_back 사용을 추천하지 않는 이유

• emplace, emplace_back 함수는 생성자를 직접 호출함으로써 완벽한 전달(perfect forwarding)을 한다.
• 이러한 완벽한 전달은 "임시 객체를 먼저 만든 다음, 복사나 이동을 통해 데이터를 저장하는 과정을 생략"하여 원소 삽입의 성능을 높인다는 장점이 있다.
• 하지만 emplace, emplace_back은 어떤 생성자가 호출되었는지 명확하지 않기 때문에 프로그래머가 실수할 여지가 있다는 문제점이 있다.

vector<vector<int>> v1;
// v1.push_back(20000); // 오류 : 20000은 vector<int>로 변환 할 수 없음.

v1.emplace_back(20000); // 암묵적으로 20000 -> vector<int>(20000)으로 변환.
cout << v1[0].size() << '\n'; // 출력 결과: 20000

• 위 예시처럼, v1에 20000의 값을 가진 원소가 삽입될 것이라고 프로그래머가 착각했을 때,  push_back(20000)은 오류를 발생시켜 실수를 바로잡아주지만, emplace_back() 같은 경우 예상한 것과 다르게 20000의 크기를 가진 벡터가 추가되며 통과되는 모습을 보인다. 이처럼 emplace_back을 사용한다면 예상치 못한 생성자의 호출에 의해 의도와 다른 코드가 통과되는 문제가 발생한다. 
• 게다가 요즘의 컴파일러는 최적화가 잘 되어 있어 거의 대부분의 push_back이 emplace_back과 동일한 코드로 생성되기 때문에 프로그래머가 emplace_back을 사용해서 얻는 성능적 이점도 크게 없다.
• 요약하자면, 1) 실수할 여지가 있고, 2) 컴파일러 최적화로 인해 성능적 이점이 크게 없기 때문에 emplace_back 말고 그냥 push_back을 사용하는 것이 낫다. (emplace도 동일)

---

참고 자료

https://modoocode.com/314

https://modoocode.com/223

https://modoocode.com/326

https://en.cppreference.com/w/cpp/container/vector

https://blockdmask.tistory.com/70

https://hwan-shell.tistory.com/119