vector 1. C언어의 배열과 동일한 형태의 연속된 메모리를 보장하는 유일한 컨테이너.
2. 컨테이너의 마지막에서 발생하는 추가와 삭제는 쉽게 처리되지만, 처음과 중간에서의 처리는 메모리 이동으로 인해 비용이 많이 든다.
3. 연속된 메모리를 보장하기 때문에, deque 컨테이니ㅓ와 함꼐 임의 접근 반복자를 제공한다.
배열처럼 [] 연산자를 사용한 모든 연산을 할 수 있다. 특히 [] 연산자를 사용해서 요소에 직접 접근하는 것이 가능.
deque 1. vector 컨테이너와 비슷하게 생각되지만, 메모리를 할당하는 전략이 다름. 다만 외부에서 볼 때는 별 차이가 없어 보인다.
2. 컨테이너의 처음과 마지막에서 발생하는 추가와 삭제는 쉽게 처리되지만, 중간에서의 처리는 메모리 이동으로 인해 비용이 많이 발생
3. 대부분의 경우 연속된 메모리 형태로 만들어지지만, 표준에서 보장하지는 않는다.
[] 연산자를 사용할 수 있는 임의 접근 반복자 제공list 1. 전형적인 구조체 형태를 띠는 ,이중, 연결 리스트의 자료 구조를 사용.
2. 각각의 요소가 단일 구조체로 구성 되기 때문에, 추가와 삭제에서 메모리 이동이 전혀 일어나지 않아 최적의 성능 보장
3. 양방향 반복자를 제공하기 때문에 검색에 있어서 모든 노드를 뒤져야 하는 어려움이 있다.
추가와 삭제에 대한 비용은 적지만 추가나 삭제가 일어나기까지의 비용이 많이 발생set 1. 자체적으로 정렬 기능을 갖고 있다. 기본 자료형 이외의 자료형에 대해서는 프로그래머가 직접 정렬 기능을 수행하는 조건자를 제공해야 한다.
2. 컨테이너에 저장되는 값으로 크기를 비고한다. 조건자의 성격에 따라 큰 값이 앞에 오는 내림차순, 작은 값이 앞에 오는 오름차순 정렬이 있다.
3. 저장되는 요소가 구조체인 경우, 구조체의 특정 멤버의 크기를 비교하는 조건자를 제공함으로써 일부 멤버를 사용한 정렬도 가능.
4. 트리 자료구조를 사용하기 때문에 검색에 탁월한 성능을 발휘multiset 1. set 컨테이너의 기능 중에서, 중복된 값을 갖는다는 사실 이외에는 모두 동일
2. 중복된 요소들을 위한 equal_range 와 같은 전용 멤버 함수 제공
map 1. set 컨테이너와 다른 점은, 값에 의한 비교가 아닌 별도의 키를 사용해서 정렬되고 나머지는 동일 당연히 정렬에 사용한 키가 구조체일 수 도 있다.
2. 일반적으로 키에는 가벼운 자료형을, 키로 참조되는 값에는 무거운 자료형을 사용함
multimap 1. map 컨테이너의 기능 중에서, 중복된 값을 갖는다는 사실 이외에는 모두 동일
2. 중복된 요소들을 위한 equal_range와 같은 전용 멤버 함수 제공
접근 배열 : 탁월. [] 연산자를 사용해서 어느 위치로든 한번에 접근 가능
리스트 : 엄청 떨어짐. 접근하려는 요소가 중간에 들어가 있다면 이전 요소를 모두 거쳐야 함.
트리 : 배열보다는 못하지만, 대단히 좋음. 보통 이진 트리로 구현하기 때문에, 1000개의 요소에
대해 10회의 비교로 접근 가능. 갯수가 늘어나도 비교횟수는 거의 늘어나지 않는다.
수정 배열 : 가능
리스트 : 가능
트리 : 불가능 (정렬이 기본이기 때문에 수정할 경우 정렬 상태가 깨짐)삽입/삭제 배열 : 엄청 떨어짐. 중간에 새로운 요소가 삽일될 경우 삽입 위치 이후의 모든 요소는 뒤로 밀려나야함
엄청난 메모리 이동이 불가피. 마지막 요소를 추가할 경우에는 이동이 필요 없어 탁월
리스트 : 탁월. 용소 각각을 독립적으로 유지학 ㅣ때문에 삽입과 삭제에 대한 비용이 거의 없음.
다만 삽입이나 삭제 위치를 찾기까지 비용이 많이 든다.
트리 : 리스트만큼 좋은데가, 삽입/삭제 위치를 찾기 위한 비용이 최소한도로 유지됨배열 : vector, deque
리스트 : list
트리 : set, multiset, map, multimap
반복자 중복요소 정렬
vector : 임의접근 : 가능 : X
(동적배열) [] 사용 별도 알고리즘사용deque : 임의 접근 : 가능 : X
(배열의배열) [] 사용 별도 알고리즘 사용
list : 양방향 : 가능 : X
(이중 sort 멤버함수 사용
연결리스트)set : 양방향 : 불가능 : O
(이진트리) (읽기전용)
multiset : 양방향 : 가능 : O
(이진트리) (읽기전용)
map : 양방향 : 불가능(키) : O (키)
(이진트리) (키는 읽기전용) 가능(값) X (값)
multimap : 양방향 : 가능 : O (키)
(이진트리) (키는 읽기전용) X (값)