# C++ concepts: AssociativeContainer

From cppreference.com
< cpp‎ | concept

An `AssociativeContainer` is an ordered `Container` that provides fast lookup of objects based on keys.

### Requirements

### Legend

`X` | Container type
`a` | Value of type `X`
`a2` | Value of a type `Y` whose node handles are compatible with X
`b` | Possibly const value of type `X`
`u` | Arbitrary variable name
`a_uniq` | Value of type `X` when `X` supports unique keys
`a_eq` | Value of type `X` when `X` supports multiple keys
`a_tran` | Possibly const value of type `X` when type `X::key_compare::is_transparent` exists
`i`, `j` | `InputIterator`s denoting a valid range and referring to elements implicitly convertible to `X::value_type`
`p` | A valid const iterator to `a`
`q` | A valid dereferenceable const iterator to `a`
`r` | A valid dereferenceable iterator to `a`
`q1`, `q2` | const iterators denoting a valid range in `a`
`il` | An object of type std::initializer_list<value_type>
`t` | A value of type `X::value_type`
`k` | A value of type `X::key_type`
`c` | A possibly const value of type `X::key_compare`
`kl` | A value such that `a` is partitioned with respect to c(r,kl), with `r` the key value of `e` and `e` in `a`
`ku` | A value such that `a` is partitioned with respect to !c(ku, r)
`ke` | A value such that `a` is partitioned with respect to c(r, ke) and !c(ke, r), with c(r, ke) implying !c(ke, r)
`A` | Storage allocator used by `X`, or std::allocator_type<X::value_type>
`m` | Allocator of a type convertible to `A`
`nh` | A non-const rvalue of type `X::node_type`

expression | return type | pre/requirements | post/effects | complexity
--- | --- | --- | --- | ---
X::key_type | `Key` | `Key` is `Destructible` |  | compile time
X::key_compare | `Compare` |  |  | compile time
X::value_compare | a type satisfying `BinaryPredicate` | key_compare for std::set and std::multiset; an ordering relation over `Key` for std::map and std::multimap |  | compile time
X(c), X a(c); |  | key_compare is `CopyConstructible` | Construct an empty container using a copy of c as `key_comp` | constant
X(), X a; |  | key_compare is `CopyConstructible` | Construct an empty container using a Compare() as `key_comp` | constant
X(i, j, c), X a(i, j, c); |  | key_compare is `CopyConstructible` and value_type is `EmplaceConstructible` into X from *i | Constructs an empty container using a copy of c as `key_comp` and inserts all elements from the range `[i; j)` | generally `N log N`, or `N` if `[i, j)` is sorted (where `N` is std::distance(i, j))
X(i, j), X a(i, j); |  | key_compare is `CopyConstructible` and value_type is `EmplaceConstructible` into X from *i | Constructs an empty container using a Compare() as `key_comp` and inserts all elements from the range `[i; j)` | generally `N log N`, or `N` if `[i, j)` is sorted according to value_comp() (where `N` is std::distance(i, j))
X(il); |  | Equivalent to X(il.begin(), il.end()); | Equivalent to X(il.begin(), il.end());
a = il | X& | `T` is `CopyInsertable` into `X` and also `CopyAssignable` | Assign the range [il.begin(), il.end()) into `a`. Elements of `a` that were not assigned to are destroyed | generally `N log N`, or `N` if [il.begin(), il.end()) is sorted according to value_comp() (where `N` is il.size() + a.size())
a.key_comp() | X::key_compare |  | The comparison object with which `a` was constructed is returned. | constant
a.value_comp() | X::value_compare |  | An object of type X::value_compare constructed out of the comparison object is returned. | constant

An AssociativeContainer `X` that is either `std::map` and `std::multimap` additionally supports the expression X::mapped_type, which has a return type of T, with the requirement that `T` be `Destructible`, and compile time complexity.

| This section is incomplete Reason: Finish requirements.

### AssociativeContainers in the standard library

set | collection of unique keys, sorted by keys (class template)
multiset | collection of keys, sorted by keys (class template)
map | collection of key-value pairs, sorted by keys, keys are unique (class template)
multimap | collection of key-value pairs, sorted by keys (class template)

Retrieved from "http://en.cppreference.com/mwiki/index.php?title=cpp/concept/AssociativeContainer&oldid=88052"
Category:

- Todo with reason