List, Vector, deque, Array 비교

다수의 데이터를 저장할 수 있는 컨테이너들중  자주 사용되는 3가지(벡터, 덱, 리스트)들의 특징을 정리해보았다.

어차피 속도는 그리 중요하지 않기에 ㅎㅎ 그냥 편한걸로 쓰는 경우가 많았다 

하지만 다수의 데이터를 다루게되면 처리속도에 큰 영향을 줄수 있는 요소이므로

컨테이너별 특징, 장단점을 다루고 넘어가려고 한다.

 

1. Vector 

array 기반 구조 but, 크기를 바꿀수 있음

장점)

컨테이너의 끝에 데이터를 추가/삭제가 매우 빠르다.

메모리가 연속적,  position index로 접근, iterator 연산자를 이용한 접근이 가능하다.

물론, index를 이용한 접근도 가능하다.

단점)

컨테이너의 중간에서 삽입/제거 효율이 떨어진다. (모든 원소들을 한칸씩 당기거나 밀어야 함)

원소들을 연속적으로 배치해야 하므로 push_back 함수를 많이 사용하여 메모리공간이 부족해지면 전체 메모리를 재할당한다. 

+) 똑똑하신 분들의 노력으로 C+11부터는 push_back 함수의 시간 복잡도가 항상 상수시간이라고 한다. (꾸벅)

 

+) 벡터 관련 함수

v.assign(n) : 0인 원소 n개로 초기화 v.assign(n, k) : 값 10인 원소 5개로 초기화 v.begin() 첫번째칸의 iterator 반환; v.end() 마지막칸의 iterator 반환; v.front() : 첫 번째 원소 v.back() : 마지막 원소 v.at(i) : i 번째 원소 v.push_back(k) : 배열 마지막에 k 추가 v.insert(v.begin(), 3) : iterator의 위치에  '3' 추가 v.size() : 백터내 원소의 갯수 v.capacity() : 할당된 메모리 크기 (공간 수) v.reserve(10) : 메모리 선언(10칸) , 빈공간은 냅둠 v.resize(10) : 메모리 선언(10칸) 후 빈 공간에 0으로 초기화 v.clear() : 전체 원소 삭제 v.erase(v.begin()) : iterator가 가리키는 원소 삭제, 다음원소를 가르키는 iterator 반환

+) vec = {1, 2, 3, 4, 5}가 있을때

vec.insert(vec.begin(), 100); 을 하면 vec = {100, 1, 2, 3, 4, 5}

vec.insert(vec.end(), 100); 을 하면    vec = {1, 2, 3, 4, 5, 100} 이 된다.

 

insert는 iterator 위치에 원소를 추가 한다. 그런데,

vec.begin()에서는 원소 앞에 붙고, vec.end()에서는 원소 뒤에 붙는점이 혼란 스러웠다.

 

이걸로 한참 마음이 불편했는데 이걸 보고 게비스콘 해버렸따 

vec.begin()은 원소를 가르키지만, vec.end()는 마지막원소가 아닌 배열의 범위 밖에 위치한다. 

2. deque

거의 벡터와 유사함

장점)

컨테이너의 앞, 뒤에서  추가/삭제가 빠르다.

index를 이용해 중간 원소에 접근이 가능하다.

대체로 vector와 유사하지만 메모리공간이 불연속적이라는 차이점이 있다.

때문에 메모리 할당이 많은경우 전체를 재할당 할 필요가 없어 vector보다 비용이 적게 든다.

단점)

메모리가 불연속적이므로 포인터 연산이 불가능하다.

 

3. list (double linked List)

장점)

모든위치에서 삽입/삭제가 빠르다. (링크드리스트의 특성)

단점)

중간원소에 접근이 어렵다. 처음또는 뒤에서부터 선형탐색으로 접근해야함.

연결정보를 저장하기위해 메모리가 추가 사용된다.

 

+) 4. array

위의 vector, deque, list 는 동적배열이므로 필요에 따라 크기가 자동으로 늘어난다.

하지만 array는 정적 배열이라는 것이 가장 큰 차이점

이를 제외하면 vector와 가장 유사한 배열이다.

장점)

검색이 빠르다. 인덱스를 통한 임의 접근이 가능

메모리가 연속적이다.

단점)

컴파일 시점에 크기가 확정. 배열의 크기를 미리 선언해주어야한다.

삽입/삭제가 자주 일어날 경우 비효율적이다.