STL 관련 용기 의 set \ map --- - STL 소스 코드 를 예 로 들 면

관련 용기 의 특징: 사용 하 는 요 소 는 요소 의 키 값 에 따라 자동 으로 정렬 됩 니 다.
set

STL 의 관련 용기 저층 데이터 구 조 는 빨간색 과 검은색 나무 로 그 기능 은 모두 저층 데이터 구조 에서 제공 하 는 해당 인 터 페 이 스 를 호출 하 는 것 이다.

set 원 의 요 소 는 map 처럼 키 (key) 와 값 (value) 을 동시에 가지 지 않 습 니 다.

set 요소 의 키 는 값 이 고 값 은 키 이 며 두 요소 가 같은 키 를 가 질 수 없습니다.

multiset 는 같은 키 가 존재 할 수 있 습 니 다.

set 요소 의 키 와 값 이 같 기 때문에 set 요소 의 값 을 수정 할 수 없습니다.(데이터 구 조 는 key 에 따라 요 소 를 정렬 하고 value 의 변경 은 트 리 에 있 는 요소 의 배열 순 서 를 바 꿉 니 다).

set 용기 가 제공 하 는 교체 기 는 const iterator 입 니 다.set 클래스 의 성명:

template 
class set;

set 클래스 는 세 개의 템 플 릿 매개 변 수 를 포함 하고 키 형식Key, 키 비교 방법compare, 분배 기 종류Alloc；평소에 자주 사용 하 는 것 은 첫 번 째 템 플 릿 매개 변수: 키 종류Key, 예:

set iset={1,2,3,4,5};

다른 두 템 플 릿 매개 변 수 는 특수 한 응용 장면 에서 역할 을 발휘 합 니 다.compare 템 플 릿 파 라미 터 는 용기 에 있 는 원소 의 비교 방법 을 지정 할 수 있 으 며, 용기 에 저 장 된 원소 의 크기 에 따라 메모리 분배 정책 을 수정 할 수 있 습 니 다Alloc。이 두 매개 변 수 는 set 의 구조 함수 인 자 를 설정 하여 지정 할 수 있 습 니 다.

  explicit set(const _Compare& __comp,
               const allocator_type& __a = allocator_type())
    : _M_t(__comp, __a) {}

set 가 지정 하지 않 은 두 템 플 릿 인 자 를 사용 하면 기본 버 전 을 사용 합 니 다.

template ),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set;

map

map 의 모든 요 소 는 pair < 입 니 다.key >, 키 쌍 을 동시에 가지 고 있 습 니 다.

맵 은 두 원소 의 키 가 같 을 수 없습니다.

map 는 교체 기 를 통 해 요소 의 값 을 수정 할 수 있 지만 키 를 수정 할 수 없습니다 (요소 배열 을 변경 할 수 있 습 니 다).map iterator 는 const iterator 와 mutable iterator 사이 에 있 는 교체 기 입 니 다.

template 
class map ;

map 류 는 네 가지 템 플 릿 매개 변수 가 있 는데 그것 이 바로 키 유형 입 니 다.Key, 값 유형Tp, 키 비교 방법compare, 분배 기 종류Alloc；평소에 자주 사용 하 는 것 은 앞의 두 템 플 릿 매개 변수: 키 형식Key 와 값 유형Tp, 예:

#include
#include

다음 두 개의 인 자 를 지정 하지 않 으 면 기본 템 플 릿 인 자 를 사용 합 니 다.

template ),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class map;

맵 의 키 맵 값 은 [] 연산 자 를 통 해 진 행 됩 니 다:

  _Tp& operator[](const key_type& __k) {
    iterator __i = lower_bound(__k);
    // __i->first is greater than or equivalent to __k.
    // insert  ，             ，      ，         
    //            ->value_type(__k,_Tp()),          map  
    //   ，__i              ，       。
    if (__i == end() || key_comp()(__k, (*__i).first))
      __i = insert(__i, value_type(__k, _Tp()));
    return (*__i).second;
  }

이 함 수 는 우선 키k. 검색 을 진행 합 니 다. 찾 지 못 하면 검색 끝 위치 에 새로운 노드 를 삽입 합 니 다.함수 가 되 돌아 오 는 것 은 키 에 대응 하 는 값 의 인용 이기 때문에 값 을 부여 할 수 있 습 니 다.
multiset 와 multimap
multiset 와 multimap 의 용법 은 set, map 의 용법 과 같 지만 중복 되 는 키 를 허용 합 니 다.소스 코드 에 대응 하 는 것 은 multi 버 전의 삽입 작업 이 빨 간 검 은 나무의 insert 를 호출 하 는 것 입 니 다.equal 인터페이스, 일반 버 전 은 insert유 니 크 인터페이스.multiset 를 예 로 들 면 set 버 전

  pair insert(const value_type& __x) { 
    pair __p = _M_t.insert_unique(__x); 
    return pair(__p.first, __p.second);
  }

multiset 버 전

  iterator insert(const value_type& __x) { 
    return _M_t.insert_equal(__x);
  }

작은 매듭

map 와 set 는 자주 사용 하 는 관계 형 용기 로 이들 내 부 는 모두 빨 간 검 은 나 무 를 저층 데이터 구조 로 사용한다.클래스 가 제공 하 는 인 터 페 이 스 는 모두 빨 간 검 은 나무 가 제공 하 는 해당 인 터 페 이 스 를 호출 합 니 다.붉 은 검 은 나무 류 에 대한 패키지 입 니 다.

set 와 map 의 요 소 는 모두 자동 으로 정렬 됩 니 다.

set 의 요 소 는 키 (같은 값) 입 니 다.map 의 요 소 는 키 쌍 (key - value pair) 으로 키 값 에 대한 맵 기능 을 제공 할 수 있 습 니 다.

set 의 값 (키) 은 수정 할 수 없습니다. map 에서 요소 의 값 은 수정 할 수 있 지만 키 는 수정 할 수 없습니다.