Category: containers
Component type: concept
A Destructive Associative Container is an Associative Container that supports both deletion and erasing of elements as a single operation.
Destructive operations are only required for values that are pointers. For Pair Associative Containers, the data in the key/data pair is what is deleted before the entire pair is erased. For Multiple Associative Containers that are also Simple Associative Containers, all elements that have identical keys to the one being destroyed must be destroyed as well, but note that the implementation must be careful to only delete one instance of the data. For Multiple Associative Containers that are also Pair Associative Containers, all elements that have identical key/data pairs to the one being destroyed must be destroyed as well. In this case, the data type in the value_type pair must be Equality Comparable and pointers satisfy this requirement.
In all cases, the user of the container must make sure that duplicate pointers are not deleted more than once.
The same as Associative Container
X | A type that is a model of Destructive Associative Container |
a | Object of type X |
t | Object of type X::value_type |
k | Object of type X::key_type |
p, q | Object of type X::iterator |
If a is an associative container, then p is a valid iterator in a if it is a valid iterator that is reachable from a.begin().
If a is an associative container, then [p, q) is a valid range in a if [p, q) is a valid range and p is a valid iterator in a.
In addition to the expressions defined in Associative Container, the following expressions must be valid.
| Name | Expression | Type requirements | Return type |
|---|---|---|---|
| Destroy key | a.destroy(k) | size_type | |
| Destroy element | a.destroy(p) | void | |
| Destroy range | a.destroy(p, q) | void | |
| Destroy | a.destroy() | void |
| Name | Expression | Precondition | Semantics | Postcondition |
|---|---|---|---|---|
| Destroy key | a.destroy(k) | Deletes each unique instance of data associated found in elements with the key k, and then removes all elements with that key k from a. [2] The return value is the number of elements that were erased, i.e. the old value of a.count(k). | a.size() is decremented by a.count(k). a contains no elements with key k. | |
| Destroy element | a.destroy(p) | p is a dereferenceable iterator in a. | Deletes the data associated with the element pointed to by p and removes said element from a. If multiple instances of the data is found within the container, the user must take measures to not delete them. | a.size() is decremented by 1. |
| Erase range | a.destroy(p, q) | [p, q) is a valid range in a. | Deletes the data associated with the elements in the range [p,q) and removes them from a. Duplicate instances of data are only checked for identical keys. If instances of the same data exists with different keys, then the user must take care to erase those elements before calling this method. | a.size() is decremented by the distance from i to j. |
| Destroy | a.destroy() | Equivalent to a.destroy(a.begin(), a.end()) |
Average complexity for destroy key is at most O(log(size()) + count(k)2) when multiple instances of the same key are allowed, O(log(size()) + count(k)) otherwise.
Average complexity for erase element is constant time.
Average complexity for erase range when multiple instances of the same key are allowed is at most O(log(size()) + N2), where N is the number of elements in the range. Otherwise, it is O(log(size()) + N) time.
| Contiguous storage | All elements with the same key are adjacent to each other. That is, if p and q are iterators that point to elements that have the same key, and if p precedes q, then every element in the range [p, q) has the same key as every other element. |
| Immutability of keys | Every element of an Associative Container has an immutable key. Objects may be inserted and erased, but an element in an Associative Container may not be modified in such a way as to change its key. |
[1] The reason there is no such mechanism is that the way in which elements are arranged in an associative container is typically a class invariant; elements in a Sorted Associative Container, for example, are always stored in ascending order. It would make no sense to allow the position of an element to be chosen arbitrarily.
[2] Keys are not required to be Equality Comparable: associative containers do not necessarily use operator== to determine whether two keys are the same. In /ref sortedassociativecontainer "Sorted Associative Containers", for example, where keys are ordered by a comparison function, two keys are considered to be the same if neither one is less than the other.
[3] Note the implications of this member function: it means that if two elements have the same key, there must be no elements with different keys in between them. The requirement that elements with the same key be stored contiguously is an associative container invariant.
Destructive Associative Container LOGN, Simple Associative Container, Pair Associative Container, Unique Associative Container, Multiple Associative Container, Sorted Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container,
1.7.3
