map 와 set 의 초보 적 이해

STL 용 기 는 크게 두 종류 로 나 뉘 는데 하 나 는 서열 식 용기 이 고 하 나 는 연관 식 용기 이다.예 를 들 어: vector list deque forwardlist 등 이 용기 들 은 모두 서열 식 용기 라 고 부 릅 니 다. 그 밑 에 선형 서열 의 데이터 구조 이 고 그 안에 요소 자체 가 저장 되 어 있 기 때 문 입 니 다.서열 식 용 기 는 이른바 서열 용기, 즉 용기 중의 요 소 는 모두 순서 가 있 지만 반드시 질서 가 있 는 것 은 아니다.흔히 볼 수 있 는 시퀀스 용 기 는 vector, list, deque, queue, stack 을 포함한다.연관 식 용기 연관 식 용기 도 데 이 터 를 저장 하 는 데 쓰 인 다. 서열 식 용기 와 달리 그 안에 저 장 된 것 은 구조의 키 쌍 으로 데이터 검색 시 서열 식 용기 보다 효율 이 높다.일일이 대응 하 는 관 계 를 가 진 구 조 를 나타 내 는 데 사용 되 며, 이 구 조 는 일반적으로 두 개의 구성원 변수 키 와 value 만 포함 하고, 키 는 키 값 을 나타 내 며, value 는 키 와 대응 하 는 정 보 를 나타 낸다.이 기능 은 관련 용 기 를 사용 하 는 과정 에서 목표 요소 의 키 값 을 알 고 있다 면 이 키 를 통 해 대상 요 소 를 찾 을 수 있 으 며 전체 용 기 를 옮 겨 다 니 지 않 아 도 된다.트 리 구조의 연관 식 은 응용 장면 의 불통 에 따라 STL 은 모두 두 가지 서로 다른 구조의 관리 식 용 기 를 실현 했다. 그것 이 바로 트 리 구조 와 해시 구조 이다.용 기 는 주로 네 가지 가 있 습 니 다. map, set, multimap, multiset.저희 가 오늘 맵 과 set * 를 주로 설명해 드릴 게 요.
map
**

map 는 관련 용기 로 특정한 순서 (key 에 따라 비교) 에 따라 키 키 키 와 값 value 로 구 성 된 요 소 를 저장 합 니 다.

map 에서 키 키 키 는 보통 정렬 과 유일한 표지 요소 에 사용 되 며, 값 value 에 서 는 이 키 키 와 연 결 된 내용 을 저장 합 니 다.키 키 와 값 value 의 유형 이 다 를 수 있 으 며, 맵 내부 에서 키 와 value 는 구성원 형식 value 를 통 해type 이 연결 되 어 있 습 니 다. 다른 이름 을 pair: typedef pair value 로 지정 합 니 다.type;

내부 에서 맵 의 요 소 는 항상 키 키 키 에 따라 비교 정렬 됩 니 다.

map 에서 키 값 을 통 해 단일 요소 에 접근 하 는 속 도 는 보통 unordered 보다map 용 기 는 느 리 지만 map 는 순서에 따라 요 소 를 직접 교체 할 수 있 습 니 다 (즉, map 의 요 소 를 교체 할 때 질서 있 는 서열 을 얻 을 수 있 습 니 다).

map 는 아래 표 시 된 접근 자 를 지원 합 니 다. 즉, [] 에 key 를 넣 으 면 key 와 대응 하 는 value 를 찾 을 수 있 습 니 다.

맵 은 보통 이 진 트 리 (더 정확히 말 하면 균형 이 진 트 리) 로 이 루어 진다.

map 의 매개 변수 설명

template<class Key, //key:     key   
class T,//T：     value   
 class compare = less<Key>,//Compare:       ，map       key    ，            ，
  class Alloc = allocator<T> //             ，       ，                   
  > class map ;//   map ，       。

맵 의 교체 기
함수 선언
기능 소개
begin () 과 end ()
begin: 첫 번 째 요소 의 위치, end 마지막 요소 의 다음 위치
–
–
cbeg () 와 cend ()
begin 과 end 의 의 미 는 같 지만 cbgin 과 cend 가 가리 키 는 요 소 는 수정 할 수 없습니다.
–
–
rbegin () 과 rend ()
역방향 교체 기, rbegin 은 end 위치, rend 는 begin 위치 에 있 습 니 다.
–
–
crbegin () 과 crend ()
rbegin 과 rend 의 위치 와 마찬가지 로 crbegin 과 crend 가 가리 키 는 요 소 는 바 꿀 수 없습니다.
map 의 용량 과 요소 접근
함수 선언
기능 소개
bool empty ( ) const
맵 의 요소 가 비어 있 는 지 확인 하고 true 로 돌아 갑 니 다. 그렇지 않 으 면 false 로 돌아 갑 니 다.
–
–
size_type size() const
맵 의 유효 요소 개 수 를 되 돌려 줍 니 다.
–
–
mapped_type& operator[] (const key_type& k)
key 에 대응 하 는 val 값 을 되 돌려 줍 니 다.
맵 에서 요소 의 수정

#include 
#include 
void TestMap()
{
 map<string, string> a;
 //  map        ：
 //       map ， pair        
 a.insert(pair<string, string>("peach", "  "));
 //       map ， make_pair        
 a.insert(make_pair("banan", "  "));
 
 //   operator[] map     
 /*
 operator[]    ：
         ，    insert()          map 
   key    ，    ，insert     key        
   key   ，    ，insert                 
 operator[]     insert        value  
 */
 //    map ，    ，  value   ， “  ”        ，
 m["apple"] = "  ";
 // key       
 //m.at("waterme") = "   ";
 cout << m.size() << endl;
 //        map    ，        key     
 for (auto& e : m)
 cout << e.first << "--->" << e.second << endl;
 cout << endl;
 // map     key      ，  key       
 auto ret = m.insert(make_pair("peach", "  "));
 if (ret.second)
 cout << "  map ,     " << endl;
 else
 cout << "   peach       ：" << ret.first->first << "--->" <<
ret.first->second <<"     "<< endl;
 //   key "apple"   
 m.erase("apple");
 if (1 == m.count("apple"))
 cout << "apple  " << endl;
 else
 cout << "apple   " << endl; }

지도 총화

map 의 요 소 는 키 쌍

입 니 다.

map 의 key 는 유일한 것 이 며 수정 할 수 없습니다

기본 값 은 키 를 작은 방식 으로 비교 합 니 다

map 의 요 소 를 교체 기 로 옮 겨 다 니 면 질서 있 는 서열

을 얻 을 수 있 습 니 다.

맵 의 밑바닥 은 균형 검색 트 리 (붉 은 검 은 나무) 로 검색 효율 이 비교적 높다

지원 [] 연산 자, operator [] 에서 실제 삽입 검색 을 합 니 다.

set

set 는 일정한 순서에 따라 원 소 를 저장 하 는 용기 입 니 다.

set 에서 요소 의 value 도 이 를 표시 하고 (value 는 key 이 며 유형 은 T) 모든 value 가 유일 해 야 합 니 다.set 의 요 소 는 용기 에서 수정 할 수 없 지만 용기 에서 삽입 하거나 삭제 할 수 있 습 니 다.

내부 에서 set 중의 요 소 는 내부 비교 대상 (유형 비교) 이 지시 하 는 특정한 엄격 하고 약 한 정렬 준칙 에 따라 순 서 를 매 긴 다.

set 용 기 는 키 를 통 해 단일 원소 에 접근 하 는 속도 가 보통 unordered 보다set 용 기 는 느 리 지만 하위 집합 을 순서대로 직접 교체 할 수 있 습 니 다.

set 는 밑바닥 에서 두 갈래 로 나무 (붉 은 검 은 나무) 를 검색 하여 이 루어 졌 다.

set 템 플 릿 매개 변수

template <class T,//T: set        ，           。
class compare = less<T>//Compare：set            
class Alloc = alloctor<T>//Alloc：set          ，  STL          
>class set;

set 의 구조
함수 선언
기능 소개
set (const Compare& comp = Compare(), const Allocator& = Allocator() );
빈 set
–
–
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );
[first, last) 구간 의 원소 구조 set 로
–
–
set ( const set& x);
set 의 복사 구조
set 의 교체 기
함수 선언
기능 구조
iterator begin()
set 의 시작 위치 요소 의 교체 기 를 되 돌려 줍 니 다.
–
–
iterator end()
set 의 마지막 요소 뒤의 교체 기 를 되 돌려 줍 니 다.
–
–
const_iterator cbegin() const
const 는 set 의 시작 위치 요 소 를 되 돌려 주 는 const 교체 기 입 니 다.
–
–
const_iterator cend() const
const 는 set 의 마지막 요소 뒤의 const 교체 기 를 되 돌려 줍 니 다.
–
–
reverse_iterator rbegin()
set 첫 번 째 요소 의 역방향 교체 기, 즉 end 를 되 돌려 줍 니 다.
–
–
reverse_iterator rend()
set 마지막 요소 의 다음 위 치 를 되 돌려 주 는 역방향 교체 기, 즉 rbegin
–
–
const_reverse_iterator crbegin() cons t
const 는 set 첫 번 째 요소 의 역방향 const 교체 기, cend 를 되 돌려 줍 니 다.
–
–
const_reverse_iterator crend() const
set 마지막 요소 의 다음 위 치 를 되 돌려 주 는 역방향 const 교체 기, 즉 crbegin
set 용량
함수 선언
기능 구조
bool empty ( ) const
set 가 비어 있 는 지 확인 하고 true 로 돌아 갑 니 다. 그렇지 않 으 면 true 로 돌아 갑 니 다.
–
–
size_type size() const
set 에서 유효 요소 의 개 수 를 되 돌려 줍 니 다.
set 실례,

#include
#include 
void TestSet()
{
 //    array      set
 int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
 set<int> s(array, array+sizeof(array)/sizeof(array));
 cout << s.size() << endl;
 //     set    ，          ：set   
 for (auto& e : s)
 cout << e << " ";
 cout << endl;
 //          set    
 for (auto it = s.rbegin(); it != s.rend(); ++it)
 cout << *it << " ";
 cout << endl;
 // set   3        
 cout << s.count(3) << endl;
  }

맵 과 set 는 모두 C + + 의 관련 용기 이 며, 그 밑 에 있 는 구현 은 모두 레 드 블랙 트 리 (RB - Tree) 입 니 다. 맵 과 set 가 열 린 각종 조작 인터페이스 로 인해 RB - tree 도 제공 되 기 때문에 거의 모든 맵 과 set 의 조작 행 위 는 RB - tree 의 조작 행위 일 뿐 입 니 다.
map 와 set 의 차이
(1) map 의 요 소 는 key - value (키워드 - 값) 입 니 다. 키 워드 는 색인 | 역할 을 하고 값 은 색인 과 연 결 된 데 이 터 를 표시 합 니 다. set 와 상대 적 으로 키워드 의 간단 한 집합 입 니 다. set 에 있 는 모든 요 소 는 - 하나의 키워드 만 포함 합 니 다. (2)set 의 교체 기 는 const 입 니 다. 요소 의 값 을 수정 할 수 없습니다. map 는 value 를 수정 할 수 있 지만 key 를 수정 할 수 없습니다. 그 이 유 는 map 와 set 는 키워드 정렬 에 따라 질서 성 을 확보 하기 때 문 입 니 다. key 를 수정 할 수 있다 면 먼저 이 키 를 삭제 하고 균형 을 조절 한 다음 에 수 정 된 키 값 을 삽입 하여 균형 을 조절 해 야 하기 때 문 입 니 다. 그러면 map 와 set 를 심각하게 파괴 합 니 다.의 구조 로 인해 iterator 가 실 효 됩 니 다. 변경 전 위 치 를 가리 키 는 지, 변 경 된 위 치 를 가리 키 는 지 모 르 겠 습 니 다. 따라서 STL 에 서 는 set 의 교체 기 를 const 로 설정 하고 교체 기의 값 을 수정 할 수 없습니다. map 의 교체 기 는 key 값 을 수정 할 수 없고 value 값 을 수정 할 수 있 습 니 다. (3)| map 는 아래 표 시 를 지원 합 니 다. set 는 아래 표 시 를 지원 하지 않 습 니 다. map 는 key 로 아래 표 시 를 할 수 있 습 니 다. map 의 아래 표 시 된 연산 자 [] 는 키 코드 를 아래 표 시 를 통 해 찾 을 수 있 습 니 다. 키 코드 가 존재 하지 않 으 면 이 키 코드 와 mapped type 형식의 기본 값 을 가 진 요 소 를 map 에 삽입 할 수 있 습 니 다. 따라서 아래 표 시 된 연산 자 []map 응용 프로그램 에 서 는 신중하게 사용 해 야 합 니 다. const map 는 사용 할 수 없습니다. 요소 삽입 을 원 하지 않 을 때 도 사용 하지 말 아야 합 니 다. mapped type 형식 은 기본 값 이 없어 도 사용 하지 말 아야 합 니 다. find 가 수 요 를 해결 할 수 있다 면 가능 한 find 를 사용 하 십시오.