목록벡터와 리스트의 차이 (1)

혀니의 이거저거 뿌시기

[C++]Vector와 List의 차이점

1.Array Vs List 차이점 Array : 메모리 상에 데이터가 연속적으로 저장됨 List : 메모리 상에 데이터가 비연속적으로 저장됨 2.Vector Vs List 차이점 99퍼센트는 벡터를 씀 (벡터가 더 빠름) 랜덤 접근 삽입/삭제 뒤쪽 삽입/삭제 벡터 O(1) O(n) - 하나하나 다 밀어야함 O(1) 리스트 O(n) - iterator를 사용해야함 O(1) O(1) if find함수를 쓸 때는 둘 다 O(n) 시간복잡도가 필요함 but vector의 find가 훨씬 빠름 실제 저장 공간은 격자구조. vector는 순차적으로 저장됨 -> 다 cache안에 들어감 list는 여기저기 끊어져있음 -> cache miss가 일어남 더보기 자료구조의 성능을 비교할 때는 원소의 크기, 지역성에 대한..
CS/C++ 2023. 10. 1. 12:09
이전 Prev 1 Next 다음