Destructive Associative Container LOGN

Category: containers
Component type: concept

Description

A Destructive Associative Container LOGN 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, the implementation must be careful to only delete one instance of the data when the same data appears multiple times with the same key. 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.

A Destructive Associative Container LOGN is identical to a Destructive Associative Container except that the performance requirement for destroying an element via an iterator has been changed to logarithmic time.

Refinement of

Associative Container

Associated types

The same as Associative Container

Notation

X A type that is a model of Destructive Associative Container LOGN
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

Definitions

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.

Valid expressions

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

Expression semantics

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())  

Complexity guarantees

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 logarithmic 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.

Invariants

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.

Models

Notes

[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.

See also

Destructive Associative Container, Simple Associative Container, Pair Associative Container, Unique Associative Container, Multiple Associative Container, Sorted Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container,

 All Classes Files Functions Variables Typedefs