![]() |
Home | Libraries | People | FAQ | More |
boost::container::multimap
// In header: <boost/container/map.hpp> template<typename Key, typename T, typename Compare = Key>, typename Allocator = new_allocator< const Key, T> >, typename Options = tree_assoc_defaults> class multimap { public: // types typedef Key ; typedef T ; typedef ; typedef ::boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef boost::container::allocator_traits< ; typedef implementation_defined ; typedef implementation_defined ; typedef Compare ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; // construct/copy/destruct () ; (const ); (const Compare &); (const Compare &, const ); template<typename InputIterator> (InputIterator, InputIterator); template<typename InputIterator> (InputIterator, InputIterator, const ); template<typename InputIterator> (InputIterator, InputIterator, const Compare &); template<typename InputIterator> (InputIterator, InputIterator, const Compare &, const ); template<typename InputIterator> (ordered_range_t, InputIterator, InputIterator); template<typename InputIterator> (ordered_range_t, InputIterator, InputIterator, const Compare &); template<typename InputIterator> (ordered_range_t, InputIterator, InputIterator, const Compare &, const ); template<typename InputIterator> (ordered_range_t, InputIterator, InputIterator, const ); (); (, const ); (, const Compare &); (, const Compare &, const ); (ordered_range_t, ); (ordered_range_t, , const Compare &); (ordered_range_t, , const Compare &, const ); (const multimap &); (multimap &&) ; (const multimap &, const ); (multimap &&, const ); multimap & (const multimap &); multimap & (multimap &&) ; multimap & (); // public member functions ((typename const Key, T > >::); () ; stored_allocator_type & (); const stored_allocator_type & () ; iterator (); () ; () ; iterator () ; () ; () ; reverse_iterator () ; const_reverse_iterator () ; const_reverse_iterator () ; reverse_iterator () ; const_reverse_iterator () ; const_reverse_iterator () ; bool () ; size_type () ; size_type () ; template< Args> iterator (Args &&...); template< Args> iterator (, Args &&...); iterator (const ); iterator (); template<typename Pair> iterator (Pair &&); iterator (, const ); iterator (, ); template<typename Pair> iterator (, Pair &&); template<typename InputIterator> void (InputIterator, InputIterator); void (); iterator (); iterator (, ); iterator (); size_type (const ); iterator (, ); (const ); (); template<typename C2> void (multimap< Key, T, C2, Allocator, Options > &); template<typename C2> void (multimap< Key, T, C2, Allocator, Options > &&); template<typename C2> void (map< Key, T, C2, Allocator, Options > &); template<typename C2> void (map< Key, T, C2, Allocator, Options > &&); void (multiset &) ; void () ; key_compare () ; value_compare () ; iterator (const ); (const ) ; template<typename K> iterator (const K &); template<typename K> (const K &) ; size_type (const ) ; template<typename K> size_type (const K &) ; bool (const ) ; template<typename K> bool (const K &) ; iterator (const ); (const ) ; template<typename K> iterator (const K &); template<typename K> (const K &) ; iterator (const ); (const ) ; template<typename K> iterator (const K &); template<typename K> (const K &) ; iterator, iterator > (const ); (const ) ; template<typename K> iterator, iterator > (const K &); template<typename K> (const K &) ; void (); // friend functions bool (const multimap &, const multimap &); bool (const multimap &, const multimap &); bool (const multimap &, const multimap &); bool (const multimap &, const multimap &); bool (const multimap &, const multimap &); bool (const multimap &, const multimap &); void (multimap &, multimap &) ; };
A multimap is a kind of associative container that supports equivalent keys (possibly containing multiple copies of the same key value) and provides for fast retrieval of values of another type T based on the keys. The multimap class supports bidirectional iterators.
A multimap satisfies all of the requirements of a container and of a reversible container and of an associative container. The value_type
stored by this container is the value_type is std::pair<const Key, T>.
typename Key
is the key_type of the map
typename T
typename Compare = Key>
is the ordering function for Keys (e.g. std::less<Key>).
typename Allocator = new_allocator< const Key, T> >
is the allocator to allocate the value_type
s (e.g. allocator< std::pair<const Key, T> > ).
typename Options = tree_assoc_defaults
is an packed option type generated using using boost::container::tree_assoc_options
.
multimap
public
construct/copy/destruct() ;
Effects: Default constructs an empty multimap.
Complexity: Constant.
(const a);
Effects: Constructs an empty multimap using the specified allocator object and allocator.
Complexity: Constant.
(const Compare & comp);
Effects: Constructs an empty multimap using the specified comparison.
Complexity: Constant.
(const Compare & comp, const a);
Effects: Constructs an empty multimap using the specified comparison and allocator.
Complexity: Constant.
template<typename InputIterator> (InputIterator first, InputIterator last);
Effects: Constructs an empty multimap and inserts elements from the range [first ,last ).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is last - first.
template<typename InputIterator> (InputIterator first, InputIterator last, const a);
Effects: Constructs an empty multimap using the specified allocator, and inserts elements from the range [first ,last ).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is last - first.
template<typename InputIterator> (InputIterator first, InputIterator last, const Compare & comp);
Effects: Constructs an empty multimap using the specified comparison object and inserts elements from the range [first ,last ).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is last - first.
template<typename InputIterator> (InputIterator first, InputIterator last, const Compare & comp, const a);
Effects: Constructs an empty multimap using the specified comparison object and allocator, and inserts elements from the range [first ,last ).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is last - first.
template<typename InputIterator> (ordered_range_t, InputIterator first, InputIterator last);
Effects: Constructs an empty multimap and inserts elements from the ordered range [first ,last). This function is more efficient than the normal range creation for ordered ranges.
Requires: [first ,last) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
template<typename InputIterator> (ordered_range_t, InputIterator first, InputIterator last, const Compare & comp);
Effects: Constructs an empty multimap using the specified comparison object and inserts elements from the ordered range [first ,last). This function is more efficient than the normal range creation for ordered ranges.
Requires: [first ,last) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
template<typename InputIterator> (ordered_range_t, InputIterator first, InputIterator last, const Compare & comp, const a);
Effects: Constructs an empty multimap using the specified comparison object and allocator, and inserts elements from the ordered range [first ,last). This function is more efficient than the normal range creation for ordered ranges.
Requires: [first ,last) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
template<typename InputIterator> (ordered_range_t, InputIterator first, InputIterator last, const a);
Effects: Constructs an empty multimap using the specified allocator and inserts elements from the ordered range [first ,last). This function is more efficient than the normal range creation for ordered ranges.
Requires: [first ,last) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
( il);
Effects: Constructs an empty multimap and and inserts elements from the range [il.begin(), il.end()).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is il.first() - il.end().
( il, const a);
Effects: Constructs an empty multimap using the specified allocator, and inserts elements from the range [il.begin(), il.end()).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is il.first() - il.end().
( il, const Compare & comp);
Effects: Constructs an empty multimap using the specified comparison object and inserts elements from the range [il.begin(), il.end()).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is il.first() - il.end().
( il, const Compare & comp, const a);
Effects: Constructs an empty multimap using the specified comparison object and allocator, and inserts elements from the range [il.begin(), il.end()).
Complexity: Linear in N if the range [first ,last ) is already sorted using the predicate and otherwise N logN, where N is il.first() - il.end().
(ordered_range_t, il);
Effects: Constructs an empty map and inserts elements from the ordered range [il.begin(), il.end()). This function is more efficient than the normal range creation for ordered ranges.
Requires: [il.begin(), il.end()) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
(ordered_range_t, il, const Compare & comp);
Effects: Constructs an empty map using the specified comparison object and inserts elements from the ordered range [il.begin(), il.end()). This function is more efficient than the normal range creation for ordered ranges.
Requires: [il.begin(), il.end()) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
(ordered_range_t, il, const Compare & comp, const a);
Effects: Constructs an empty map and inserts elements from the ordered range [il.begin(), il.end()). This function is more efficient than the normal range creation for ordered ranges.
Requires: [il.begin(), il.end()) must be ordered according to the predicate.
Complexity: Linear in N.
Note: Non-standard extension.
(const multimap & x);
Effects: Copy constructs a multimap.
Complexity: Linear in x.size().
(multimap && x) ;
Effects: Move constructs a multimap. Constructs *this using x's resources.
Complexity: Constant.
Postcondition: x is emptied.
(const multimap & x, const a);
Effects: Copy constructs a multimap.
Complexity: Linear in x.size().
(multimap && x, const a);
Effects: Move constructs a multimap using the specified allocator. Constructs *this using x's resources. Complexity: Constant if a == x.get_allocator(), linear otherwise.
Postcondition: x is emptied.
multimap & (const multimap & x);
Effects: Makes *this a copy of x.
Complexity: Linear in x.size().
multimap & (multimap && x) ;
Effects: this->swap(x.get()).
Complexity: Constant.
multimap & ( il);
Effects: Assign content of il to *this.
multimap
public member functions((typename const Key, T > >::);
() ;
Effects: Returns a copy of the allocator that was passed to the object's constructor.
Complexity: Constant.
stored_allocator_type & ();
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
const stored_allocator_type & () ;
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
iterator ();
Effects: Returns an iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant
() ;
Effects: Returns a const_iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant.
() ;
Effects: Returns a const_iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant.
iterator () ;
Effects: Returns an iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
() ;
Effects: Returns a const_iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
() ;
Effects: Returns a const_iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
reverse_iterator () ;
Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
reverse_iterator () ;
Effects: Returns a reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
bool () ;
Effects: Returns true if the container contains no elements.
Throws: Nothing.
Complexity: Constant.
size_type () ;
Effects: Returns the number of the elements contained in the container.
Throws: Nothing.
Complexity: Constant.
size_type () ;
Effects: Returns the largest possible size of the container.
Throws: Nothing.
Complexity: Constant.
template< Args> iterator (Args &&... args);
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the container. p is a hint pointing to where the insert should start to search.
Returns: An iterator pointing to the element with key equivalent to the key of x.
Complexity: Logarithmic in general, but amortized constant if t is inserted right before p.
template< Args> iterator ( p, Args &&... args);
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the container. p is a hint pointing to where the insert should start to search.
Returns: An iterator pointing to the element with key equivalent to the key of x.
Complexity: Logarithmic in general, but amortized constant if t is inserted right before p.
iterator (const x);
Effects: Inserts x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator ( x);
Effects: Inserts a new value move-constructed from x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
template<typename Pair> iterator (Pair && x);
Effects: Inserts a new value constructed from x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator ( p, const x);
Effects: Inserts a copy of x in the container. p is a hint pointing to where the insert should start to search.
Returns: An iterator pointing to the element with key equivalent to the key of x.
Complexity: Logarithmic in general, but amortized constant if t is inserted right before p.
iterator ( p, x);
Effects: Inserts a new value move constructed from x in the container. p is a hint pointing to where the insert should start to search.
Returns: An iterator pointing to the element with key equivalent to the key of x.
Complexity: Logarithmic in general, but amortized constant if t is inserted right before p.
template<typename Pair> iterator ( p, Pair && x);
Effects: Inserts a new value constructed from x in the container. p is a hint pointing to where the insert should start to search.
Returns: An iterator pointing to the element with key equivalent to the key of x.
Complexity: Logarithmic in general, but amortized constant if t is inserted right before p.
template<typename InputIterator> void (InputIterator first, InputIterator last);
Requires: first, last are not iterators into *this.
Effects: inserts each element from the range [first,last) .
Complexity: At most N log(size()+N) (N is the distance from first to last)
void ( il);
Effects: inserts each element from the range [il.begin(), il.end().
Complexity: At most N log(size()+N) (N is the distance from il.begin() to il.end())
iterator ( nh);
Requires: nh is empty or this->get_allocator() == nh.get_allocator().
Effects/Returns: If nh is empty, has no effect and returns end(). Otherwise, inserts the element owned by nh and returns an iterator pointing to the newly inserted element. If a range containing elements with keys equivalent to nh.key() exists, the element is inserted at the end of that range. nh is always emptied.
Complexity: Logarithmic
iterator ( hint, nh);
Effects: Same as insert(node_type && nh)
but the element is inserted as close as possible to the position just prior to "hint".
Complexity: logarithmic in general, but amortized constant if the element is inserted right before "hint".
iterator ( p);
Effects: Erases the element pointed to by p.
Returns: Returns an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns end().
Complexity: Amortized constant time
size_type (const x);
Effects: If present, erases the element in the container with key equivalent to x.
Returns: Returns the number of erased elements (0/1).
Complexity: log(size()) + count(k)
iterator ( first, last);
Effects: Erases all the elements in the range [first, last).
Returns: Returns last.
Complexity: log(size())+N where N is the distance from first to last.
(const k);
Effects: Removes the first element in the container with key equivalent to k.
Returns: A node_type owning the element if found, otherwise an empty node_type.
Complexity: log(size()).
( position);
Effects: Removes the element pointed to by "position".
Returns: A node_type owning the element, otherwise an empty node_type.
Complexity: Amortized constant.
template<typename C2> void (multimap< Key, T, C2, Allocator, Options > & source);
Requires: this->get_allocator() == source.get_allocator().
Effects: Extracts each element in source and insert it into a using the comparison object of *this.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(size() + N) (N has the value source.size())
template<typename C2> void (multimap< Key, T, C2, Allocator, Options > && source);
Requires: this->get_allocator() == source.get_allocator().
Effects: Extracts each element in source and insert it into a using the comparison object of *this.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(size() + N) (N has the value source.size())
template<typename C2> void (map< Key, T, C2, Allocator, Options > & source);
Requires: this->get_allocator() == source.get_allocator().
Effects: Extracts each element in source and insert it into a using the comparison object of *this.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(size() + N) (N has the value source.size())
template<typename C2> void (map< Key, T, C2, Allocator, Options > && source);
Requires: this->get_allocator() == source.get_allocator().
Effects: Extracts each element in source and insert it into a using the comparison object of *this.
Postcondition: Pointers and references to the transferred elements of source refer to those same elements but as members of *this. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into *this, not into source.
Throws: Nothing unless the comparison object throws.
Complexity: N log(size() + N) (N has the value source.size())
void (multiset & x) ;
Effects: Swaps the contents of *this and x.
Throws: Nothing.
Complexity: Constant.
void () ;
Effects: erase(begin(),end()).
Postcondition: size() == 0.
Complexity: linear in size().
key_compare () ;
Effects: Returns the comparison object out of which a was constructed.
Complexity: Constant.
value_compare () ;
Effects: Returns an object of value_compare constructed out of the comparison object.
Complexity: Constant.
iterator (const x);
Returns: An iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.
Complexity: Logarithmic.
(const x) ;
Returns: A const iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.
Complexity: Logarithmic.
template<typename K> iterator (const K & x);
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: An iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.
Complexity: Logarithmic.
template<typename K> (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: A const_iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.
Complexity: Logarithmic.
size_type (const x) ;
Returns: The number of elements with key equivalent to x.
Complexity: log(size())+count(k)
template<typename K> size_type (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: The number of elements with key equivalent to x.
Complexity: log(size())+count(k)
bool (const x) ;
Returns: Returns true if there is an element with key equivalent to key in the container, otherwise false.
Complexity: log(size()).
template<typename K> bool (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: Returns true if there is an element with key equivalent to key in the container, otherwise false.
Complexity: log(size()).
iterator (const x);
Returns: An iterator pointing to the first element with key not less than x, or end() if such an element is not found.
Complexity: Logarithmic
(const x) ;
Returns: A const iterator pointing to the first element with key not less than x, or end() if such an element is not found.
Complexity: Logarithmic
template<typename K> iterator (const K & x);
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: An iterator pointing to the first element with key not less than x, or end() if such an element is not found.
Complexity: Logarithmic
template<typename K> (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: A const iterator pointing to the first element with key not less than x, or end() if such an element is not found.
Complexity: Logarithmic
iterator (const x);
Returns: An iterator pointing to the first element with key greater than x, or end() if such an element is not found.
Complexity: Logarithmic
(const x) ;
Returns: A const iterator pointing to the first element with key greater than x, or end() if such an element is not found.
Complexity: Logarithmic
template<typename K> iterator (const K & x);
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: An iterator pointing to the first element with key greater than x, or end() if such an element is not found.
Complexity: Logarithmic
template<typename K> (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Returns: A const iterator pointing to the first element with key greater than x, or end() if such an element is not found.
Complexity: Logarithmic
iterator, iterator > (const x);
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
(const x) ;
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
template<typename K> iterator, iterator > (const K & x);
Requires: This overload is available only if key_compare::is_transparent exists.
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
template<typename K> (const K & x) ;
Requires: This overload is available only if key_compare::is_transparent exists.
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
void ();
Effects: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
Complexity: Linear
multimap
friend functionsbool (const multimap & x, const multimap & y);
Effects: Returns true if x and y are equal
Complexity: Linear to the number of elements in the container.
bool (const multimap & x, const multimap & y);
Effects: Returns true if x and y are unequal
Complexity: Linear to the number of elements in the container.
bool (const multimap & x, const multimap & y);
Effects: Returns true if x is less than y
Complexity: Linear to the number of elements in the container.
bool (const multimap & x, const multimap & y);
Effects: Returns true if x is greater than y
Complexity: Linear to the number of elements in the container.
bool (const multimap & x, const multimap & y);
Effects: Returns true if x is equal or less than y
Complexity: Linear to the number of elements in the container.
bool (const multimap & x, const multimap & y);
Effects: Returns true if x is equal or greater than y
Complexity: Linear to the number of elements in the container.
void (multimap & x, multimap & y) ;
Effects: x.swap(y)
Complexity: Constant.