STL 의 map, set 데이터 구조 기반

STL 의 map, set 데이터 구조의 기본 요약: 본 고 는 몇 가지 기본 적 인 STL 을 열거 합 니 다. 맵 과 STL set 의 문 제 는 이러한 문 제 를 풀 어 STL 관련 용기 내부 의 데이터 구 조 를 설명 하고 마지막 으로 UNIX / LINUX 자체 균형 이 진 트 리 라 이브 러 리 함수 와 map 를 제시 했다. set 선택 문제, 맵 분석, set 의 강점.STL 을 깊이 배우 고 싶 고 STL 에 대해 서 알 고 싶 어 요. map 등 용기 밑바닥 데이터 구조 와 관련 된 친구 들 에 게 참고 가치 가 있 습 니 다.
        STL map 와 set 의 사용 은 복잡 하지 않 지만 이해 하기 어 려 운 부분 도 있 습 니 다. 예 를 들 어:
        왜 맵 과 set 의 삽입 삭제 효율 이 다른 시퀀스 용기 보다 높 습 니까?
        왜 매번 insert 이후 이전에 저 장 된 iterator 는 효력 을 잃 지 않 습 니까?
        왜 맵 과 set 는 vector 처럼 reserve 함수 로 데 이 터 를 미리 분배 할 수 없 습 니까?
        데이터 요소 가 증가 할 때 (10000 에서 20000 개 비교) 맵 과 set 의 삽입 과 검색 속도 변 화 는 어 떻 습 니까? 
        아마도 어떤 사람 은 대략적인 원인 을 대답 할 수 있 을 것 이다. 그러나 철저하게 이해 하려 면 STL 의 하부 데이터 구 조 를 알 아야 한다.
        C++ STL 광범 위 한 찬 사 를 받 은 이 유 는 vector 뿐만 아니 라 많은 사람들 이 사용 하고 있 습 니 다. string, list 등 편리 한 용기, 더 중요 한 것 은 STL 이 복잡 한 데이터 구조 알고리즘 과 대량의 상용 데이터 구조 조작 을 밀봉 한 것 이다.vector 패 키 징 배열, list 는 링크, map 와 set 는 이 진 트 리 등 을 패 키 징 했 습 니 다. 이 데이터 구 조 를 패 키 징 할 때 STL 은 프로그래머 의 사용 습관 에 따라 구성원 함수 방식 으로 자주 사용 하 는 동작 입 니 다. 예 를 들 어 삽입, 정렬, 삭제, 찾기 등 입 니 다.사용자 로 하여 금 STL 사용 과정 에서 낯 설 지 않 게 하 다.
        C++ STL 표준 관련 용기 set, multiset, map, multimap 내부 에서 사용 하 는 것 은 매우 효율 적 인 균형 검색 이 진 트 리 입 니 다. 빨 간 검 은 나무 도 RB 나무 (Red - Black) 가 됩 니 다. Tree)。RB 트 리 는 일반적인 밸 런 스 이 진 트 리 (저자 이름, Adelson - Velskii, Landis 에 따라 AVL - 트 리 라 고 부 르 는 책 도 있 음) 보다 통계 성능 이 좋아 STL 에서 관련 용기 의 내부 구조 로 선택 했다.본 고 는 AVL 나무 와 RB 나무의 실현 과 그들의 우열 을 상세 하 게 소개 하지 않 을 것 이다. RB 나무의 상세 한 실현 은 빨간색 과 검은색 나 무 를 참조한다. 이론 과 실현.본 고 는 처음에 제기 한 몇 가지 문제 에 대한 대답 에 대해 map 와 set 의 바 텀 데이터 구 조 를 간단하게 소개 한다.
        왜 맵 과 set 의 삽입 삭제 효율 이 다른 시퀀스 용기 보다 높 습 니까?
        대부분의 사람들 은 관련 용기 에 있어 서 메모리 복사 와 메모리 이동 을 할 필요 가 없 기 때문에 간단 하 다 고 말한다.맞다, 확실히 그렇다.map 와 set 용기 안의 모든 요 소 는 노드 의 방식 으로 저장 되 고 노드 구조 와 링크 의 차이 가 많 지 않 으 며 부모 노드 와 서브 노드 를 가리킨다.구조 도 는 다음 과 같 을 수 있 습 니 다.
            A            / \           B   C          / \ / \         D  E F  G
        따라서 삽입 할 때 조금 만 바 꾸 고 노드 의 지침 을 새로운 노드 에 가리 키 면 된다.삭제 할 때 와 비슷 합 니 다. 조금 만 바 꾸 면 삭제 노드 를 가리 키 는 지침 을 다른 노드 에 가리 키 면 됩 니 다.이곳 의 모든 조작 은 포인터 가 바 뀌 는 것 으로 메모리 이동 과 관계 가 없다.
        왜 매번 insert 이후 이전에 저 장 된 iterator 는 효력 을 잃 지 않 습 니까?
        위의 답안 의 해석 을 보 았 으 니, 너 는 이미 이 문 제 를 쉽게 해석 할 수 있 을 것 이다.iterator 는 노드 를 가리 키 는 지침 에 해당 합 니 다. 메모리 가 변 하지 않 았 습 니 다. 메모리 를 가리 키 는 지침 이 어떻게 효력 을 잃 을 수 있 습 니까? (물론 삭 제 된 요소 자체 가 효력 을 잃 었 습 니 다)vector 에 비해 매번 삭제 와 삽입 할 때마다 포인터 가 효력 을 잃 을 수 있 습 니 다. push 를 호출 합 니 다.백 을 끝부분 에 삽입 하 는 것 도 마찬가지다.내부 데이터 의 연속 저장 을 확보 하기 위해 iterator 가 가리 키 는 블록 에 삭제 와 삽입 과정 에서 다른 메모리 에 덮어 쓰 거나 메모리 가 풀 렸 을 수 있 습 니 다.시 pushback 일 때 용기 내부 공간 이 부족 할 수 있 습 니 다. 더 큰 메모리 가 필요 합 니 다. 예전 의 메모리 만 방출 하고 더 큰 메모 리 를 신청 하 며 기 존의 데이터 요 소 를 새로운 메모리 로 복사 합 니 다. 마지막 으로 삽입 해 야 할 요 소 를 마지막 에 두 면 예전 의 메모리 포인터 가 자 연 스 럽 게 사용 되 지 않 습 니 다.특히 find 등 알고리즘 과 함께 사용 할 때 이 원칙 을 명심 하 세 요. 만 료 된 iterator 를 사용 하지 마 세 요.
        왜 맵 과 set 는 vector 처럼 reserve 함수 로 데 이 터 를 미리 분배 할 수 없 습 니까?
        나 도 예전 에 이렇게 물 었 다. 그 원 리 를 따 져 볼 때 이 를 일 으 킨 이 유 는 map 와 set 내부 에 저 장 된 것 은 요소 자체 가 아니 라 요 소 를 포함 하 는 노드 이기 때문이다.즉, map 내부 에서 사용 하 는 Alloc 는 map < Key 가 아 닙 니 다. Data, Compare, Alloc > 선언 할 때 인자 에서 들 어 오 는 Alloc 입 니 다.예 를 들 면:

map<int, int, less<int>, Alloc<int> > intmap;

        이때 intmap 에서 사용 하 는 allocator 는 Alloc < int > 가 아 닙 니 다. 변 환 된 Alloc 를 통 과 했 습 니 다. 구체 적 인 변환 방법 은 내부 에서 Alloc < int >: rebind 를 통 해 새로운 노드 분배 기 를 재 정 의 했 습 니 다. 상세 한 실현 은 STL 의 Allocator 를 철저히 학습 하 는 것 을 참조 하 십시오.사실 한 가지 만 기억 하 세 요. map 와 set 내 에 있 는 분배 기 가 바 뀌 었 으 니 reserve 방법 은 바라 지 마 세 요.
        데이터 요소 가 증가 할 때 (10000 개 와 20000 개 비교) 맵 과 set 의 삽입 과 검색 속도 변 화 는 어 떻 습 니까?
        로그 2 의 관 계 를 알 고 있다 면 그 답 을 철저히 알 아야 합 니 다.맵 과 set 에서 찾 는 것 은 2 분 으로 찾 는 것 입 니 다. 즉, 16 개의 요소 가 있 으 면 최대 4 번 비교 해 야 결 과 를 찾 을 수 있 고 32 개의 요소 가 있 으 며 최대 5 번 비교 할 수 있 습 니 다.그럼 10000 개 는 요?최대 비교 횟수 는 log 10000, 최대 14 회 입 니 다. 20000 개의 요소 라면 요?기껏해야 15 번 에 불과 하 다.보 셨 죠? 데이터 양 이 배로 늘 었 을 때 검색 횟수 는 1 회 에 불과 하고 1 / 14 의 검색 시간 이 늘 었 을 뿐 입 니 다.네가 이 이 치 를 알 게 되면 안심 하고 안에 원 소 를 넣 을 수 있 을 것 이다.
        마지막 으로 맵 과 set 에 대해 Winter 는 또 하나의 c 언어 포장 창고 와 의 효율 비교 도 언급 해 야 한다.많은 유 닉 스 와 Liux 플랫폼 에서 isc 라 는 라 이브 러 리 가 있 는데 그 안에 다음 과 같은 성명 과 유사 한 함 수 를 제공 합 니 다.

voidtree_init(void**tree);
void*tree_srch(void**tree, int(*compare)(), void*data);
voidtree_add(void**tree, int(*compare)(), void*data, void(*del_uar)());
inttree_delete(void**tree, int(*compare)(), void*data,void(*del_uar)());
inttree_trav(void**tree, int(*trav_uar)());
voidtree_mung(void**tree, void(*del_uar)());

        많은 사람들 이 이 함수 들 을 직접 사용 하면 STL 보다 map 속도 가 빨 라 요. STL 때문에... 맵 에 템 플 릿 같은 거 많이 사 용 했 어 요.그렇지 않 으 면 알고리즘 이 아니 라 메모리 조각 에 차이 가 있다.이 함 수 를 직접 사용 하려 면 new 노드 에 직접 가 야 합 니 다. 노드 가 매우 많 고 잦 은 삭제 와 삽입 을 할 때 메모리 조각 이 존재 합 니 다. STL 은 자신의 Allocator 로 메모 리 를 분배 하고 메모리 풀 방식 으로 이 메모 리 를 관리 하면 메모리 조각 을 크게 줄 여 시스템 의 전체적인 성능 을 향상 시 킬 수 있 습 니 다.Winter 는 자신의 시스템 에서 테스트 를 한 적 이 있 으 며, 이전의 모든 isc 함수 코드 를 map 로 바 꾸 었 으 며, 프로그램 속 도 는 기본적으로 일치 합 니 다.시간 이 오래 실행 되면 (예 를 들 어 백 스테이지 서비스 프로그램) 맵 의 장점 이 나타난다.다른 측면 에서 볼 때 맵 을 사용 하면 인 코딩 의 난이 도 를 크게 낮 출 뿐만 아니 라 프로그램의 가 독성 도 증가 할 수 있다.왜 기꺼이 하지 않 겠 는가?