C++ named requirements: AssociativeContainer
AssociativeContainer 는 키를 기반으로 한 객체의 빠른 조회를 제공하는 정렬된 Container 입니다.
연관 컨테이너는 각 키에 대해 최대 하나의 요소만 포함할 수 있는 경우 unique keys 를 지원합니다. 그렇지 않은 경우 equivalent keys 를 지원합니다.
목차 |
요구사항
범례 |
|
X
|
연관 컨테이너 클래스 |
T
|
X
의 요소 타입
|
A
|
X의 할당자 타입:
X::allocator_type
가 존재하는 경우 해당 타입, 그렇지 않으면
std::
allocator
<
X
::
value_type
>
|
| a |
X
타입의 값
|
| a2 |
Y
타입의 값으로, 해당
노드 핸들
이
X
와 호환되는
|
| b |
X
타입 또는
const
X
타입의 값
|
| u | 선언 중인 변수의 이름 |
| a_uniq |
X
타입의 값으로,
X
가 고유 키를 지원하는 경우
|
| a_eq |
X
타입의 값으로,
X
가 동등 키를 지원하는 경우
|
| a_tran |
X
타입의 값 또는
const
X
타입의 값 (단,
X::key_compare::is_transparent
타입이 존재할 경우)
|
| i , j |
LegacyInputIterator
s
를 참조하는 이터레이터들로,
X::value_type
으로 암시적으로 변환 가능한 요소들을 가리킵니다.
|
[
i
,
j
)
|
유효한 범위 |
|
rg
(C++23부터) |
R
타입의 값으로
container-compatible-range
<value_type>
를 모델링함
|
| p | a 에 대한 유효한 상수 반복자 |
| q | a 에 대한 유효한 역참조 가능한 상수 반복자 |
| r | 유효한 역참조 가능 반복자 a |
| q1 , q2 | a 의 유효한 const 반복자 범위 |
| il | std:: initializer_list < X :: value_type > 타입의 객체 |
| t |
X::value_type
타입의 값
|
| k |
X::key_type
타입의 값
|
| c |
X::key_compare
타입 또는
const
X
::
key_compare
의 값
|
| kl | a 가 c ( x, kl ) 에 따라 분할되는 값이며, 여기서 x 는 e 의 키 값이고 e 는 a 에 속함 |
| ku | a 가 ! c ( ku, x ) 에 대해 분할되는 값으로, x 는 e 의 키 값이고 e 는 a 에 포함됨 |
| ke | a 가 c ( x, ke ) 와 ! c ( ke, x ) 에 대해 분할되는 값으로, c ( x, ke ) 가 ! c ( ke, x ) 를 의미하며, x 는 e 의 키 값이고 e 는 a 에 포함됨 |
|
kx
(C++23부터) |
다음 조건을 만족하는 값:
|
| m |
A
로 변환 가능한 타입의 할당자
|
| nh |
X::node_type
타입의 비-상수 rvalue
|
타입
X
가 다음 조건을 만족하면
AssociativeContainer
를 만족합니다
-
타입
X는 Container (until C++11) AllocatorAwareContainer (since C++11) 를 만족합니다, -
Key와Key요소들에 대한 strict weak ordering 을 유도하는 순서 관계Compare를 매개변수로 가지며,-
추가적으로,
std::map
과
std::multimap
은 임의의
mapped type
T를Key와 연관시킵니다. -
Compare타입의 객체는X타입 컨테이너의 comparison object 라고 불립니다.
-
추가적으로,
std::map
과
std::multimap
은 임의의
mapped type
- 모든 연관 컨테이너에 대해 다음 표현식들은 유효해야 하며 지정된 효과를 가져야 합니다:
타입
| 이름 | 유형 | 요구 사항 |
|---|---|---|
key_type
|
Key
|
|
mapped_type
|
T
(
std::map
및
std::multimap
전용)
|
|
value_type
|
|
Erasable
from
X
|
key_compare
|
Compare
|
CopyConstructible |
value_compare
|
|
BinaryPredicate |
node_type
|
node-handle 클래스 템플릿
의 특수화로, 공개 중첩 타입들이
X
의 해당 타입들과 동일한 타입들임.
|
멤버 함수와 연산자
| 표현식 | 결과 | 사전 조건 | 효과 | 반환값 | 복잡도 |
|---|---|---|---|---|---|
| X ( c ) | 빈 컨테이너를 생성합니다. c 의 복사본을 비교 객체로 사용합니다 | 상수 시간 | |||
|
X u
=
X
(
)
;
X u ; |
key_compare
가
DefaultConstructible
요구사항을 충족함
|
빈 컨테이너를 생성합니다. Compare ( ) 를 비교 객체로 사용합니다 | 상수 시간 | ||
| X ( i, j, c ) |
value_type
이
EmplaceConstructible
로
X
에
*
i
로부터 생성 가능해야 함
|
빈 컨테이너를 생성하고 범위
[
i
,
j
)
의 요소들을 삽입함;
c
를 비교 객체로 사용함
|
N·log
(
N
)
일반적으로, 여기서
N
은
std::
distance
(
i, j
)
의 값을 가짐;
[
i
,
j
)
가
value_comp
(
)
에 대해 정렬된 경우 선형 시간
|
||
| X ( i, j ) |
key_compare
가
DefaultConstructible
요구사항을 충족합니다.
value_type
이
EmplaceConstructible
되어
X
에
*
i
로부터 생성 가능합니다.
|
빈 컨테이너를 생성하고 범위
[
i
,
j
)
의 요소들을 삽입합니다;
Compare
(
)
를 비교 객체로 사용합니다.
|
|||
|
X
(
from_range, rg, c
)
(C++23부터) |
value_type
이
EmplaceConstructible
로
X
에
*
ranges::
begin
(
rg
)
로부터 생성 가능해야 함
|
빈 컨테이너를 생성하고 rg 의 각 요소를 삽입합니다. c 를 비교 객체로 사용합니다. |
N·log
(
N
)
의 일반적인 시간 복잡도, 여기서
N
은
ranges::
distance
(
rg
)
의 값을 가짐;
rg
가
value_comp
(
)
에 대해 정렬된 경우 선형 시간
|
||
|
X
(
from_range, rg
)
(C++23부터) |
key_compare
가
DefaultConstructible
요구사항을 충족합니다.
value_type
은
EmplaceConstructible
되어
X
에
*
ranges::
begin
(
rg
)
로부터 생성 가능해야 합니다.
|
빈 컨테이너를 생성하고 rg 의 각 요소를 삽입합니다. Compare ( ) 를 비교 객체로 사용합니다. | |||
| X ( il, c ) | X ( il. begin ( ) , il. end ( ) , c ) | ||||
| X ( il ) | X ( il. begin ( ) , il. end ( ) ) | ||||
| a = il | X & |
value_type
이
CopyInsertable
되어
X
에 삽입 가능하고
CopyAssignable
이어야 함
|
범위
[
il.
begin
(
)
,
il.
end
(
)
)
를
a
에 할당합니다.
a
의 모든 기존 요소들은 할당되거나 파괴됨
|
N·log
(
N
)
(일반적인 경우), 여기서
N
의 값은
il.
size
(
)
+
a.
size
(
)
임;
[
il.
begin
(
)
,
il.
end
(
)
)
가
value_comp
(
)
에 대해 정렬된 경우 선형 시간
|
|
| b. key_comp ( ) |
X::key_compare
|
b 가 생성될 때 사용된 비교 객체 | 상수 | ||
| b. value_comp ( ) |
X::value_compare
|
비교 객체로부터 생성된
value_compare
객체
|
상수 | ||
| a_uniq. emplace ( args ) |
std::
pair
<
iterator, bool > |
value_type
이
EmplaceConstructible
요구사항을 만족하며
X
에
args
로부터 생성 가능한 경우
|
value_type
객체
t
를
std::
forward
<
Args
>
(
args
)
...
로 생성하여 컨테이너에
t
의 키와 동등한 키를 가진 요소가 없는 경우에만 삽입합니다
|
반환된 pair의 bool 구성 요소는 삽입이 발생한 경우에만 true 이며, pair의 반복자 구성 요소는 t 의 키와 동등한 키를 가진 요소를 가리킵니다 | 로그 시간 |
| a_eq. emplace ( args ) |
iterator
|
value_type
이
EmplaceConstructible
요구사항을 만족하며
X
에
args
로부터 생성 가능해야 함
|
std::
forward
<
Args
>
(
args
)
...
로 생성된
t
객체를
value_type
으로 삽입합니다.
a_eq
에
t
와 동등한 요소들을 포함하는 범위가 존재할 경우,
t
는 해당 범위의 끝에 삽입됩니다
|
새로 삽입된 요소를 가리키는 반복자 | 로그 시간 복잡도 |
| a. emplace_hint ( p, args ) |
iterator
|
다음 표현식과 동등함
a.
emplace
(
|
새로 삽입된 요소와 동등한 키를 가진 요소를 가리키는 반복자 | 일반적으로 로그 시간이지만, 요소가 p 바로 앞에 삽입되는 경우 분할 상환 상수 시간 | |
| a_uniq. insert ( t ) |
std::
pair
<
iterator, bool > |
만약
t
가 비-const 우측값(rvalue)인 경우,
value_type
은
MoveInsertable
이어야
X
에 삽입 가능하며, 그렇지 않은 경우
value_type
은
CopyInsertable
이어야
X
에 삽입 가능합니다.
|
t 의 키와 동등한 키를 가진 요소가 컨테이너에 없는 경우에만 t 를 삽입합니다. |
반환된 pair의
bool
구성 요소는 삽입이 발생한 경우에만
true
이며, pair의
iterator
구성 요소는
t
의 키와 동등한 키를 가진 요소를 가리킵니다.
|
로그 시간 |
| a_eq. insert ( t ) |
iterator
|
만약
t
가 const가 아닌 rvalue라면,
value_type
은
MoveInsertable
을
X
에 대해 만족해야 합니다; 그렇지 않으면,
value_type
은
CopyInsertable
을
X
에 대해 만족해야 합니다
|
t 를 삽입하고 새로 삽입된 요소를 가리키는 반복자를 반환합니다. a_eq 에 t 와 동등한 요소들을 포함하는 범위가 존재하는 경우, t 는 해당 범위의 끝에 삽입됩니다 | 로그 시간 | |
| a. insert ( p, t ) |
iterator
|
만약
t
가 non-const rvalue라면,
value_type
은
MoveInsertable
을
X
에 대해 만족해야 합니다; 그렇지 않으면,
value_type
은
CopyInsertable
을
X
에 대해 만족해야 합니다.
|
고유 키를 가진 컨테이너에서는 t 의 키와 동등한 키를 가진 요소가 없는 경우에만 t 를 삽입합니다; 동등 키를 허용하는 컨테이너에서는 항상 t 를 삽입합니다. t 는 p 바로 앞 위치에 최대한 가깝게 삽입됩니다. | t 의 키와 동등한 키를 가진 요소를 가리키는 반복자 | 일반적으로 로그 시간이지만, t 가 p 바로 앞에 삽입되는 경우 분할 상환 상수 시간 |
| a. insert ( i, j ) | void |
value_type
은
EmplaceConstructible
이어야 하며
X
에
*
i
로부터 생성 가능해야 함.
i
와
j
는
a
의 반복자가 아님
|
범위
[
i
,
j
)
의 각 요소를 삽입함. 고유 키를 가진 컨테이너에서는 해당 요소의 키와 동등한 키를 가진 요소가 없을 때만 삽입하며, 동등 키를 가진 컨테이너에서는 항상 삽입함
|
N·log
(
a.
size
(
)
+
N
)
, 여기서
N
은
std::
distance
(
i, j
)
의 값임
|
|
|
a.
insert_range
(
rg
)
(C++23부터) |
void |
value_type
이
EmplaceConstructible
여야 하며
X
에
*
ranges::
begin
(
rg
)
로부터 생성 가능해야 함.
rg
와
a
가 겹치지 않아야 함
|
고유 키를 가진 컨테이너에서는 rg 의 각 요소에 대해 동등한 키를 가진 요소가 컨테이너에 없을 때만 삽입함; 동등 키를 가진 컨테이너에서는 항상 해당 요소를 삽입함 |
N·log
(
a.
size
(
)
+
N
)
, 여기서
N
은
ranges::
distance
(
rg
)
의 값임
|
|
| a. insert ( il ) | a. insert ( il. begin ( ) , il. end ( ) ) | ||||
| a_uniq. insert ( nh ) |
insert_return_type
|
nh
가 비어 있거나
a_uniq.
get_allocator
(
)
|
만약 nh 가 비어 있으면, 아무런 효과가 없습니다. 그렇지 않으면, 컨테이너에 nh. key ( ) 와 동등한 키를 가진 요소가 없는 경우에만 nh 가 소유한 요소를 삽입합니다. |
만약
nh
가 비어 있으면,
inserted
는
false
이고,
position
은
end
(
)
이며,
node
는 비어 있습니다. 그렇지 않고 삽입이 발생한 경우,
inserted
는
true
이고,
position
은 삽입된 요소를 가리키며,
node
는 비어 있습니다. 삽입이 실패한 경우,
inserted
는
false
이고,
node
는
nh
의 이전 값을 가지며,
position
은
nh.
key
(
)
와 동등한 키를 가진 요소를 가리킵니다.
|
로그 시간 |
| a_eq. insert ( nh ) |
iterator
|
nh
가 비어 있거나
a_eq.
get_allocator
(
)
|
만약 nh 가 비어 있다면, 아무런 효과가 없으며 a_eq. end ( ) 를 반환합니다. 그렇지 않으면, nh 가 소유한 요소를 삽입하고 새로 삽입된 요소를 가리키는 iterator를 반환합니다. nh. key ( ) 와 동등한 키를 가진 요소들의 범위가 a_eq 에 존재한다면, 요소는 해당 범위의 끝에 삽입됩니다. 보장: nh 는 비어 있음 | 로그 시간 | |
| a. insert ( p, nh ) |
iterator
|
nh
가 비어 있거나
a.
get_allocator
(
)
|
만약 nh 가 비어 있으면, 아무 효과도 없으며 a. end ( ) 를 반환합니다. 그렇지 않으면, 고유 키를 가진 컨테이너에서는 nh. key ( ) 와 동등한 키를 가진 요소가 없을 때만 nh 가 소유한 요소를 삽입합니다; 동등 키를 가진 컨테이너에서는 항상 nh 가 소유한 요소를 삽입합니다. 요소는 p 바로 앞 위치에 최대한 가깝게 삽입됩니다. 삽입이 성공하면 nh 가 비어 있고, 삽입이 실패하면 변경되지 않음을 보장합니다. | nh. key ( ) 와 동등한 키를 가진 요소를 가리키는 반복자 | 일반적으로 로그 시간이지만, 요소가 p 바로 앞에 삽입되는 경우 분할 상환 상수 시간 |
| a. extract ( k ) |
node_type
|
키가 k 와 동등한 첫 번째 요소를 컨테이너에서 제거합니다 |
요소를 찾은 경우 해당 요소를 소유하는
node_type
, 그렇지 않으면 빈
node_type
|
log ( a. size ( ) ) | |
|
a_tran.
extract
(
kx
)
(C++23 이후) |
node_type
|
키가 r 이고 ! c ( r, kx ) && ! c ( kx, r ) 조건이 true 인 첫 번째 요소를 컨테이너에서 제거합니다 |
요소가 발견된 경우 해당 요소를 소유하는
node_type
, 그렇지 않은 경우 빈
node_type
|
log ( a_tran. size ( ) ) | |
| a. extract ( q ) |
node_type
|
q 가 가리키는 요소를 제거합니다 |
해당 요소를 소유하는
node_type
|
분할 상환된 상수 시간 | |
| a. merge ( a2 ) | void |
a.
get_allocator
(
)
== a2. get_allocator ( ) |
a2 의 각 요소를 추출하여 a 의 비교 객체를 사용하여 a 에 삽입하려고 시도합니다. 고유 키를 가진 컨테이너에서 a 에 a2 의 요소 키와 동등한 키를 가진 요소가 있는 경우, 해당 요소는 a2 에서 추출되지 않습니다. 보장: 전송된 a2 요소에 대한 포인터와 참조는 동일한 요소를 참조하지만 a 의 멤버로서 참조합니다. 전송된 요소를 참조하는 반복자는 해당 요소를 계속 참조하지만, 이제는 a2 가 아닌 a 의 반복자처럼 동작합니다. 예외: 비교 객체가 예외를 발생시키지 않는 한 아무것도 발생하지 않음 |
N·log
(
a.
size
(
)
+
N
)
, 여기서
N
은 값
a2.
size
(
)
을 가짐
|
|
| a. erase ( k ) |
size_type
|
키가 k와 동등한 모든 요소를 컨테이너에서 삭제합니다 | 삭제된 요소의 수 |
log
(
a.
size
(
)
)
+ a. count ( k ) |
|
|
a_tran.
erase
(
kx
)
(C++23 이후) |
size_type
|
키가 r 인 모든 요소를 컨테이너에서 제거하며, 이때 ! c ( r, kx ) && ! c ( kx, r ) 조건이 true 인 경우 | 제거된 요소의 수 |
log
(
a_tran.
size
(
)
)
+ a_tran. count ( kx ) |
|
| a. erase ( q ) |
iterator
|
q 가 가리키는 요소를 삭제합니다 | 삭제되는 요소 바로 다음에 위치한 요소를 가리키는 iterator. 해당 요소가 존재하지 않는 경우 a. end ( ) 를 반환합니다 | 분할 상환 상수 시간 | |
| a. erase ( r ) |
iterator
|
r이 가리키는 요소를 삭제합니다 | 삭제되는 요소 바로 다음에 위치한 요소를 가리키는 iterator. 해당 요소가 존재하지 않을 경우 a. end ( ) 을 반환합니다 | 분할 상환 상수 시간 | |
| a. erase ( q1, q2 ) |
iterator
|
범위 내의 모든 요소를 삭제합니다
[
q1
,
q2
)
|
요소들이 삭제되기 전에 q2 가 가리키던 요소를 가리키는 반복자. 해당 요소가 존재하지 않는 경우, a. end ( ) 가 반환됩니다 |
log
(
a.
size
(
)
)
+
N
, 여기서
N
은
std::
distance
(
q1, q2
)
의 값을 가집니다
|
|
| a. clear ( ) | a. erase ( a. begin ( ) , a. end ( ) ) . 보장 조건: a. empty ( ) 가 true | a. size ( ) 에 선형적 | |||
| b. find ( k ) |
iterator
;
const_iterator
상수 객체의 경우
b
|
키 k 와 동등한 요소를 가리키는 반복자. 해당 요소를 찾지 못한 경우 b. end ( ) 를 반환 | 로그 시간 | ||
| a_tran. find ( ke ) |
iterator
;
const_iterator
상수 객체에 대해
a_tran
|
키가
r
인 요소를 가리키는 반복자로,
!
c
(
r, ke
)
&&
|
로그 시간 | ||
| b. count ( k ) |
size_type
|
키가 k 와 동등한 요소의 개수 |
log
(
b.
size
(
)
)
+ b. count ( k ) |
||
| a_tran. count ( ke ) |
size_type
|
키가
r
인 요소들의 개수로, 다음 조건을 만족함:
!
c
(
r, ke
)
&&
|
log
(
a_tran.
size
(
)
)
+ a_tran. count ( ke ) |
||
| b. contains ( k ) | bool | return b. find ( k ) ! = b. end ( ) ; | |||
| a_tran. contains ( ke ) | bool |
return
|
|||
| b. lower_bound ( k ) |
iterator
;
const_iterator
for constant
b
|
k 이상의 키를 가진 첫 번째 요소를 가리키는 반복자, 또는 해당 요소를 찾을 수 없는 경우 b. end ( ) 를 반환 | 로그 시간 | ||
| a_tran. lower_bound ( kl ) |
iterator
;
const_iterator
상수 객체용
a_tran
|
키가 r 이고 ! c ( r, kl ) 조건을 만족하는 첫 번째 원소를 가리키는 반복자. 해당 원소를 찾지 못한 경우 a_tran. end ( ) 반환 | 로그 시간 복잡도 | ||
| b. upper_bound ( k ) |
iterator
;
const_iterator
상수 버전
b
|
k 보다 큰 키를 가진 첫 번째 요소를 가리키는 반복자, 또는 해당 요소를 찾지 못한 경우 b. end ( ) 반환 | 로그 시간 복잡도 | ||
| a_tran. upper_bound ( ku ) |
iterator
;
const_iterator
for constant
a_tran
|
키가 r 이고 c ( ku, r ) 조건을 만족하는 첫 번째 요소를 가리키는 반복자. 해당 요소를 찾지 못한 경우 a_tran. end ( ) 반환 | 로그 시간 | ||
| b. equal_range ( k ) |
std::
pair
<
iterator, iterator > ;
std::
pair
<
|
다음과 동등함:
return
|
로그 시간 복잡도 | ||
| a_tran. equal_range ( ke ) |
std::
pair
<
iterator, iterator > ;
std::
pair
<
|
다음과 동등함:
return
|
로그 시간 |
반복자
연관 컨테이너의 반복자는 LegacyBidirectionalIterator 요구 사항을 충족합니다.
value_type
이
key_type
과 동일한 연관 컨테이너의 경우,
iterator
와
const_iterator
모두 상수 반복자입니다.
iterator
와
const_iterator
가 동일한 타입인지 여부는 명시되어 있지 않습니다.
연관 컨테이너의 반복자는 컨테이너를 키의 비내림차순으로 순회하며, 여기서 비내림차순은 컨테이너를 구성하는 데 사용된 비교 연산에 의해 정의됩니다. 즉, 주어진
- a , 연관 컨테이너
- i 와 j , a 에 대한 역참조 가능 반복자.
i 에서 j 까지의 거리가 양수이면, a. value_comp ( ) ( * j, * i ) == false 입니다. 또한 a 가 고유 키를 가진 연관 컨테이너인 경우, 더 강력한 조건인 a. value_comp ( ) ( * i, * j ) ! = false 가 성립합니다.
|
이 섹션은 불완전합니다
이유: 요구사항을 완성해야 합니다. |
표준 라이브러리
다음 표준 라이브러리 컨테이너들은 AssociativeContainer 요구 사항을 충족합니다:
|
고유 키의 컬렉션, 키로 정렬됨
(class template) |
|
|
키의 컬렉션, 키로 정렬됨
(class template) |
|
|
키-값 쌍의 컬렉션, 키로 정렬됨, 키는 고유함
(class template) |
|
|
키-값 쌍의 컬렉션, 키로 정렬됨
(class template) |
결함 보고서
다음의 동작 변경 결함 보고서들은 이전에 발표된 C++ 표준에 소급 적용되었습니다.
| DR | 적용 대상 | 게시된 동작 | 올바른 동작 |
|---|---|---|---|
| LWG 354 | C++98 |
lower_bound
와
upper_bound
가 요소를 찾지 못했을 때
end iterator를 반환하지 않음 |
이 경우 end iterator를
반환함 |
| LWG 589 | C++98 |
i
와
j
가 참조하는 요소들의
타입이
X::value_type
이어야 함
|
요소들이
X::value_type
으로
암시적으로 변환 가능해야 함 |