연관 용기

이 기사는 위키피디아의 품질 기준을 충족시키기 위해 정리가 필요할 수 있다. 정리 사유가 지정되지 않았다. 가능한 경우 이 문서를 개선하는 데 도움을 주십시오.(2011년 12월) (이 템플리트 메시지를 제거하는 방법 및 시기 알아보기)

컴퓨팅에서 연관 용기는 순서 연관 배열을 구현하는 C++ 프로그래밍 언어의 표준 라이브러리에 있는 클래스 템플릿 그룹을 가리킨다.^[1]템플릿으로서, 그것들은 정수나 사용자 정의 클래스와 같은 임의 요소를 저장하는 데 사용될 수 있다.C++ 표준의 현재 개정판에는 다음과 같은 용기가 정의되어 있다.set,map,multiset,multimap각각의 컨테이너는 그 요소들에 놓여진 제약조건에 따라서만 다르다.

연관 용기는 C++ 표준 라이브러리에 있는 정렬되지 않은 연관 용기와 유사하며, 유일한 차이점은 이름에서 알 수 있듯이 정렬되지 않은 연관 용기는 요소를 정렬하지 않는다는 것이다.

디자인

특성.

• 키 고유성: inmap그리고set각 키는 고유해야 한다. multimap그리고multiset이 제한은 없다.
• 요소 구성: 위치map그리고multimap각 요소는 키와 매핑된 값으로 구성된다.인set그리고multiset각 요소는 키, 매핑된 값이 없다.
• 요소 순서: 요소가 엄격한 약한 순서를^[1] 따르십시오.

연관 용기는 위치에 따라 요소에 더 효율적으로 접근하는 시퀀스 용기와 달리 키로 요소에 접근하는데 특히 효율적이도록 설계된다.^[1]연관 용기는 원소가 삽입, 삭제 및 그 안에 있는지 테스트하는 작업을 로그 시간 – O(log n)에 수행할 수 있도록 보장된다.이와 같이, 그것들은 일반적으로 자가 균형 이진 검색 트리를 사용하여 구현되며 양방향 반복을 지원한다.반복기와 참조는 삭제된 요소에 대한 반복기와 참조를 제외하고 삽입 및 지우기 작업에 의해 무효화되지 않는다.연관 용기의 정의 특성은 요소들이 정렬된 오름차순과 같이 미리 정의된 순서로 삽입된다는 것이다.

연관 용기는 지도와 세트라는 두 개의 하위 집합으로 분류될 수 있다.사전이라고도 하는 지도는 키/값 쌍으로 구성되어 있다.키는 시퀀스를 주문하기 위해 사용되며, 그 값은 어떻게든 그 키와 연관되어 있다.예를 들어, 지도에는 텍스트의 모든 고유 단어를 나타내는 키와 텍스트에 단어가 나타나는 횟수를 나타내는 값이 포함될 수 있다.한 세트는 단순히 독특한 원소의 오름차순 용기에 불과하다.

맵과 세트 모두 하나의 키 또는 요소 인스턴스만 용기에 삽입할 수 있다.요소의 여러 인스턴스가 필요한 경우 멀티맵 또는 멀티셋을 사용하십시오.

지도와 세트 모두 양방향 반복기를 지원한다.반복기에 대한 자세한 내용은 반복기를 참조하십시오.

공식적으로 STL 표준의 일부는 아니지만, hash_map과 hash_set은 일반적으로 검색 시간을 개선하기 위해 사용된다.이 컨테이너들은 각각의 테이블 항목이 양방향으로 연결된 요소 목록을 포함하는 해시 테이블로 요소를 저장한다.가장 빠른 검색 시간을 보장하려면 요소의 해싱 알고리즘이 고르게 분산된 해시 값을 반환하는지 확인하십시오.

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다(2011년 12월)

퍼포먼스

연관 용기에 적용할 수 있는 작업의 점증적 복잡성은 다음과 같다.

함수 개요

컨테이너는 예를 들어 컨테이너의 이름을 따서 명명된 헤더에 정의된다.set헤더에 정의됨<set> . 모든 컨테이너는 컨테이너 개념의 요구 조건을 충족하며, 이는 그들이begin(),end(),size(),max_size(),empty()그리고swap()방법들

사용법

다음 코드는 다음을 사용하는 방법을 보여준다.map<string, int>단어의 발생 횟수를 세다.단어를 키로, 카운트를 값으로 사용한다.

#include <아이오스트림> #include <끈> #include <지도>  인트로 본래의() {     찌꺼기::지도를 그리다<찌꺼기::끈을 매다, 인트로> 단어 수;     찌꺼기::끈을 매다 s;      하는 동안에 (찌꺼기::씨네 >> s && s != "끝")         ++단어 수[s];      하는 동안에 (찌꺼기::씨네 >> s && s != "끝")         찌꺼기::뻐드렁니가 나다 << s << ' ' << 단어 수[s] << '\n'; } 

실행될 때 사용자는 먼저 공백으로 구분된 일련의 단어와 입력의 끝을 나타내는 "끝" 단어를 입력한다. 그런 다음, 사용자는 단어를 입력하여 각 단어가 이전 시리즈에서 몇 번이나 발생했는지 쿼리할 수 있다.

위의 예는 키와 연관된 객체가 없는 경우 (기본 생성자를 사용하여) 연산자 []가 지도에 새 객체를 삽입하는 것도 보여준다.그래서 정수형은 제로 초기화, 문자열은 빈 문자열 등으로 초기화한다.

다음 예에서는 삽입 기능을 사용하여 요소를 지도에 삽입하고 지도 반복기와 찾기 기능을 사용하여 키를 검색하는 방법을 보여 준다.

#include <아이오스트림> #include <지도> #include <<utility>>// make_make  인트로 본래의() {     타이피프 찌꺼기::지도를 그리다<마를 뜨다, 인트로> 맵타입;     맵타입 my_map;      // 삽입 기능을 사용하여 요소 삽입     my_map.삽입하다(찌꺼기::짝을 짓다<마를 뜨다, 인트로>('a', 1));     my_map.삽입하다(찌꺼기::짝을 짓다<마를 뜨다, 인트로>('b', 2));     my_map.삽입하다(찌꺼기::짝을 짓다<마를 뜨다, 인트로>('c', 3));     my_map.삽입하다(맵타입::value_type('d', 4)); // 모든 표준 컨테이너가 이 형식 정의를 제공함     my_map.삽입하다(찌꺼기::make_make('e', 5));      // 유틸리티 함수 make_make도 사용할 수 있음     my_map.삽입하다({'f', 6});                    // C++11 이니셜라이저 목록 사용          //map 키는 자동으로 낮은 키에서 높은 키로 정렬된다.      //그래서 my_map.시작은 먼저 삽입된 키가 아닌 가장 낮은 키 값을 가리킨다.     맵타입::반복기 반복하다 = my_map.시작되다();      // 지우기 기능을 사용하여 첫 번째 요소 지우기     my_map.지우다(반복하다);      // 지도 크기 출력     찌꺼기::뻐드렁니가 나다 << "my_map 크기: " << my_map.사이즈를 맞추다() << '\n';      찌꺼기::뻐드렁니가 나다 << " 검색할 키를 입력하십시오. ";     마를 뜨다 c;     찌꺼기::씨네 >> c;      // find가 발견되면 일치하는 요소로 리터레이터가 반환됨     // 또는 키를 찾을 수 없는 경우 지도 끝까지     반복하다 = my_map.찾아내다(c);     만일 (반복하다 != my_map.종지부를 찍다() )          찌꺼기::뻐드렁니가 나다 << "값은: " << 반복하다->둘째 << '\n';     다른         찌꺼기::뻐드렁니가 나다 << "키가 my_map에 없음" << '\n';      // 지도에서 항목 지우기     my_map.분명한(); } 

위의 예에서는 삽입 기능을 사용하여 6개의 요소를 입력한 다음 첫 번째 요소를 삭제한다.그러면 지도 크기가 출력된다.다음으로, 사용자에게 검색할 키를 입력하라는 메시지가 표시된다.반복기를 사용하여 찾기 함수는 지정된 키로 요소를 검색한다.키를 찾으면 프로그램이 요소의 값을 인쇄한다.찾지 못할 경우 지도 끝의 반복기가 반환되고 키를 찾을 수 없는 상태로 출력된다.마침내 나무의 모든 원소가 지워진다.

반복기

지도는 컨테이너의 특정 요소를 가리키기 위해 반복기를 사용할 수 있다.반복기는 요소의 키 값과 매핑된 값 모두에 액세스할 수 있다.^[1]

지도를 그리다<키,T>::반복기 그럭저럭; // 지도 반복자를 선언함 그럭저럭->맨 처음의;               // 키 값 그럭저럭->둘째;              // 매핑된 값 (*그럭저럭);                   // "element value" 유형: pair(pair)<const 키,T> 

다음은 반복기를 사용하여 모든 키와 값을 표시하기 위해 지도를 반복하는 예:

#include <아이오스트림> #include <끈> #include <지도>  인트로 본래의() {     찌꺼기::지도를 그리다 <찌꺼기::끈을 매다, 인트로> 자료{      { "밥 점수", 10 },      { "Martys 점수", 15 },      { "메메츠 점수", 34 },      { "로키스 점수", 22 },      { "로키스 점수", 23 } /*키들이 동일하므로 22를 덮어쓴다 */     };          // 지도를 반복해서 모든 키/값 쌍을 출력한다.     을 위해 (경시하다 자동차로& 요소 : 자료)     {         찌꺼기::뻐드렁니가 나다 << "누구(키 = 먼저):" << 요소.맨 처음의;         찌꺼기::뻐드렁니가 나다 << " 점수(값 = 초):" << 요소.둘째 << '\n';     }      돌아오다 0; } 

GCC 컴파일러에서 위의 샘플을 컴파일하려면 특정 표준 선택 플래그를 사용해야 한다.

g++ -찌꺼기=c++11 출처.cpp -o src 

이렇게 하면 전체 맵의 키와 값이 키별로 정렬되어 출력된다.

참고 항목

• 컨테이너(추상 데이터 유형)
• 표준 템플릿 라이브러리#컨테이너

참조