vector와 list
vector
배열과 비슷한 구조로 메모리에 연속적으로 저장되며 배열과는 다르게
동적으로 할당하기 때문에 공간의 확장,축소가 가능하다.
그치만 공간의 확장,축소시에 기존 데이터를 복사하고 삭제후에 공간의
크기를 확장,축소하고 복사해둔 기존데이터를 붙여넣기하는 작업을
거치기때문에 비용이 크다.그렇기 때문에 reserve 함수를 이용해서 미리
공간의 크기를 정해놓고 사용하는것이 좋다.
중간 삽입,삭제가 어렵다.중간에 데이터를 추가하면 vector는 메모리가
연속적으로 저장되어있기 때문에 추가할 데이터의 위치에있던 데이터부터
모두 한칸씩 뒤로 밀어줘야한다.삭제 역시 삭제후에 삭제한 데이터의 다음
데이터부터 모두 한칸씩 앞으로 한칸씩 땡겨줘야한다.
그렇기 때문에 제일 뒤의 데이터 삭제에는 큰 문제가 없다.
삽입 역시 메모리의 크기가 충분하다면 문제가 없다.
인덱스로 랜덤으로 데이터에 접근이 가능하다.메모리가 연속적이기 때문에
주소들이 모두 붙어있고 그렇기 때문에 중간인덱스(n번째)로 접근시
begin()+n 을 하여 원하는 n의 위치로 바로 접근이 가능하다.(랜덤 엑세스)
그렇기 때문에 원하는 위치에서 데이터 순회도 가능하다.(랜덤 원소 순회)
데이터의 검색(순회)은 모든 인덱스마다 다 검색해봐야 하기때문에 검색속도가 느리다.
list
list는 node(노드)를 기반으로 한 doubly linked list(양방향 연결 리스트) 구조로 되어있다.
여기서 노드란 자기 자신과 같은 자료형의 참조형을 가지고 있는 방식이다.
vector와는 다르게 메모리가 연속적으로 되어있지 않고 각각의 데이터들은 자기의
전 데이터와 다음 데이터하고 노드를 이용하여 서로와 서로를 연결해주고 있는 구조다.
노드를 사용하기 때문에 추가적 메모리 비용이 발생한다.
노드로 자기의 전 데이터와 다음 데이터를 알고 있기때문에 중간 삽입,삭제가 용이하다.
삽입: 삽입하려는 위치의 전 데이터와 다음 데이터 사이에 데이터를 넣고
전 데이터의 노드의 next를 연결해주고
다음 데이터의 노드의 prev를 연결해주면 된다.
삭제: 삭제되는 노드의 전 노드의 next와
삭제되는 노드의 다음 노드의 prev를 연결해주면 된다.
랜덤으로 접근이 불가능하다.
연결된 노드로 처음이나 끝부터 순차적으로 접근하는 방법 말고는 없기 때문이다.
그렇기 때문에 검색(순회)이 느리다.
list와 vector 는 둘다 순회 속도가 느리다.Iterator 이용해서 순회를 하게되는데
list와 vector 둘다 주소값을 이용해서 순회하지만
list의 경우는 노드의 prev 혹은 next의 값을 받아오면서 이동한다.
반면 vector의 경우에는 메모리가 연속적으로 되어있기 때문에
단순히 인덱스의 값만 가져와서 바로바로 접근이 가능하다.
그렇기 때문에 순회 속도는 vector가 더 빠른것이다.