Книга: Standard Template Library Programmer
Multiple Sorted Associative Container
Разделы на этой странице:
Multiple Sorted Associative Container
Category: containers
Component type: concept
Description
A Multiple Sorted Associative Container is a Sorted Associative Container that is also a Multiple Associative Container. That is, it is a Sorted Associative Container
with the property that any number of elements in the container may have equivalent keys.
Refinement of
Sorted Associative Container, Multiple Associative Container
Associated types
None, except for those described in the Sorted Associative Container and Multiple Associative Container requirements.
Notation
X A type that is a model of Multiple 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
Valid expressions
In addition to the expressions defined in Sorted Associative Container and Multiple Associative Container, the following expressions must be valid.
| 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]. | X |
| 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. | X |
| 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 |
Expression semantics
| 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). The comparison object used by the container is key_compare(). | size() is 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) . The comparison object used by the container is c. | size() is 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. 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 that was just inserted. | a contains an element whose key is the same as that of t. The size of a is incremented by 1. |
| 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. | The size of a is incremented by j – i. |
Complexity guarantees
The range constructor, and range constructor with compare, are in general O(N * log(N)), where N is the size of the range. However, they are linear in N if the range is already sorted by value_comp().
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().
Models
• multimap
• multiset
Notes
[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.
See also
Associative Container, Sorted Associative Container, Unique Sorted Associative Container Hashed Associative Container
Оглавление книги
- Associative Container
- Simple Associative Container
- Pair Associative Container
- Sorted Associative Container
- Hashed Associative Container
- Hash Function
- Unique Associative Container
- Multiple Associative Container
- Unique Sorted Associative Container
- Multiple Sorted Associative Container
- Unique Hashed Associative Container
- Multiple Hashed Associative Container
- Multiple Associative Container
- Associative Container
- Multiple Hashed Associative Container
- Метод Sorted
- Associative Containers
- Simple Associative Container
- Pair Associative Container
- Sorted Associative Container
- Hashed Associative Container
- Unique Associative Container
- Unique Sorted Associative Container
- Unique Hashed Associative Container