[C++] 2D vector push_back의 시간복잡도(time complexity)에 대하여

C++ STL에서 사용할 수 있는 vector는 Java의 ArrayList와 아주 유사합니다.

동적으로 크기가 변하는 배열?이라고 보면 될 것 같습니다.

 

List<Integer> myList = new ArrayList<>();

vector<int> myVector;

초기화에는 여러 방법이 있지만 대표적으로 위와 같은 방법으로 List와 vector를 초기화할 수 있습니다.

 

2차원 구조를 할당하기 위해서는 아래와 같이 하면 됩니다.

List<List<Integer>> myList = new ArrayList<>();

vector<vector<int>> myVector;

구조가 상당히 비슷해 보입니다.

 

Java에서는 ArrayList의 멤버?들은 reference로 관리된다고 봐야할 것 같습니다.

myList.add(subList);와 같은 코드를 사용한 후 subList를 수정하면 myList에 들어있던 subList도 변경이 됩니다.

그래서 경우에 따라 이와 같은것을 원하지 않는다면

List<Integer> temp = new ArrayList<>(subList);
myList.add(temp);

위와 같은 방식으로 복사본을 만들어 추가해야 합니다. 이 복사본을 만드는 과정에서 subList의 길이 n만큼 시간이 걸립니다. 시간복잡도로 보면 O(n)이라는 말입니다.

 

동일한 경우 2차원 구조인 myVector에서 push_back()함수를 이용해 subVector를 추가하는 것을 보면

myVector.push_back(subVector);

그냥 위와 같이 사용하면 됩니다. Java에서와 달리 개발자가 복사본을 만드는 과정이 필요없습니다. 왜 그럴까요?

push_back이 수행되면 자동으로 복사본이 들어가기 때문에 그렇습니다. 그래서 2차원 vector인 이 경우에도 push_back은 subVoctor의 길이 n만큼 시간이 걸립니다. 시간복잡도로 보면 O(n)입니다.

 

만약 Java와 같이 동작하기를 희망한다면

vector<vector<int*>> myVector와 같은 방식으로 타입을 변경해야 합니다.

 

Java와 C++를 같이 사용하다보면 헷갈리는 내용이라 정리해봤습니다.

 

참고

stackoverflow.com/questions/2275076/is-stdvector-copying-the-objects-with-a-push-back