예전/STL (6) 썸네일형 리스트형 [STL] 연관 컨테이너 ( set,multiset,map,multimap ) 연관 컨테이너 정렬 연관 컨테이너란, 컨테이너 내의 자료들이 규칙에 따라 연관, 정렬 되어있는 컨테이너이다.일정한 규칙으로 정렬되어있기 때문에 검색속도가 빠른 것이 장점이다. 모든 연관 컨테이너는 균형 2진 트리로 레드 블랙 트리이다.레드 블랙 트리란, AVL 트리로 삽입, 삭제 검색에서 최악의 경우에도 일정한 실행시간을 보장하는 것이다. 연관 컨테이너는 데이터를 Push한다는 의미보다는 트리에 Insert 한다는 의미로 Push함수 대신 Insert 함수를 가지고 있다. 그리고 AVL 트리 이므로 삽입 후 균형을 맞춘다. 연관 컨테이너는 저장된 데이터를 빠르게 검색할 목적으로 사용되므로 주로 검색을 하는 함수를 가지고 있고, 검색 시간은 log시간이다. 양방향 반복자를 사용한다. Set Set과 mul.. [STL] 연관 컨테이너 ( set,multiset,map,multimap ) set 과 multiset , map, multimap은 연관 컨테이너이자, 노드 기반 컨테이너이다. 모든 연관 컨테이너는 균형 이진 트리로 레드블랙트리이다.레드블랙트리란 AVL 트리로 삽입, 삭제, 검색에서 최악의 경우에도 일정한 실행시간을 보장하는 것이다. ( AVL 트리 : 자식노드와의 높이차이가 1보다 크지 않은 것으로 그 균형을 맞추기 위해 회전한다. ) 연관 컨테이너는 데이터를 push한다는 의미보단 트리에 insert한다는 의미로 push함수 대신 insert함수를 가지고 있다. 연관 컨테이너는 저장된 데이터를 빠르게 검색할 목적으로 사용되므로 주로 검색류의 함수를 가지고 있다.그리고 양방향 반복자를 사용한다. 검색시간은 log시간이다. 1. set각 노드마다 다른 key가 있는 컨테이너이다.. [STL] 반복자와 반복자 무효화 현상 반복자 반복자란 컨테이너에 저장된 요소를 순회하고 접근하는 스마트 포인터이다. ( 스마트 포인터란 언제 할당되고 해제되는지를 아는 똑똑한 포인터라는 뜻이다. ) 반복자는 조작 방법에 따라 5가지 종류로 나뉠 수 있다. 1. 입력 반복자(input iterator) : 반복자가 가리키는 위치의 데이터를 읽기만 가능한 반복자로 다음 위치로 이동할 수 있다. 2. 출력 반복자(output iterator) : 반복자가 가리키는 위치의 데이터를 쓰기만 가능한 반복자로 다음 위치로 이동할 수 있다. 3. 순방향 반복자(forward iterator) : 입력 반복자와 출력 반복자의 기능과 더불어 가리키는 위치의 데이터를 여러번 읽거나 쓸 수 있고 현재의 위치를 저장하여 동일한 위치에서 다시 순회를 시작할 수 있다.. [STL] 컨테이너의 분류 및 정리 ( Vector, List, String, Deque ) 1. Vector : 시퀀스 컨테이너 이면서 , 연속 메모리 기반 컨테이너이다. 특징 ① 메모리가 증가할 때 현재 메모리의 1.5배로 증가한다. ② 임의 접근 반복자를 사용하며 산술 연산이 가능하다. ③ 삽입, 삭제 보단 검색에 용이하다. ④ 삽입 삭제시 메모리를 재할당하고 컨테이너를 복사해야 한다. 2. List : 시퀀스 컨테이너 이면서 , 노드 기반 컨테이너이다. 특징 ① 삽입, 삭제에 용이하다. (리스트의 앞뒤에 추가할 수 있다.) ② 양방향 반복자를 제공하며 산술 연산이 불가하나, 이동은 가능하다. 3. String : 시퀀스 컨테이너 이면서 , 연속 메모리 기반 컨테이너이다. 특징 ① 문자열 전용 컨테이너로 문자열 관련 함수를 제공한다. ② 임의 접근 반복자를 사용하며 산술 연산이 가능하다. .. [STL] 컨테이너 컨테이너 컨테이너란 부둣가에 많이 보이는 박스로, C++에선비슷한 성질의 객체를 한군데에 모아 관리하고 저장하는 용기라는 뜻이다. STL의 컨테이너는 크게 순차 컨테이너와 정렬 연관 컨테이너로 나눌 수 있다. - 순차 컨테이너 ( Sequence Container ) 순차 컨테이너는 시퀀스 컨테이너 라고도 불린다. 시퀀스라는 말은 일렬로 나열되어 있다는 뜻이다.순차 컨테이너는 자료를 순차적으로 저장하는 방식에 있어 가장 일반적인 컨테이너이다. 순차 컨테이너에는 Vector, List, String, Deque 이 있다. - 정렬 연관 컨테이너 ( Sorted Associated container ) 정렬 연관 컨테이너란 컨테이너 속의 자료들이 규칙에 따라 연관 즉, 정렬 되어있는 컨테이너 이다.일정한 규.. [STL] 컨테이너의 정의 STL은 standard template Library이다. 컨테이너 컨테이너란 부둣가에 많이 보이는 박스로, C++에선 비슷한 성질의 객체를 한군데에 모아 관리하고 저장하는 용기라는 뜻이다. STL의 컨테이너는 크게 순차컨테이너, 정렬연관컨테이너, 어뎁터 컨테이너. 세 가지로 나뉠수 있다. 1. 순차 컨테이너 (Sequence container) - 삽입삭제에 제약이 없는 것들을 모아 놓은 것이다. 자료를 순차적으로 저장하는 방식에 있어 가장 일반적인 컨테이너이다. 삽입된 자료를 해당 컨테이너 성질에 맞게 무조건 저장하며 데이터의 제약은 없다. 순차적으로 임의의 위치에 원하는 요소를 삽입 삭제할 수 있다. 대표적인 STL에는 벡터, 리스트, 덱이 있다. 2. 정렬 연관 컨테이너 (Associative .. 이전 1 다음