List2 list vs vector vector와 list의 timecomplexity다. 이것만 보면 서로 장단 점이 있어 random access 를 할 때는 vector로 구현하고 i/d 를 쓸 때는 list를 쓰면 될 것 같다 하지만 99%가 vector를 쓴다 find 때문이다 TimeComplexity는 같지만 실행해보면 vector의 find가 훨씬 빠르다. 그 이유는 두가지 이유가 있는데 첫번째로 메모리 구조 때문이다. vector는 연속되게 저장된다 하지만 list는 3개씩 떨어진 상태로 저장된다. find를 하게 되면 vector에서는 1부터 4까지 하나씩 움직이며 찾게 되고 움직인 뒤 그 메모리는 캐시 된다 그런데 list는 떨어진 상태로 존재하기 때문에 1을 찾고 캐시를 하고 캐쉬가 캐시 미스가나고 2를 찾고 캐쉬를 .. 2022. 6. 6. list, forward_list list (Double Linked List) list 는 라는 헤더 파일을 가진다. list는 insertion/removal o(1)을 가진다 list는 Double Linked List 다 Double Linked List란 무엇일까? list nums는 포인터 두개와 size를 가지고 있다 포인트중 하나는 first를 가르키고 하나는 last를 가르킨다 size는 원소의 개수이다. 원소의 두번째 포인터는 다음 원소의 첫번째 포인터를 가르키는 형식으로 연결 되어 있다 이걸 Double Linked List라 한다. emplace_back() - O(1) emplace_front() - O(1) emplace() - O(1) find() - O(n) Merge, splice merge Merges t.. 2022. 6. 3. 이전 1 다음