c++ std::vector review

[frequent interview question]
Q1) std::vector의 push_back() time complexity는?
Q2) std::vector의 push_front() time complexity는?
Q3) std::vector의 push_back과 emplace_back의 차이는?

std::vector는 heap 메모리 영역의 연속된 공간의 동적 배열을 구현할 수 있는 stl 자료구조이다.

 

stack 자료구조를 사용하고 싶을 때 보통 std::vector로 사용한다.

따라서 이 stack 구조로 사용된다는 점에서 Q1)의 push_back는 big O(n)은 O(1) : 끝에서 하나만 삽입이므로 head ptr만 올리면 됨, push_front는 전체를 한 칸씩 밀어서 써야하므로 O(n)이다.

---

advanced c++ 강의에서 내가 질문한 내용인 emplace_back과 push_back의 차이는 내가 기억하기로는 push_back는 () 안에 객체를 새로 생성하고 전달 후 또 생성하여 삽입하기 때문에 추가적인 생성자/소멸자 사용의 오버헤드가 존재하지만 emplace_back은 reference를 이용해 객체를 전달하고 거기서 생성하기 때문에 추가적인 contructor/destructor의 사용이 줄어들어 수행속도에 이점을 갖는 것으로 알고있다. <- 하지만 강의를 더 듣고 추가해야 할 듯

 

하지만 emplace_back이 참조를 전달한다는 점에서 값의 불변성을 보장할 수 없다는 단점이 존재하고, 최신 컴파일러에서는 두 함수의 동작이 거의 비슷해서 실질적인 수행시간의 차이가 없다는 의견도 있었다.

---

vector는 heap 공간의 연속된 메모리 자료구조라는 점에서, memory fragmentation 문제와 alloc/deallocation 문제를 초래할 수 있다.

heap은 기본적으로 사용하는 구조체를 연속으로 할당해 주는데, 내가 사용하는 vector 구조체를 한 칸 더 늘리고 싶은데(push) 이미 옆에 자리가 차있으면, 그 전체 벡터 구조체를 copy해서 널널한 자리로 이동해야 하므로, 나는 객체 하나를 push 했을 뿐인데, O(1)이 아닌 O(n)의 동작이 일어날 수 있다는 것이다. 

또한 이 벡터가 떠난 자리는 또 재활용되기 어려울 수 있기 때문에, 빈공간 채로 남는, memory fragmentation(external) 문제가 생길 수 있다.

=> 따라서 이런 문제를 해결하기 위해서, vector를 사용할 때는 시작 전에 사용할 크기만큼 vec.reserve(size N) 하는 것이 바람직하다.

 

memory fragmentation 개념이 들어봤는데, 잘 기억나지 않아 다시 찾아보았는데 아래 링크가 정리가 잘 되어있었다. 

- https://jeong-pro.tistory.com/91

메모리 단편화(Memory Fragmentation)가 무엇이고 왜 발생하는가?

 

정리하자면

- memory fragmenation은 메모리 낭비, 비활용성이라고 볼 수 있는데, 크게 internal / external로 나뉘는데,

internal은 실질적으로 사용하는 메모리보다 더 큰 메모리가 할당되어, 사용하지 않는 잉여 메모리가 크게 잡히는 것,

external은 heap에서 해제되고 빈공간이, heap 자체의 연속적으로 객체를 할당하는 법칙에 따라, 재사용되지 못하고 빈공간인 채로 전체 메모리 사용에서 봤을 때, 메모리를 제대로 활용하지 못하는 문제이다.

 

이에 대한 해결책 으로는 

- paging :메모리를 특정 block으로 나누어 table에 사용여부를 업데이트 하여, 빈공간이 생기면 table을 참조해 해당 메모리 공간을 알뜰하게 사용하는 구조. solution for external

- segmentation(메모리 크기를 fixed block size가 아니라 사용하고자 하는 메모리 크기만큼 할당하여 사용하는 구조, sol for internal)

- memory pooling: memory를 처음 시작에 heap에 크게 띄워두고, 사용하고자 하는 양만큼 head ptr을 업데이트하여 사용/해제하는 것, 대신 해제되지 않으면 그자체로 잉여. memory fragmentation으로 인한 낭비보다 pool을 잡아두었는데 실질적으로 사용하지 않은 낭비가 더 크면 사용하지 말아야 함

 

이 중에서 memory pooling은 기존에 쓰던 구조이고, 지금 고민하고 있는 문제에 가장 적용하기 쉬워 보이므로 더 생각해봐야겠다.