다시 정리하는 C++ STL 자료구조 map/set

[ STL 자료구조 map / set ] STL array, vector, list가 연속 컨테이너(Sequential Container)였다면 map과 set은 연관 컨테이너(Associative Container)이다. 연관이라는 말은 저장하려고 하는 자료와 key값이 서로 관련이 있다는 의미이다. map은 pair를 원소로 저장하는데, key를 기준으로 데이터를 정렬한다. set은 key를 기준으로 원소를 정렬 상태로 저장하지만, value가 따로 있지 않다. 즉, set은 key와 value가 같은 데이터를 원소로 저장한다. 연관 컨테이너는 찾고자 하는 원소를 빨리 찾기 위해 사용한다. 여기서 빠르다는 것은 연속 컨테이너보다 빠르다는 의미이다. 연관 컨테이너에서 원소를 찾는 데 걸리는 시간 복잡도..

2020.08.10

03. [C++] STL (Standard Template Library) - Map

Map 표준 연관 컨테이너. (비 선형적). 자가 균형 이진 탐색트리 (레드 - 블랙 트리) 기반이다. 노드 기반. (비 연속된 메모리 구조.) 원소 하나가 Key와 Value 한 쌍으로 이루어져 있다. (중복 Key는 허용하지 않는다.) 삽입, 삭제 시 Key 기준으로 매번 정렬이 일어난다. (빈번한 삽입, 삭제 불리.) Key값을 통해서 [] 접근이 가능하다. 이진 탐색 트리 기반이다. (탐색 유리.) [ Map의 선언 ] map로 선언 한다. Key와 Value에는 구조체나 클래스가 올 수 도 있다. [ Map의 원소 삽입 ] (1) pair 구조체를 이용한 Map 원소 삽입. map에 원소를 삽입하기 전에 pair구조체를 생성해야한다. 즉, map의 원소는 pair로 이루어졌다. first - K..

2019.06.25