hash_map 클래스

아티클
06/09/2015

참고

이 API는 사용되지 않습니다.unordered_map 클래스를 대신 사용하는 것이 좋습니다.

고유하며 데이터 값과 연합된 정렬 키를 가진 쌍으로 된 각 요소의 컬렉션으로부터 데이터를 빠르게 저장하고 검색합니다.

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

매개 변수

Key
hash_map에 저장되는 키 데이터 형식입니다.
Type
hash_map에 저장되는 요소 데이터 형식입니다.
Traits
클래스 비교 중 하나인 두 함수 개체를 포함하는 형식은, 상대적인 순서를 결정하기 위한 정렬 키와 size_t 형식의 부호 없는 정수인 요소인 매핑 키 값에 대한 단항 술어인 해쉬 함수를 값으로 갖는 두 요소를 비교할 수 있게 합니다. 이 인수는 선택적이며, hash_compare<Key, less<Key>>가 기본값입니다.
Allocator
hash_map의 할당 및 할당 취소에 대한 세부 정보를 캡슐화하는 저장된 할당기 개체를 나타내는 형식입니다. 이 인수는 선택적 요소이며 기본값은 allocator<pair<constKey, Type>>입니다.

설명

hash_map은:

연관된 키 값을 기준으로 하며 요소 값의 효율적인 검색을 지원하는 가변 크기 컨테이너 결합형 컨테이너입니다.
해당 요소에 액세스할 수 있는 양방향 반복기를 제공하기 때문에 되돌릴 수 있습니다.
해쉬되었습니다. 해당 요소는 버킷으로 요소의 키 값에 적용되는 해쉬 함수의 값을 기준으로 그룹화되어 있습니다.
각각의 요소가 반드시 고유한 키를 가지고 있어야 한다는 점에서 고유성을 갖고 있습니다.
요소의 데이터 값은 키 값과 구별되기 때문에 쌍 결합형 컨테이너입니다.
템플릿 클래스입니다. 기능적으로 제네릭과 요소나 키로 포함하고 있는 특정한 데이터 형식에 대한 독립성을 제공합니다. 요소에 사용될 데이터 형식과 키는 대신 비교 함수와 할당자와 함께 클래스 템플릿에서 매개 변수로 지정됩니다.

정렬된 상태에서 해싱의 주된 잇점은 향상된 효율성입니다; 컨테이너의 정렬 기술이 요소의 개수를 진수로 하는 로그값에 비례하는 시간이 소요되는 반면, 성공적인 해싱은 삽입, 삭제 및 찾기를 평균적으로 상수 시간에 수행합니다. hash_map 요소의 값 (연관된 키 값이 아니라) 은 직접적으로 변경될 수 있습니다. 대신, 이전 요소와 관련된 키 값은 삭제되어야 하며, 삽입된 새 요소와 새 키 값이 연결되어야 합니다.

컨테이너 형식의 선택은 응용 프로그램에 의해 검색과 삽입이 필요한 일반적인 형식에 기초해야 합니다. 해쉬된 연관된 컨테이너들은 조회, 삽입 및 제거 작업에 최적화되어 있습니다. 명시적으로 이러한 작업을 지원하는 멤버 함수는 평균적으로 컨테이너의 요소 갯수에 의존적이지 않고 상수 시간에 수행하는 잘 설계된 해쉬 함수와 함께 사용하면 효율적입니다. 잘 설계된 해쉬 함수는 해쉬 값을 균일한 분포시키며 다른 키 값에 동일한 해쉬 값이 매핑되는 경우 일어나는 충돌의 횟수를 최소화합니다. 가능한 최악의 해쉬 함수를 사용하며, 최악의 경우에 작업의 수는 시퀀스 내의 요소의 숫자에 비례합니다. (선형 시간)

응용 프로그램에 의해 키과 값들을 연결되는 조건이 만족되면 hash_map은 결합형 컨테이너여야 합니다. 이 구조체의 형식에 대한 모델은 키워드가 연결된 문자열 값인 정의와 함께 고유하게 나타나는 정렬된 목록입니다. 만약, 단어가 하나 이상의 올바른 정의를 가진 경우, 따라서 키가 고유하지 않은 경우는 hash_multimap을 컨테이너로 선택할 수 있습니다. 반면에, 단어의 목록만을 저장하는 경우에는 hash_set이 올바른 컨테이너가 될 것입니다. 여러 번 중복하여 단어가 등장하는 것을 허용하는 경우는, hash_multiset이 적절한 컨테이너 구조입니다.

hash_map은 value_compare 클래스의 저장된 해쉬 Traits 개체를 호출함으로써 시퀀스 정렬을 제어합니다. 이 저장된 개체는 멤버 함수 key_comp를 호출하여 액세스할 수 있습니다. 함수 개체는 hash_compare<Key, less<Key>> 클래스의 개체와 동일하게 동작해야 합니다. 구체적으로는, 모든 Key형식의 Key 값, Traits(Key)의 호출이 size_t 형식의 값 분포를 산출

일반적으로, 요소는 이 순서를 설정하기 위해 비교 가능한 값보다 작을 필요가 있습니다: 제공된 어떤 두 요소에서도, 두 요소가 동일하거나(어떤 것도 다른 것보다 작지 않음) 하나가 다른 것보다 작음을 정할 수 있습니다. 그러면 동일하지 않은 요소 사이에 정렬이 수행됩니다. 더 기술적인 설명으로, 비교 함수는 표준 수학 의미로 엄밀한 약한 순서를 포함하는 이진 술어입니다. 이진 술어 f(x y)는 두 인수 개체 x 및 y를 가지는 함수 개체이며, true 또는 false 값을 반환합니다. 이진 술어가 비재귀적, 비대칭 및 타동적이며, 동등성이 타동적일 경우, f(x,y) 및 f(y,x)가 모두 false인 경우 두 개체 x 및 y는 동등한 것으로 정의되며, hash_map에 부과된 순서는 엄밀한 약한 순서입니다. 더 강력한 키 사이의 상등 조건이 동등 조건을 대체하는 경우, 순서는 전체 (모든 요소들이 서로에 관련하여 정렬됨을 의미) 가 되며, 키의 일치는 서로 식별할 수 없게 됩니다.

제어되는 시퀀스에 있는 요소의 실제 순서는 해시 함수, 정렬 함수 및 컨테이너 개체에 저장 된 해시 테이블의 현재 크기에 따라 달라집니다. 해쉬 테이블의 현재 크기를 지정할 수 없으므로, 일반적으로 제어되는 시퀀스에서 요소의 순서를 예측할 수 없습니다. 요소를 삽입하는 것은 어떤 반복기도 무효화하지 않으며, 요소를 제거하는 것은 제거된 요소를 명확히 가리키고 있는 반복기만을 무효화합니다.

hash_map 클래스에 의해 제공되는 반복기는 양방향 반복기지만, 삽입 및 맵 클래스 멤버 함수는 양방향 반복기의 클래스에 의해 보장되는 것보다 기능적 요구사항이 더 적은 약한 입력 반복기를 템플릿 매개 변수로써 취하는 버전들을 가집니다. 다른 반복기 개념은 그들의 기능을 정제화하여 연관된 가족을 구성합니다. 각 반복기 개념은 고유한 요구 사항과 반복기의 형식에 의해 제공되는 요구 사항의 가정에 제약을 받는 알고리즘을 가집니다. 일부 개체를 참조하려면 입력 반복기가 역참조될 수 있으며, 이는 시퀀스 내의 다음 반복기를 증가시킬 수 있습니다. 이것은 최소한의 기능 모음이지만, 클래스 멤버 함수의 문맥에서 [First, Last) 반복기의 범위에 대해 의미있는 대화를 하기에 충분합니다.

Visual C++.NET 2003에서, <hash_map> 및 <hash_set> 헤더 파일의 멤버는 더 이상 std 네임스페이스에 존재하지 않습니다. 대신 stdext 네임스페이스로 이동되었습니다. 자세한 내용은 stdext 네임스페이스를 참조하십시오.

생성자

hash_map

비어 있거나 모든 복사본이거나 또는 일부 다른 hash_map 부분인 hash_map을 생성 합니다.

형식 정의

allocator_type	형식은 hash_map 개체를 위한 allocator 클래스를 나타냅니다.
const_iterator	hash_map에 있는 const 요소를 읽을 수 있는 양방향 반복기를 제공하는 형식
const_pointer	hash_map에서 const 요소에 대한 포인터를 제공하는 형식입니다.
const_reference	const 작업을 읽고 수행하기 위해 hash_map에 저장된 const 요소에 대한 참조를 제공하는 형식입니다.
const_reverse_iterator	hash_map에 있는 모든 const 요소를 읽을 수 있는 양방향 반복기를 제공하는 형식
difference_type	부호 있는 정수 형식은 반복기가 가리키는 요소 사이의 범위에 있는 hash_map의 요소의 갯수를 표현하는 데에 사용될 수 있습니다.
반복기	hash_map에 있는 모든 요소를 읽거나 수정할 수 있는 양방향 반복기를 제공하는 형식입니다.
key_compare	hash_map의 두 요소간 상대적 순서를 결정하는 두 정렬 키를 비교할 수 있는 함수 개체를 제공하는 형식입니다.
key_type	hash_map 의 각 요소를 구성하는 정렬 키 개체를 설명하는 형식입니다.
mapped_type	다음 hash_map 내에 저장된 데이터 형식을 나타내는 형식입니다.
포인터	다음 hash_map 내의 요소에 대한 포인터를 제공하는 형식입니다.
reference	다음 hash_map 내에 저장된 요소에 대한 참조를 제공하는 형식입니다.
reverse_iterator	예약된 hash_map에 있는 요소를 읽거나 수정할 수 있는 양방향 반복기를 제공하는 형식입니다.
size_type	부호 없는 정수 형식은 hash_map의 요소 갯수를 표현할 수 있습니다.
value_type	hash_map의 상대적 순서를 결정하는 정렬 키로써의 두 요소를 비교할 수 있는 함수 개체를 제공하는 형식입니다.

멤버 함수

hash_map::at	hash_map 에서 지정된 키 값이 있는 요소를 찾습니다.
begin	hash_map에서 첫 번째 요소를 주소 지정하는 반복기를 반환합니다.
hash_map::cbegin	hash_map에서 첫 번째 요소를 주소 지정하는 상수 반복기를 반환합니다.
hash_map::cend	hash_map에서 마지막 요소 뒤에 나오는 위치를 주소 지정하는 상수 반복기를 반환합니다.
clear	다음 hash_map의 모든 요소를 지웁니다.
count	hash_map 에서 키가 매개 변수에 지정된 키와 일치하는 요소의 갯수를 반환합니다.
hash_map::crbegin	예약된 hash_map에서 첫 번째 요소를 주소 지정하는 상수 반복기를 반환합니다.
hash_map::crend	예약된 hash_map에서 마지막 요소 뒤에 나오는 위치를 주소 지정하는 상수 반복기를 반환합니다.
hash_map::emplace	hash_map에 생성된 요소를 삽입합니다.
hash_map::emplace_hint	배치 힌트를 사용하여 hash_map에 생성된 요소를 삽입합니다.
empty	hash_map이 비어 있는지를 테스트합니다.
end	hash_map에서 마지막 요소 뒤에 나오는 위치를 주소 지정하는 반복기를 반환합니다.
equal_range	지정된 키보다 더 큰 키를 가진 hash_map의 첫 번째 요소와 지정된 키보다 더 크거나 같은 키를 가진 hash_map의 첫 번째 요소에 반복기의 쌍을 각각 반환합니다.
지우기	지정된 위치의 문자열에서부터 hash_map 내의 요소 또는 요소 범위를 제거합니다.
find	지정된 키와 같은 키를 가진 hash_map 내 요소의 위치를 가리키는 반복기를 반환합니다.
get_allocator	hash_map을 생성하는 데 사용되는 allocator 개체의 복사본을 반환합니다.
insert	hash_map에 요소 또는 요소의 범위를 삽입합니다.
key_comp	hash_map에서 지정된 키보다 같거나 큰 키 값을 가진 첫 번째 요소에 반복기를 반환합니다.
lower_bound	hash_map에서 지정된 키보다 같거나 큰 키 값을 가진 첫 번째 요소에 반복기를 반환합니다.
max_size	hash_map의 최대 길이를 반환합니다.
rbegin	예약된 hash_map에서 첫 번째 요소를 참조하는 반복기를 반환합니다.
rend	예약된 hash_map에서 마지막 요소 뒤에 나오는 위치를 주소 지정하는 반복기를 반환합니다.
size	다음 hash_map내에 있는 요소 수를 반환합니다.
스왑	두 hash_map의 요소를 교환합니다.
upper_bound	hash_map에서 지정된 키보다 큰 키 값을 가진 첫 번째 요소에 반복기를 반환합니다.
value_comp	hash_map에서 요소 값을 정렬하기 위해 사용되는 비교 개체의 복사본을 검색합니다.

연산자

operator[]	지정된 키 값을 사용하여 hash_map에 요소를 삽입합니다.
hash_map::operator=	다른 hash_map 의 복사본이 hash_map 의 요소를 대체합니다.