[Vector / Array] std::vector

 

 

벡터(Vector)의 시간 복잡도와 emplace_back

이번 시간에는 벡터(Vector)의 시간 복잡도(Time Complexity)와 emplace_back의 동작 방식에 대해 알아보겠습니다.

1. 벡터의 시간 복잡도

C++ 레퍼런스에서는 벡터의 주요 연산에 대해 다음과 같이 설명합니다.

• 임의 접근(Random Access) : O(1)
• 맨 뒤에 삽입/삭제 (push_back, emplace_back, pop_back) : 평균 O(1)
• 중간 삽입/삭제 (insert, erase) : O(N)

 

 

2. 랜덤 액세스가 O(1)인 이유

벡터는 연속된 메모리 공간에 데이터를 저장합니다.

• 벡터는 첫 번째 원소의 주소를 알고 있습니다.
• 원하는 원소의 인덱스만 알면 주소를 바로 계산할 수 있습니다.
• 따라서 첫 번째 원소든, 마지막 원소든, 중간 원소든 접근 시간이 거의 동일합니다.

이 때문에 벡터의 임의 접근은 O(1) 입니다.

---

3. 맨 뒤 삽입과 삭제가 O(1)인 이유

push_back, emplace_back, pop_back은 모두 벡터의 마지막 위치에서만 작업을 수행합니다.

• 마지막에 원소를 하나 추가하거나
• 마지막 원소를 제거하기만 하면 되므로

기존 데이터를 이동할 필요가 없어 평균 O(1)의 시간 복잡도를 가집니다.

---

4. 중간 삽입과 삭제는 O(N)

반면 insert()나 erase()를 이용하여 벡터 중간에 데이터를 추가하거나 삭제하면 문제가 달라집니다.

예를 들어 맨 앞에 원소를 삽입하면

• 기존 모든 원소를 한 칸씩 뒤로 이동해야 합니다.

또한 맨 앞 원소를 삭제하면

• 나머지 모든 원소를 한 칸씩 앞으로 이동해야 합니다.

즉, 데이터 이동이 원소 개수만큼 발생하므로 O(N)의 시간이 필요합니다.

따라서 벡터에서는 중간 삽입과 삭제를 자주 수행하는 것은 성능상 좋지 않으며, 정말 필요한지 한 번 더 고려하는 것이 좋습니다.

---

push_back과 emplace_back

벡터의 끝에 원소를 추가할 때는 push_back()보다 emplace_back()을 사용하는 것이 일반적으로 권장됩니다.

push_back

객체를 먼저 생성한 뒤 벡터에 넣습니다.

cats.push_back(Cat("Kitty", 2));

이 과정에서는

1. 임시 객체 생성
2. 벡터 내부로 이동(move) 또는 복사(copy)

가 발생합니다.

---

emplace_back

객체를 만들지 않고 생성자 인자를 직접 전달합니다.

cats.emplace_back("Kitty", 2);

이 경우

• 벡터 내부에서 객체가 직접 생성(in-place construction) 되므로
• 불필요한 임시 객체와 Move 연산을 줄일 수 있습니다.

즉, 더 효율적인 객체 생성이 가능합니다.

---

C++17 이후의 변화

C++17부터는 emplace_back()이 생성된 객체의 참조(reference) 를 반환합니다.

Cat& cat = cats.emplace_back("Kitty", 2);

이처럼 방금 생성된 객체를 바로 사용할 수 있습니다.

---

lvalue와 rvalue

이미 만들어진 객체를 전달하는 경우에는

Cat cat("Kitty", 2);
cats.emplace_back(cat);

• lvalue는 복사(copy) 됩니다.

반면

cats.emplace_back(std::move(cat));

• rvalue는 이동(move) 됩니다.

이는 emplace_back뿐 아니라 C++의 일반적인 복사/이동 규칙과 동일합니다.

---

정리

• 벡터는 연속된 메모리를 사용하는 컨테이너입니다.
• 랜덤 액세스는 주소 계산만으로 가능하므로 O(1)입니다.
• 맨 뒤 삽입/삭제는 데이터 이동이 없어 평균 O(1)입니다.
• 중간 삽입/삭제는 기존 원소들을 이동해야 하므로 O(N)입니다.
• 객체를 벡터 끝에 추가할 때는 emplace_back()을 사용하는 것이 일반적으로 더 효율적입니다.
• C++17부터는 emplace_back()이 생성된 객체의 참조를 반환하여 더욱 편리하게 사용할 수 있습니다.