Each associative container is parameterized on
Key
and an ordering relation
Compare
that induces a strict weak ordering ([alg.sorting]) on
elements of
Key.

The phrase “equivalence of keys” means the equivalence relation imposed by the
comparison object.

That is, two keys
k1
and
k2
are considered to be equivalent if for the
comparison object
comp,
comp(k1, k2) == false && comp(k2, k1) == false.

For any two keys
k1
and
k2
in the same container, calling
comp(k1, k2)
shall always return the same value.

An associative container supports *unique keys* if it may contain at
most one element for each key.

Otherwise, it supports *equivalent keys*.

The set and map classes support unique keys; the multiset
and multimap classes support equivalent keys.

For multiset and multimap,
insert, emplace, and erase preserve the relative ordering
of equivalent elements.

In this subclause,

- X denotes an associative container class,
- a denotes a value of type X,
- a2 denotes a value of a type with nodes compatible with type X (Table 79),
- b denotes a possibly const value of type X,
- u denotes the name of a variable being declared,
- a_uniq denotes a value of type X when X supports unique keys,
- a_eq denotes a value of type X when X supports multiple keys,
- a_tran denotes a possibly const value of type X
when the
*qualified-id*X::key_compare::is_transparent is valid and denotes a type ([temp.deduct]), - i and j
meet the
*Cpp17InputIterator*requirements and refer to elements implicitly convertible to value_type, - [i, j) denotes a valid range,
- rg denotes a value of a type R
that models
*container-compatible-range*<value_type>, - p denotes a valid constant iterator to a,
- q denotes a valid dereferenceable constant iterator to a,
- r denotes a valid dereferenceable iterator to a,
- [q1, q2) denotes a valid range of constant iterators in a,
- il designates an object of type initializer_list<value_type>,
- t denotes a value of type X::value_type,
- k denotes a value of type X::key_type, and
- c denotes a possibly const value of type X::key_compare;
- kl is a value such that a is partitioned ([alg.sorting]) with respect to c(x, kl), with x the key value of e and e in a;
- ku is a value such that a is partitioned with respect to !c(ku, x), with x the key value of e and e in a;
- ke is a value such that a is partitioned with respect to c(x, ke) and !c(ke, x), with c(x, ke) implying !c(ke, x) and with x the key value of e and e in a;
- kx is a value such that
- a is partitioned with respect to c(x, kx) and !c(kx, x), with c(x, kx) implying !c(kx, x) and with x the key value of e and e in a, and
- kx is not convertible to either iterator or const_iterator; and

- A denotes the storage allocator used by X, if any, or allocator<X::value_type> otherwise,
- m denotes an allocator of a type convertible to A, and nh denotes a non-const rvalue of type X::node_type.

A type X meets the *associative container* requirements
if X meets all the requirements of an allocator-aware
container ([container.requirements.general]) and
the following types, statements, and expressions are well-formed and
have the specified semantics,
except that for
map and multimap, the requirements placed on value_type
in [container.alloc.reqmts] apply instead to key_type
and mapped_type.

```
typename X::key_type
```

```
typename X::mapped_type
```

```
typename X::value_type
```

```
typename X::key_compare
```

```
typename X::value_compare
```

```
typename X::node_type
```

```
X(c)
```

```
X u = X();
X u;
```

```
X(i, j, c)
```

```
X(i, j)
```

```
X(from_range, rg, c)
```

```
X(from_range, rg)
```

```
X(il, c)
```

```
X(il)
```

```
a = il
```

```
b.key_comp()
```

```
b.value_comp()
```

```
a_uniq.emplace(args)
```

```
a_eq.emplace(args)
```

```
a.emplace_hint(p, args)
```

```
a_uniq.insert(t)
```

```
a_eq.insert(t)
```

```
a.insert(p, t)
```

```
a.insert(i, j)
```

```
a.insert_range(rg)
```

```
a.insert(il)
```

```
a_uniq.insert(nh)
```

Otherwise if the insertion took place, inserted is true,
position points to the inserted element, and node is empty;
if the insertion failed, inserted is false,
node has the previous value of nh, and
position points to an element with a key equivalent to nh.key().

```
a_eq.insert(nh)
```

```
a.insert(p, nh)
```

```
a.extract(k)
```

```
a_tran.extract(kx)
```

```
a.extract(q)
```

```
a.merge(a2)
```

```
a.erase(k)
```

```
a_tran.erase(kx)
```

```
a.erase(q)
```

```
a.erase(r)
```

```
a.erase(q1, q2)
```

```
a.clear()
```

```
b.find(k)
```

```
a_tran.find(ke)
```

```
b.count(k)
```

```
a_tran.count(ke)
```

```
b.contains(k)
```

```
a_tran.contains(ke)
```

```
b.lower_bound(k)
```

```
a_tran.lower_bound(kl)
```

```
b.upper_bound(k)
```

```
a_tran.upper_bound(ku)
```

```
b.equal_range(k)
```

```
a_tran.equal_range(ke)
```

The insert, insert_range, and emplace members
shall not affect the validity of
iterators and references to the container,
and the erase members shall invalidate only iterators and
references to the erased elements.

The extract members invalidate only iterators to the removed element;
pointers and references to the removed element remain valid.

However, accessing
the element through such pointers and references while the element is owned by
a node_type is undefined behavior.

References and pointers to an element
obtained while it is owned by a node_type are invalidated if the element
is successfully inserted.

The fundamental property of iterators of associative containers is that they iterate through the containers
in the non-descending order of keys where non-descending is defined by the comparison that was used to
construct them.

For any two dereferenceable iterators
i
and
j
such that distance from
i
to
j
is positive, the following condition holds:
value_comp(*j, *i) == false

For associative containers with unique keys the stronger condition holds:
value_comp(*i, *j) != false

When an associative container is constructed by passing a comparison object the
container shall not store a pointer or reference to the passed object,
even if that object is passed by reference.

When an associative container is copied, through either a copy constructor
or an assignment operator,
the target container shall then use the comparison object from the container
being copied,
as if that comparison object had been passed to the target container in
its constructor.

The member function templates
find, count, contains,
lower_bound, upper_bound, equal_range,
erase, and extract
shall not participate in overload resolution unless
the *qualified-id* Compare::is_transparent is valid
and denotes a type ([temp.deduct]).

Additionally, the member function templates extract and erase
shall not participate in overload resolution if
is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator>
is true,
where K is the type substituted as the first template argument.

A deduction guide for an associative container shall not participate in overload resolution
if any of the following are true:

- It has an InputIterator template parameter and a type that does not qualify as an input iterator is deduced for that parameter.
- It has an Allocator template parameter and a type that does not qualify as an allocator is deduced for that parameter.
- It has a Compare template parameter and a type that qualifies as an allocator is deduced for that parameter.

For associative containers, if an exception is thrown by any operation from
within an insert or emplace function inserting a single element, the
insertion has no effect.