[C++] list 를 쓸까?

std::list 는 double linked list 로 구현이 되어 있다

std::vector 은 array

 

array 의 경우는 탐색, 삽입, 삭제가 모두 O(n) 이고

linked list 는 탐색은 O(n) 이지만 삽입 삭제가 O(1) 이다.

 

그러면 링크드리스트 쓰는게 훨씬 효율적인 것 아닌가?

 

탐색의 경우는 같은 O(n) 일지라도, 캐싱 때문에 vector 가 훨씬 낫다.

벡터는 바로 뒤에 데이터들이 연결되어 있기 떄문에 캐싱이 되어 있어 빠르게 접근이 가능하다.

하지만 list 는 연속적인 공간 안에 존재하는 것이 아니라 힙에 띄엄띄엄 저장되어 있어 캐시라인에서 가져올 수 없다.

 

list 가 삽입과 삭제에서 O(1) 이라는 압도적인 시간복잡도를 보여주긴 한다.

하지만 vector 에서도 O(1) 을 가지게 할 수 있다. push/emplace_back() 으로 넣어서 O(1) 을 받고,

delete 역시 move() 를 써서 해당 위치의 값을 없애는 효과를 보여줄 수 있다

이럴 경우 물론 안의 순서를 보장받지는 않지만, iterator 를 통해서 컨테이너들을 돌아봐야하는 상황에서는

순서가 크게 의미가 없는 경우가 많다.

 

하지만 이는 실무적인 측면에서의 접근이기에, 알고리즘 등과 같이 정확한 자료구조를 선택할 때에는 충분한 고려가 필요할 것 같다.