 |
 |
| Category: containers | Component type: concept |
| X | A type that is a model of Unique Sorted 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 |
| c | Object of type X::key_compare |
| Name | Expression | Type requirements | Return type |
|---|---|---|---|
| Range constructor |
X(i, j) X a(i, j); |
i and j are Input Iterators whose value type is convertible to T [1]. | |
| Range constructor with compare |
X(i, j, c) X a(i, j, c); |
i and j are Input Iterators whose value type is convertible to T [1]. c is an object of type key_compare. | |
| Insert with hint | a.insert(p, t) | iterator | |
| Insert range | a.insert(i, j) | i and j are Input Iterators whose value type is convertible to X::value_type. [1] | void |
| Name | Expression | Precondition | Semantics | Postcondition |
|---|---|---|---|---|
| Range constructor |
X(i, j) X a(i, j); |
[i,j) is a valid range. | Creates an associative container that contains all of the elements in the range [i,j) that have unique keys. The comparison object used by the container is key_compare(). | size() is less than or equal to the distance from i to j. |
| Range constructor with compare |
X(i, j, c) X a(i, j, c); |
[i,j) is a valid range. | Creates an associative container that contains all of the elements in the range [i,j) that have unique keys. The comparison object used by the container is c. | size() is less than or equal to the distance from i to j. |
| Insert with hint | a.insert(p, t) | p is a nonsingular iterator in a. | Inserts t into a if and only if a does not already contain an element whose key is equivalent to t's key. The argument p is a hint: it points to the location where the search will begin. The return value is a dereferenceable iterator that points to the element with a key that is equivalent to that of t. | a contains an element whose key is the same as that of t. The size of a is incremented by either 1 or 0. |
| Insert range | a.insert(i, j) | [i, j) is a valid range. | Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j). Each element is inserted into a if and only if a does not already contain an element with an equivalent key. | The size of a is incremented by at most j - i. |
Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.
Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().
| Strictly ascending order | The elements in a Unique Sorted Associative Container are always arranged in strictly ascending order by key. That is, if a is a Unique Sorted Associative Container, then is_sorted(a.begin(), a.end(), a.value_comp()) is always true. Furthermore, if i and j are dereferenceable iterators in a such that i precedes j, then a.value_comp()(*i, *j) is always true. [2] |
[1] At present (early 1998), not all compilers support "member templates". If your compiler supports member templates then i and j may be of any type that conforms to the Input Iterator requirements. If your compiler does not yet support member templates, however, then i and j must be of type const T* or of type X::const_iterator.
[2] This is a more stringent invariant than that of Sorted Associative Container. In a Sorted Associative Container we merely know that every element is less than or equal to its successor; in a Unique Sorted Associative Container, however, we know that it must be less than its successor.
| privacy policy | | | contact us |
| Copyright © 1993-2001 Silicon Graphics, Inc. All rights reserved. | | | Trademark Information |