...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::container::multimap
// In header: <boost/container/map.hpp> template<typename Key, typename T, typename Compare = std::less<Key>, typename Allocator = new_allocator< std::pair< const Key, T> >, typename MultiMapOptions = tree_assoc_defaults> class multimap { public: // types typedef Key key_type; typedef T mapped_type; typedef std::pair< const Key, T > value_type; typedef boost::container::allocator_traits< Allocator >::pointer pointer; typedef boost::container::allocator_traits< Allocator >::const_pointer const_pointer; typedef boost::container::allocator_traits< Allocator >::reference reference; typedef boost::container::allocator_traits< Allocator >::const_reference const_reference; typedef boost::container::allocator_traits< Allocator >::size_type size_type; typedef boost::container::allocator_traits< Allocator >::difference_type difference_type; typedef Allocator allocator_type; typedef implementation_defined stored_allocator_type; typedef implementation_defined value_compare; typedef Compare key_compare; typedef implementation_defined iterator; typedef implementation_defined const_iterator; typedef implementation_defined reverse_iterator; typedef implementation_defined const_reverse_iterator; typedef std::pair< key_type, mapped_type > nonconst_value_type; typedef implementation_defined movable_value_type; // construct/copy/destruct multimap(); explicit multimap(const Compare &, const allocator_type & = allocator_type()); explicit multimap(const allocator_type &); template<typename InputIterator> multimap(InputIterator, InputIterator, const Compare & = Compare(), const allocator_type & = allocator_type()); template<typename InputIterator> multimap(InputIterator, InputIterator, const allocator_type &); template<typename InputIterator> multimap(ordered_range_t, InputIterator, InputIterator, const Compare & = Compare(), const allocator_type & = allocator_type()); multimap(std::initializer_list< value_type >, const Compare & = Compare(), const allocator_type & = allocator_type()); multimap(std::initializer_list< value_type >, const allocator_type &); multimap(ordered_range_t, std::initializer_list< value_type >, const Compare & = Compare(), const allocator_type & = allocator_type()); multimap(const multimap &); multimap(multimap &&); multimap(const multimap &, const allocator_type &); multimap(multimap &&, const allocator_type &); multimap & operator=(const multimap &); multimap & operator=(multimap &&) noexcept(condition); multimap & operator=(std::initializer_list< value_type >); // public member functions allocator_type get_allocator() const; stored_allocator_type & get_stored_allocator(); const stored_allocator_type & get_stored_allocator() const; iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end() noexcept; const_iterator end() const noexcept; const_iterator cend() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; const_reverse_iterator crbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_reverse_iterator crend() const noexcept; bool empty() const; size_type size() const; size_type max_size() const; template<class... Args> iterator emplace(Args &&...); template<class... Args> iterator emplace_hint(const_iterator, Args &&...); iterator insert(const value_type &); iterator insert(const nonconst_value_type &); iterator insert(nonconst_value_type &&); iterator insert(movable_value_type &&); iterator insert(const_iterator, const value_type &); iterator insert(const_iterator, const nonconst_value_type &); iterator insert(const_iterator, nonconst_value_type &&); iterator insert(const_iterator, movable_value_type &&); template<typename InputIterator> void insert(InputIterator, InputIterator); void insert(std::initializer_list< value_type >); iterator erase(const_iterator); size_type erase(const key_type &); iterator erase(const_iterator, const_iterator); key_compare key_comp() const; value_compare value_comp() const; iterator find(const key_type &); const_iterator find(const key_type &) const; size_type count(const key_type &) const; iterator lower_bound(const key_type &); const_iterator lower_bound(const key_type &) const; iterator upper_bound(const key_type &); const_iterator upper_bound(const key_type &) const; std::pair< iterator, iterator > equal_range(const key_type &); std::pair< const_iterator, const_iterator > equal_range(const key_type &) const; void rebalance(); // friend functions friend bool operator==(const multimap &, const multimap &); friend bool operator!=(const multimap &, const multimap &); friend bool operator<(const multimap &, const multimap &); friend bool operator>(const multimap &, const multimap &); friend bool operator<=(const multimap &, const multimap &); friend bool operator>=(const multimap &, const multimap &); friend void swap(multimap &, multimap &); // public data members void swap(multiset &x) noexcept(allocator_traits_type void clear; };
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 = std::less<Key>
is the ordering function for Keys (e.g. std::less<Key>).
typename Allocator = new_allocator< std::pair< const Key, T> >
is the allocator to allocate the value_type
s (e.g. allocator< std::pair<const Key, T> > ).
typename MultiMapOptions = tree_assoc_defaults
is an packed option type generated using using boost::container::tree_assoc_options
.
multimap
public
construct/copy/destructmultimap();
Effects: Default constructs an empty multimap.
Complexity: Constant.
explicit multimap(const Compare & comp, const allocator_type & a = allocator_type());
Effects: Constructs an empty multimap using the specified allocator.
Complexity: Constant.
explicit multimap(const allocator_type & a);
Effects: Constructs an empty multimap using the specified comparison object and allocator.
Complexity: Constant.
template<typename InputIterator> multimap(InputIterator first, InputIterator last, const Compare & comp = Compare(), const allocator_type & a = allocator_type());
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 comp and otherwise N logN, where N is last - first.
template<typename InputIterator> multimap(InputIterator first, InputIterator last, const allocator_type & 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 comp and otherwise N logN, where N is last - first.
template<typename InputIterator> multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare & comp = Compare(), const allocator_type & a = allocator_type());
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.
multimap(std::initializer_list< value_type > il, const Compare & comp = Compare(), const allocator_type & a = allocator_type());
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 comp and otherwise N logN, where N is il.first() - il.end().
multimap(std::initializer_list< value_type > il, const allocator_type & 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 comp and otherwise N logN, where N is il.first() - il.end().
multimap(ordered_range_t, std::initializer_list< value_type > il, const Compare & comp = Compare(), const allocator_type & a = allocator_type());
Effects: Constructs an empty set using the specified comparison object and allocator, 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.
multimap(const multimap & x);
Effects: Copy constructs a multimap.
Complexity: Linear in x.size().
multimap(multimap && x);
Effects: Move constructs a multimap. Constructs *this using x's resources.
Complexity: Constant.
Postcondition: x is emptied.
multimap(const multimap & x, const allocator_type & a);
Effects: Copy constructs a multimap.
Complexity: Linear in x.size().
multimap(multimap && x, const allocator_type & 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 & operator=(const multimap & x);
Effects: Makes *this a copy of x.
Complexity: Linear in x.size().
multimap & operator=(multimap && x) noexcept(condition);
Effects: this->swap(x.get()).
Complexity: Constant.
multimap & operator=(std::initializer_list< value_type > il);
Effects: Assign content of il to *this.
multimap
public member functionsallocator_type get_allocator() const;
Effects: Returns a copy of the allocator that was passed to the object's constructor.
Complexity: Constant.
stored_allocator_type & get_stored_allocator();
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
const stored_allocator_type & get_stored_allocator() const;
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
iterator begin();
Effects: Returns an iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant
const_iterator begin() const;
Effects: Returns a const_iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant.
const_iterator cbegin() const;
Effects: Returns a const_iterator to the first element contained in the container.
Throws: Nothing.
Complexity: Constant.
iterator end() noexcept;
Effects: Returns an iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
const_iterator end() const noexcept;
Effects: Returns a const_iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
const_iterator cend() const noexcept;
Effects: Returns a const_iterator to the end of the container.
Throws: Nothing.
Complexity: Constant.
reverse_iterator rbegin() noexcept;
Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator rbegin() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator crbegin() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.
Throws: Nothing.
Complexity: Constant.
reverse_iterator rend() noexcept;
Effects: Returns a reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator rend() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator crend() const noexcept;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.
Throws: Nothing.
Complexity: Constant.
bool empty() const;
Effects: Returns true if the container contains no elements.
Throws: Nothing.
Complexity: Constant.
size_type size() const;
Effects: Returns the number of the elements contained in the container.
Throws: Nothing.
Complexity: Constant.
size_type max_size() const;
Effects: Returns the largest possible size of the container.
Throws: Nothing.
Complexity: Constant.
template<class... Args> iterator emplace(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<class... Args> iterator emplace_hint(const_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 insert(const value_type & x);
Effects: Inserts x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator insert(const nonconst_value_type & x);
Effects: Inserts a new value constructed from x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator insert(nonconst_value_type && x);
Effects: Inserts a new value move-constructed from x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator insert(movable_value_type && x);
Effects: Inserts a new value move-constructed from x and returns the iterator pointing to the newly inserted element.
Complexity: Logarithmic.
iterator insert(const_iterator p, const value_type & 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 insert(const_iterator p, const nonconst_value_type & 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.
iterator insert(const_iterator p, nonconst_value_type && 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.
iterator insert(const_iterator p, movable_value_type && 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 InputIterator> void insert(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 insert(std::initializer_list< value_type > 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 erase(const_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 erase(const key_type & x);
Effects: Erases all elements in the container with key equivalent to x.
Returns: Returns the number of erased elements.
Complexity: log(size()) + count(k)
iterator erase(const_iterator first, const_iterator 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.
key_compare key_comp() const;
Effects: Returns the comparison object out of which a was constructed.
Complexity: Constant.
value_compare value_comp() const;
Effects: Returns an object of value_compare constructed out of the comparison object.
Complexity: Constant.
iterator find(const key_type & 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_iterator find(const key_type & x) const;
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 count(const key_type & x) const;
Returns: The number of elements with key equivalent to x.
Complexity: log(size())+count(k)
iterator lower_bound(const key_type & x);
Returns: An iterator pointing to the first element with key not less than k, or a.end() if such an element is not found.
Complexity: Logarithmic
const_iterator lower_bound(const key_type & x) const;
Returns: A const iterator pointing to the first element with key not less than k, or a.end() if such an element is not found.
Complexity: Logarithmic
iterator upper_bound(const key_type & 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_iterator upper_bound(const key_type & x) const;
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
std::pair< iterator, iterator > equal_range(const key_type & x);
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
std::pair< const_iterator, const_iterator > equal_range(const key_type & x) const;
Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Complexity: Logarithmic
void rebalance();
Effects: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
Complexity: Linear
multimap
friend functionsfriend bool operator==(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.
friend bool operator!=(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.
friend bool operator<(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.
friend bool operator>(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.
friend bool operator<=(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.
friend bool operator>=(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.
friend void swap(multimap & x, multimap & y);
Effects: x.swap(y)
Complexity: Constant.
multimap
public
public data membersvoid swap(multiset &x) noexcept(allocator_traits_type void clear;
Effects: x.swap(y)
Complexity: Constant.
Effects: Swaps the contents of *this and x.
Throws: Nothing.
Complexity: Constant. Effects: erase(a.begin(),a.end()).
Postcondition: size() == 0.
Complexity: linear in size().