stlab.adobe.com Adobe Systems Incorporated

MultipleAssociativeContainer

containers.gif
concept.gif
Category: containers Component type: concept

Description

A Multiple Associative Container is an AssociativeContainer in which there may be more than one element with the same key. That is, it is an AssociativeContainer that does not have the restrictions of a UniqueAssociativeContainer.

Refinement of

AssociativeContainer

Associated types

None, except for those defined by AssociativeContainer

Notation

X A type that is a model of Multiple 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

Definitions

Valid expressions

In addition to the expressions defined in AssociativeContainer, 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 InputIterator whose value type is convertible to T [1]  
Insert element a.insert(t)   X::iterator
Insert range a.insert(i, j) i and j are InputIterator whose value type is convertible to X::value_type. 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 elements in the range [i,j). size() is equal to the distance from i to j. Each element in [i, j) is present in the container.
Insert element a.insert(t)   Inserts t into a. The size of a is incremented by 1. The value of a.count(t) is incremented by a.
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

Average complexity for insert element is at most logarithmic.

Average complexity for insert range is at most O(N * log(size() + N)), where N is j - i.

Invariants

Models

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 InputIterator 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

AssociativeContainer, UniqueAssociativeContainer, UniqueSortedAssociativeContainer, MultipleSortedAssociativeContainer

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google