List / Dictionary(C++에서의 map) / Set

[C++] set container 정리 및 사용법 (tistory.com)

[C++] set container 정리 및 사용법

 

*list

C++의 list는 딱 더블 링크드리스트와 구조가 같음.

다만, C++에서는 미리 구현되어있다는 점이 다름

순서를 유지하는 구조임.

노드기반 컨테이너이며, 이중연결리스트라고 생각하면 됨

원소 탐색 시 임의접근 반복자(at(), [])는 불가능하고, 양방향 반복자를 이용해 탐색을 함

input(), erase() 멤버함수를 통해 노드 중간에서도 삽입 삭제가 가능함.

특정 위치를 정해둔 상태에서 삽입, 삭제가 이루어질 경우는 vector에 비해 삽입, 삭제가 빠르다.

중간데이터 삭제, 삽입이 자주 일어나면서

순차적으로 저장된 데이터를 빈번히 검색하지 않을때 사용하는것이 좋음.

 

*map(python - 딕셔너리)

노드 기반으로 구현되어있고, 균형이진트리임.

key, value로 이루어져있으며, pair형태 객체로 저장됨

set과 마찬가지로 삽입되면서 자동으로 정렬이 됨(디폴트는 오름차순)

저장공간의 필요에 따라서 allocator 객체를 사용함(동적할당함)

 

*set: 노드 기반 컨테이너이며, 균형 이진트리로 구현되어있음.

key라 불리는 원소들의 집합으로 이루어짐

중복이 허용되지 않음 (이게 젤 큰 특징)

원소가 insert멤버함수에 의해 삽입되면, 원소는 자동으로 정렬됨(디폴트 정렬 기준은 오름차순)

 

그림에서 보면 알듯이, 중위순회를 통하여 순서대로 출력 가능