[C++] STL - std::list와 std::vector

std::list

정의

C++ STL의 list는 이중 연결 리스트(double linked list)를 기반으로 구현된 컨테이너입니다.

이중 연결 리스트는각 노드가 앞선 노드(prev)와 다음 노드(next)에 대한 참조 또는 포인터를 가지고 있는 데이터구조입니다.

 

특징

list는 어느 위치에서든 O(1)의 시간복잡도로 요소를 삽입하거나 삭제할수 있습니다. 그러나 이러한 장점을 가지기 위해, list는 추가적인 메모리(앞 뒤 원소의 연결 정보)를 사용하고, 배열처럼 연속된 메모리 공간을 사용하지 않기 때문에 '캐시 지역성'이 떨어져 속도가 상대적으로 느립니다. 

 

> 캐시 지역성 (Cache Locality)

캐시 지역성(cache locality)은 프로그램의 메모리 접근 패턴이 얼마나 효율적으로 CPU 캐시를 활용하는지에 대한 개념입니다. 이는 데이터가 메모리에 연속적으로 배치될 때 가장 잘 작동합니다.

일반적으로 컴퓨터 시스템에서, CPU 캐시는 주기억장치(예: RAM)보다 훨씬 빠른 속도로 데이터를 제공할 수 있습니다. 따라서, 한 번 캐시된 데이터에 다시 접근하면, 그 접근은 "캐시 히트(cache hit)"라고 하며, 이는 메모리에서 직접 데이터를 가져오는 것보다 빠릅니다.

그런데 std::list와 같은 연결 리스트 구조체는 메모리 내의 여러 위치에 분산되어 저장됩니다. 이 말은 각 요소가 서로 인접해 있지 않을 수 있다는 의미입니다.
따라서 연결 리스트를 순회할 때마다 CPU는 새로운 위치로 "점프"해야 하며, 이것이 캐시 미스(cache miss)를 유발할 가능성이 높습니다.

반면 std::vector와 같은 배열 기반 컨테이너들은 모든 요소가 메모리에서 연속적인 공간을 차지합니다. 따라서 한 번의 메모리 접근이 인접한 여러 요소들을 캐싱할 수 있으므로 순차적인 접근 시에 높은 캐시 히트율을 가질 수 있습니다.

 

언제 사용하면 좋을까요?

list는 중간 위치에서 자주 발생하는 삽입/삭제가 존재할 때 유용하게 사용될 수 있습니다. std::vector나 std::array 같은 배열 기반 컨테이너는 중간 위치에서의 삽입/삭제가 O(n)의 시간복잡도가 들지만, std::list는 O(1)이라는 상수 시간으로 처리할 수 있습니다.

또한, 동적 배열과 달리 list의 크기 변경에는 추가적인 비용이 없기 때문에 크기 변경이 자주 일어나는 경우에도 유용하게 사용될 수 있습니다.

 

그러나, list는 vector나 array처럼 원소에 [0] 인덱스를 사용한 직접적인 접근이 불가능합니다. list가 원소에 접근할 때는 반복자(iterator)를 통한 접근만 가능합니다.

list에 삽입하고자 하는 원소의 위치를 모른다면, 반복자를 사용하여 선형탐색을 통해 삽입할 위치를 찾아야 합니다. ++, -- 같은 증감연산자를 통해 반복자를 움직이거나 std::advance(it, 2) 의 함수를 통해 이동시킬 수 있습니다.  

 

> *iterator

반복자 iterator를 통해 각 원소에 접근하기 위해선 역참조 연산(*)을 사용합니다.
*iterator로 사용하면, 현재 iterator가 가리키고 있는 원소에 대한 참조로써, 해당 원소에 접근할 수 있습니다.

 

std::vector

정의

C++ STL의 vector는 동적 배열을 구현한 컨테이너입니다. 메모리에서 연속된 공간을 차지하는 요소들의 집합으로, 배열의 크기를 런타임에 변경할 수 있습니다.

 

특징

vector는 내부적으로 원시 배열(raw array)를 관리합니다. 새로운 요소가 추가되고 현재 할당된 메모리를 초과하면, 일반적으로 현재 크기의 2배인 새로운 메모리 공간을 "할당"하고 기존 요소들을 새로운 공간으로 "복사"한 후, 기존 메모리를 "해제"합니다. 이를 통해 잦은 메모리 재할당과 복사를 피하여 성능을 향상시킬 수 있습니다.

 

그러나, 이처럼 벡터가 자동으로 resizing 될 때 비용이 발생하기 때문에, 가능한 경우벡터가 필요로 할 최대 크기를 알고 있다면 reserve() 함수를 통해 사전에 충분한 공간을 할당하는 것이 좋습니다.

 

언제 사용하면 좋을까요?

vector는 요소의 개수가 동적으로 변경될 수 있는 경우나, 중간 위치에 삽입/삭제보다, 맨 끝에서의 삽입/삭제가 자주 발생하는 경우, 인덱스를 통해 원소에 임의로 접근이 필요한 경우 유용하게 사용될 수 있습니다.

 

reserve와 resize의 차이

reserve(size_type n) 함수는 벡터의 용량(capacity)를 적어도 'n'으로 만듭니다.

reserve 함수는 현재 용량이 n보다 작은 경우에만 메모리 재할당이 발생합니다. 즉, 최소한 n개의 요소를 저장할 수 있는 충분한 공간을 보장하는 함수입니다. 그러나 용량(capacity)에만 적용될 뿐 실제 크기(size)는 변경되지 않습니다.

 

반면, resize( size_type n , number=0) 함수는 n만큼의 용량(capacity)을 미리 확보하고, n의 크기가 현재 벡터의 크기보다 큰 경우, 나머지 공간을 두번째 매개변수의 값으로 채웁니다.

 

즉, 두 함수의 차이는 용량을 확보한 후 그 공간을 초기화 하느냐 하지 않느냐의 차이입니다.  

 

size != capacity

vector에서 size() 함수는 vector가 사용하고 있는 공간을 반환해줍니다. 즉, size는 현재 벡터가 실제로 갖고 있는 요소들의 수 입니다.

 

반면, capacity() 함수는 vector가 사용하기 위해 확보해놓은 메모리 용량을 반환해줍니다. 즉, capacity는 현재 할당된 메모리 공간에 저장할 수 있는 최대 요소 수입니다. 

 

위 예제를 통해 vector의 변화를 살펴보면,  reserve 함수를 통해 vector의 용량을 100으로 확보하면, v.capacity() 의 결과는 100이 나오지만, v.size()는 0이 나옵니다.

그 후, resize(50)을 호출하면 size는 50이 나오고 50개의 원소가 0 값으로 초기화됩니다. 이때도 capacity는 100으로 확보되어 있습니다.

 

push_back과 emplace_back의 차이

vector의 push_back 함수는 '객체'를 집어넣는 형식으로, 객체가 없이 삽입을 하려면 임시객체(rvalue)를 만들어 복사하거나 이동하여 벡터의 끝에 추가합니다.

 

즉, 인자로 받은 객체를 복사(또는 이동)하여 저장 공간에 넣습니다. 따라서 인자로 전달되는 객체의 자료형은 벡터가 저장하는 자료형과 일치해야 합니다.

 

emplace_back 함수는 C++11에서 도입된 함수로, 가변인자 템플릿을 사용하여 객체 생성에 필요한 인자만 받은 후, 함수 내에서 객체를 생성해 삽입하는 방식입니다.

임시 객체를 만들 필요가 없기 때문에, emplace_back 내부에서 삽입에 필요한 생성자를 한번만 호출합니다.

 

위와 같은 소스코드를 실행시키면, push_back을 호출했을 때의 실행 결과는 아래와 같습니다.

push_back 호출
일반 생성자 호출
이동 생성자 호출
소멸자 호출
소멸자 호출

 

push_back 함수는 호출되는 순간, Item(3) 을 통해 임시 객체를 하나 만듭니다. 이때 일반 생성자가 호출됩니다.

이후, 임시 객체의 이동생성자를 통해 push_back 함수 내부에서 임시 객체를 또 만들어냅니다. 이때 이동 생성자가 호출됩니다.

vector 객체에 삽입한 뒤, push_back에서 빠져나온 후 Item(3)을 통해 만들어진 임시 객체를 소멸합니다. 이때 소멸자가 호출됩니다.

main 함수가 끝난 후 vector에 삽입된 객체가 소멸되면서 두번째 소멸자가 호출됩니다.

 

emplace_back을 호출했을 때의 실행 결과는 아래와 같습니다.

emplace_back 호출
일반 생성자 호출
소멸자 호출

 

emplace_back 함수가 호출되며, Item 객체를 만들 수 있는 인자 (3)이 전달됩니다.

이때, emplace_back 함수 내부에서 객체를 만들어내고, 이때 일반 생성자가 호출됩니다.

vector에 삽입이 끝난 후, main함수가 종료되면 vector에 삽입된 객체가 소멸되며 소멸자가 호출됩니다.

---

여기서 중요한 점은 emplace_back()이 임시 객체의 생성 및 파괴 없이 원하는 타입의 객체를 직접 구성할 수 있다는 것입니다. 따라서 비용이 큰 복사 연산 대신 필요한 위치에서 바로 원소를 구성할 수 있어 성능 향상을 가져올 수 있습니다.

 

그러나 실제 성능 차이는 대상 타입(복사 비용 vs 직접 구성 비용), 컴파일러 최적화 수준 등 여러 요인에 따라 다르므로 항상 프로파일링하여 확인해야 합니다.

 

또한 중요한 점 하나는, 'emplace' 계열 함수들은 기대하지 않은 형변환이 발생할 수 있다는 점입니다. emplace_back 함수를 호출하며 매개변수를 전달할 때, 예기치 않게 다른 오버로드된 생성자가 호출되거나 암시적 형 변환을 유발할 수 있다는 단점이 존재합니다. 이런 경우엔 컴파일할 땐 에러가 발생하지 않고, 프로그램이 실행되는 도중에 정의되지 않는 동작이 발생하게 됩니다.

---

https://openmynotepad.tistory.com/10

emplace_back 과 push_back 의 차이