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 AllocatorOrContainer = new_allocator< std::pair< Key, T> >

is either:

flat_multimap() noexcept(dtl::is_nothrow_default_constructible< AllocatorOrContainer >::value &&dtl::is_nothrow_default_constructible< Compare >::value);

Effects: Default constructs an empty flat_map.

Complexity: Constant.

explicit flat_multimap(const allocator_type & a);

Effects: Constructs an empty flat_multimap using the specified allocator.

Complexity: Constant.

explicit flat_multimap(const Compare & comp);

Effects: Constructs an empty flat_multimap using the specified comparison object .

Complexity: Constant.

flat_multimap(const Compare & comp, const allocator_type & a);

Effects: Constructs an empty flat_multimap using the specified comparison object and allocator.

Complexity: Constant.

template<typename InputIterator> 
  flat_multimap(InputIterator first, InputIterator last);

Effects: Constructs an empty flat_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> 
  flat_multimap(InputIterator first, InputIterator last, 
                const allocator_type & a);

Effects: Constructs an empty flat_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> 
  flat_multimap(InputIterator first, InputIterator last, const Compare & comp);

Effects: Constructs an empty flat_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> 
  flat_multimap(InputIterator first, InputIterator last, const Compare & comp, 
                const allocator_type & a);

Effects: Constructs an empty flat_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> 
  flat_multimap(ordered_range_t, InputIterator first, InputIterator last);

Effects: Constructs an empty flat_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> 
  flat_multimap(ordered_range_t, InputIterator first, InputIterator last, 
                const Compare & comp);

Effects: Constructs an empty flat_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> 
  flat_multimap(ordered_range_t, InputIterator first, InputIterator last, 
                const Compare & comp, const allocator_type & a);

Effects: Constructs an empty flat_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> 
  flat_multimap(ordered_range_t, InputIterator first, InputIterator last, 
                const allocator_type & a);

Effects: Constructs an empty flat_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.

flat_multimap(std::initializer_list< value_type > il);

Effects: Constructs an empty flat_map and inserts elements from the range [il.begin(), il.end()).

Complexity: Linear in N if the range [il.begin(), il.end()) is already sorted using the predicate and otherwise N logN, where N is last - first.

flat_multimap(std::initializer_list< value_type > il, 
              const allocator_type & a);

Effects: Constructs an empty flat_map using the specified allocator, and inserts elements from the range [il.begin(), il.end()).

Complexity: Linear in N if the range [il.begin(), il.end()) is already sorted using the predicate and otherwise N logN, where N is last - first.

flat_multimap(std::initializer_list< value_type > il, const Compare & comp);

Effects: Constructs an empty flat_map using the specified comparison object and inserts elements from the range [il.begin(), il.end()).

Complexity: Linear in N if the range [il.begin(), il.end()) is already sorted using the predicate and otherwise N logN, where N is last - first.

flat_multimap(std::initializer_list< value_type > il, const Compare & comp, 
              const allocator_type & a);

Effects: Constructs an empty flat_map using the specified comparison object and allocator, and inserts elements from the range [il.begin(), il.end()).

Complexity: Linear in N if the range [il.begin(), il.end()) is already sorted using the predicate and otherwise N logN, where N is last - first.

flat_multimap(ordered_range_t, std::initializer_list< value_type > il);

Effects: Constructs an empty flat_multimap 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.

flat_multimap(ordered_range_t, std::initializer_list< value_type > il, 
              const Compare & comp);

Effects: Constructs an empty flat_multimap 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.

flat_multimap(ordered_range_t, std::initializer_list< value_type > il, 
              const Compare & comp, const allocator_type & a);

Effects: Constructs an empty flat_multimap 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.

flat_multimap(const flat_multimap & x);

Effects: Copy constructs a flat_multimap.

Complexity: Linear in x.size().

flat_multimap(flat_multimap && x) noexcept(boost::container::dtl::is_nothrow_move_constructible< Compare >::value);

Effects: Move constructs a flat_multimap. Constructs *this using x's resources.

Complexity: Constant.

Postcondition: x is emptied.

flat_multimap(const flat_multimap & x, const allocator_type & a);

Effects: Copy constructs a flat_multimap using the specified allocator.

Complexity: Linear in x.size().

flat_multimap(flat_multimap && x, const allocator_type & a);

Effects: Move constructs a flat_multimap using the specified allocator. Constructs *this using x's resources.

Complexity: Constant if a == x.get_allocator(), linear otherwise.

flat_multimap & operator=(const flat_multimap & x);

Effects: Makes *this a copy of x.

Complexity: Linear in x.size().

flat_multimap & 
operator=(flat_multimap && x) noexcept((allocator_traits_type::propagate_on_container_move_assignment::value||allocator_traits_type::is_always_equal::value) &&boost::container::dtl::is_nothrow_move_assignable< Compare >::value);

Effects: this->swap(x.get()).

Complexity: Constant.

flat_multimap & operator=(std::initializer_list< value_type > il);

Effects: Assign content of il to *this

Complexity: Linear in il.size().

 BOOST_STATIC_ASSERT((dtl::is_same< std::pair< Key, T >, value_type >::value));

allocator_type get_allocator() const noexcept;

Effects: Returns a copy of the allocator that was passed to the object's constructor.

Complexity: Constant.

stored_allocator_type & get_stored_allocator() noexcept;

Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.

const stored_allocator_type & get_stored_allocator() const noexcept;

Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.

iterator begin() noexcept;

Effects: Returns an iterator to the first element contained in the container.

Throws: Nothing.

Complexity: Constant.

const_iterator begin() const noexcept;

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.

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.

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_iterator cbegin() const noexcept;

Effects: Returns a const_iterator to the first element contained in 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.

const_reverse_iterator crbegin() const noexcept;

Effects: Returns a const_reverse_iterator pointing to the beginning 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 noexcept;

Effects: Returns true if the container contains no elements.

Throws: Nothing.

Complexity: Constant.

size_type size() const noexcept;

Effects: Returns the number of the elements contained in the container.

Throws: Nothing.

Complexity: Constant.

size_type max_size() const noexcept;

Effects: Returns the largest possible size of the container.

Throws: Nothing.

Complexity: Constant.

size_type capacity() const noexcept;

Effects: Number of elements for which memory has been allocated. capacity() is always greater than or equal to size().

Throws: Nothing.

Complexity: Constant.

void reserve(size_type cnt);

Effects: If n is less than or equal to capacity(), or the underlying container has no reserve member, this call has no effect. Otherwise, it is a request for allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged.

Throws: If memory allocation allocation throws or T's copy constructor throws.

Note: If capacity() is less than "cnt", iterators and references to to values might be invalidated.

void shrink_to_fit();

Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to size().

iterator nth(size_type n) noexcept;

Requires: size() >= n.

Effects: Returns an iterator to the nth element from the beginning of the container. Returns end() if n == size().

Throws: Nothing.

Complexity: Constant.

Note: Non-standard extension

const_iterator nth(size_type n) const noexcept;

Requires: size() >= n.

Effects: Returns a const_iterator to the nth element from the beginning of the container. Returns end() if n == size().

Throws: Nothing.

Complexity: Constant.

Note: Non-standard extension

size_type index_of(iterator p) noexcept;

Requires: begin() <= p <= end().

Effects: Returns the index of the element pointed by p and size() if p == end().

Throws: Nothing.

Complexity: Constant.

Note: Non-standard extension

size_type index_of(const_iterator p) const noexcept;

Requires: begin() <= p <= end().

Effects: Returns the index of the element pointed by p and size() if p == end().

Throws: Nothing.

Complexity: Constant.

Note: Non-standard extension

template<class... Args> iterator emplace(Args &&... args);

Effects: Inserts an object of type T constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

template<class... Args> 
  iterator emplace_hint(const_iterator hint, 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 search time (constant time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

iterator insert(const value_type & x);

Effects: Inserts x and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

template<typename Pair> iterator insert(Pair && x);

Effects: Inserts a new value constructed from x and returns the iterator pointing to the newly inserted element.

Complexity: Logarithmic search time plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

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 search time (constant time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

template<typename Pair> iterator insert(const_iterator p, Pair && x);

Effects: Inserts a 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 search time (constant time if the value is to be inserted before p) plus linear insertion to the elements with bigger keys than x.

Note: If an element is inserted it might invalidate elements.

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: N log(N).

Note: If an element is inserted it might invalidate elements.

template<typename InputIterator> 
  void insert(ordered_range_t, InputIterator first, InputIterator last);

Requires: first, last are not iterators into *this.

Requires: [first ,last) must be ordered according to the predicate.

Effects: inserts each element from the range [first,last) if and only if there is no element with key equivalent to the key of that element. This function is more efficient than the normal range creation for ordered ranges.

Complexity: Linear.

Note: If an element is inserted it might invalidate elements.

Note: Non-standard extension.

void insert(std::initializer_list< value_type > il);

Effects: inserts each element from the range [il.begin(), il.end()) .

Complexity: N log(N).

Note: If an element is inserted it might invalidate elements.

void insert(ordered_range_t, std::initializer_list< value_type > il);

Requires: [il.begin(), il.end()) must be ordered according to the predicate.

Effects: inserts each element from the range [il.begin(), il.end()) if and only if there is no element with key equivalent to the key of that element. This function is more efficient than the normal range creation for ordered ranges.

Complexity: Linear.

Note: If an element is inserted it might invalidate elements.

Note: Non-standard extension.

template<typename C2> 
  void merge(flat_multimap< Key, T, C2, AllocatorOrContainer > & source);

Requires: this->get_allocator() == source.get_allocator().

Effects: Move-inserts each element from source into *this a using the comparison object of *this.

Complexity: Linear in this->size() + source.size().

Note: Invalidates all iterators and references.

template<typename C2> 
  void merge(flat_multimap< Key, T, C2, AllocatorOrContainer > && source);

Requires: this->get_allocator() == source.get_allocator().

Effects: Move-inserts each element from source into *this a using the comparison object of *this.

Complexity: Linear in this->size() + source.size().

Note: Invalidates all iterators and references.

template<typename C2> 
  void merge(flat_map< Key, T, C2, AllocatorOrContainer > & source);

Requires: this->get_allocator() == source.get_allocator().

Effects: Move-inserts each element from source into *this a using the comparison object of *this.

Complexity: Linear in this->size() + source.size().

Note: Invalidates all iterators and references.

template<typename C2> 
  void merge(flat_map< Key, T, C2, AllocatorOrContainer > && source);

Requires: this->get_allocator() == source.get_allocator().

Effects: Move-inserts each element from source into *this a using the comparison object of *this.

Complexity: Linear in this->size() + source.size().

Note: Invalidates all iterators and references.

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: Linear to the elements with keys bigger than p

Note: Invalidates elements with keys not less than the erased element.

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: Logarithmic search time plus erasure time linear to the elements with bigger keys.

iterator erase(const_iterator first, const_iterator last);

Effects: Erases all the elements in the range [first, last).

Returns: Returns last.

Complexity: size()*N where N is the distance from first to last.

Complexity: Logarithmic search time plus erasure time linear to the elements with bigger keys.

void swap(flat_multimap & x) noexcept(allocator_traits_type::is_always_equal::value &&boost::container::dtl::is_nothrow_swappable< Compare >::value);

Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Constant.

void clear() noexcept;

Effects: erase(begin(),end()).

Postcondition: size() == 0.

Complexity: linear in size().

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: An 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 find(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_iterator find(const K & x) const;

Requires: This overload is available only if key_compare::is_transparent exists.

Returns: An 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)

template<typename K> size_type count(const K & x) const;

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 contains(const key_type & x) const;

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 contains(const K & x) const;

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 lower_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 lower_bound(const key_type & x) const;

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> iterator lower_bound(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_iterator lower_bound(const K & x) const;

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

iterator upper_bound(const key_type & 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_iterator upper_bound(const key_type & x) const;

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 upper_bound(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_iterator upper_bound(const K & x) const;

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

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

template<typename K> std::pair< iterator, iterator > equal_range(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> 
  std::pair< const_iterator, const_iterator > equal_range(const K & x) const;

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

sequence_type extract_sequence();

Effects: Extracts the internal sequence container.

Complexity: Same as the move constructor of sequence_type, usually constant.

Postcondition: this->empty()

Throws: If secuence_type's move constructor throws

void adopt_sequence(sequence_type && seq);

Effects: Discards the internally hold sequence container and adopts the one passed externally using the move assignment.

Complexity: Assuming O(1) move assignment, O(NlogN) with N = seq.size()

Throws: If the comparison or the move constructor throws

void adopt_sequence(ordered_range_t, sequence_type && seq);

Requires: seq shall be ordered according to this->compare().

Effects: Discards the internally hold sequence container and adopts the one passed externally using the move assignment.

Complexity: Assuming O(1) move assignment, O(1)

Throws: If the move assignment throws

const sequence_type & sequence() const noexcept;

Effects: Returns a const view of the underlying sequence.

Complexity: Constant

Throws: Nothing

bool operator==(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x and y are equal

Complexity: Linear to the number of elements in the container.

bool operator!=(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x and y are unequal

Complexity: Linear to the number of elements in the container.

bool operator<(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x is less than y

Complexity: Linear to the number of elements in the container.

bool operator>(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x is greater than y

Complexity: Linear to the number of elements in the container.

bool operator<=(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x is equal or less than y

Complexity: Linear to the number of elements in the container.

bool operator>=(const flat_multimap & x, const flat_multimap & y);

Effects: Returns true if x is equal or greater than y

Complexity: Linear to the number of elements in the container.

void swap(flat_multimap & x, flat_multimap & y) noexcept(noexcept(x.swap(y)));

Effects: x.swap(y)

Complexity: Constant.