| Home | Libraries | People | FAQ | More

## Class template multimap

boost::container::multimap

## Synopsis

    // In header: <boost/container/map.hpp>

    template<typename Key, typename T, typename Compare = std::less<Key>,
             typename Allocator = std::allocator< std::pair< const Key, T> > >
    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 Compare                                                          key_compare;
      typedef std::pair< key_type, mapped_type >                               nonconst_value_type;

      // construct/copy/destruct
      multimap();
      explicit multimap(const Compare &,
                        const allocator_type & = allocator_type());
      template<typename InputIterator>
        multimap(InputIterator, InputIterator, const Compare & = Compare(),
                 const allocator_type & = allocator_type());
      template<typename InputIterator>
        multimap(ordered_range_t, InputIterator, InputIterator,
                 const Compare & = Compare(),
                 const allocator_type & = allocator_type());
      multimap(const multimap &);
      multimap(BOOST_RV_REF(multimap));
      multimap(const multimap &, const allocator_type &);
      multimap(BOOST_RV_REF(multimap), const allocator_type &);
      multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap));
      multimap& operator=(BOOST_RV_REF(multimap));

      // public member functions
      typedef BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type);
      typedef BOOST_CONTAINER_IMPDEF(value_compare_impl);
      typedef BOOST_CONTAINER_IMPDEF(tree_t::iterator);
      typedef BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const;
      typedef BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator);
      typedef BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const;
      typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl);
      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;
      iterator end();
      const_iterator end() const;
      reverse_iterator rbegin();
      const_reverse_iterator rbegin() const;
      reverse_iterator rend();
      const_reverse_iterator rend() const;
      const_iterator cbegin() const;
      const_iterator cend() const;
      const_reverse_iterator crbegin() const;
      const_reverse_iterator crend() const;
      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(BOOST_RV_REF(nonconst_value_type));
      iterator insert(BOOST_RV_REF(movable_value_type));
      iterator insert(const_iterator, const value_type &);
      iterator insert(const_iterator, const nonconst_value_type &);
      iterator insert(const_iterator, BOOST_RV_REF(nonconst_value_type));
      iterator insert(const_iterator, BOOST_RV_REF(movable_value_type));
      template<typename InputIterator> void insert(InputIterator, InputIterator);
      iterator erase(const_iterator);
      size_type erase(const key_type &);
      iterator erase(const_iterator, const_iterator);
      void swap(multimap &);
      void clear();
      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;
    };

## Description

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. For a map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.

Compare is the ordering function for Keys (e.g. std::less<Key>).

Allocator is the allocator to allocate the value_types (e.g. allocator< std::pair<const Key, T> >).

### `multimap` public construct/copy/destruct

1.     multimap();

   Effects: Default constructs an empty multimap.

   Complexity: Constant.

2.     explicit multimap(const Compare & comp,
                         const allocator_type & a = allocator_type());

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

   Complexity: Constant.

3.     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.

4.     template<typename InputIterator>
         multimap(ordered_range_t ordered_range_, 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.

5.     multimap(const multimap & x);

   Effects: Copy constructs a multimap.

   Complexity: Linear in x.size().

6.     multimap(BOOST_RV_REF(multimap) x);

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

   Complexity: Constant.

   Postcondition: x is emptied.

7.     multimap(const multimap & x, const allocator_type & a);

   Effects: Copy constructs a multimap.

   Complexity: Linear in x.size().

8.     multimap(BOOST_RV_REF(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.

9.     multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x);

   Effects: Makes *this a copy of x.

   Complexity: Linear in x.size().

10.     multimap& operator=(BOOST_RV_REF(multimap) x);

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

    Complexity: Constant.

### `multimap` public member functions

1.     typedef BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type);

2.     typedef BOOST_CONTAINER_IMPDEF(value_compare_impl);

3.     typedef BOOST_CONTAINER_IMPDEF(tree_t::iterator);

4.     typedef BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const;

5.     typedef BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator);

6.     typedef BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const;

7.     typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl);

8.     allocator_type get_allocator() const;

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

   Complexity: Constant.

9.     stored_allocator_type & get_stored_allocator();

   Effects: Returns a reference to the internal allocator.

   Throws: Nothing

   Complexity: Constant.

   Note: Non-standard extension.

10.     const stored_allocator_type & get_stored_allocator() const;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

11.     iterator begin();

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

    Throws: Nothing.

    Complexity: Constant.

12.     const_iterator begin() const;

    Effects: Returns a const_iterator to the first element contained in the container.

    Throws: Nothing.

    Complexity: Constant.

13.     iterator end();

    Effects: Returns an iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

14.     const_iterator end() const;

    Effects: Returns a const_iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

15.     reverse_iterator rbegin();

    Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

16.     const_reverse_iterator rbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

17.     reverse_iterator rend();

    Effects: Returns a reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

18.     const_reverse_iterator rend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

19.     const_iterator cbegin() const;

    Effects: Returns a const_iterator to the first element contained in the container.

    Throws: Nothing.

    Complexity: Constant.

20.     const_iterator cend() const;

    Effects: Returns a const_iterator to the end of the container.

    Throws: Nothing.

    Complexity: Constant.

21.     const_reverse_iterator crbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

22.     const_reverse_iterator crend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Throws: Nothing.

    Complexity: Constant.

23.     bool empty() const;

    Effects: Returns true if the container contains no elements.

    Throws: Nothing.

    Complexity: Constant.

24.     size_type size() const;

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

    Throws: Nothing.

    Complexity: Constant.

25.     size_type max_size() const;

    Effects: Returns the largest possible size of the container.

    Throws: Nothing.

    Complexity: Constant.

26.     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.

27.     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 in general, but amortized constant if t is inserted right before p.

28.     iterator insert(const value_type & x);

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

    Complexity: Logarithmic.

29.     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.

30.     iterator insert(BOOST_RV_REF(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.

31.     iterator insert(BOOST_RV_REF(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.

32.     iterator insert(const_iterator position, 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.

33.     iterator insert(const_iterator position, 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.

34.     iterator insert(const_iterator position, BOOST_RV_REF(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.

35.     iterator insert(const_iterator position, BOOST_RV_REF(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.

36.     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)

37.     iterator erase(const_iterator position);

    Effects: Erases the element pointed to by position.

    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

38.     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)

39.     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.

40.     void swap(multimap & x);

    Effects: Swaps the contents of *this and x.

    Throws: Nothing.

    Complexity: Constant.

41.     void clear();

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

    Postcondition: size() == 0.

    Complexity: linear in size().

42.     key_compare key_comp() const;

    Effects: Returns the comparison object out of which a was constructed.

    Complexity: Constant.

43.     value_compare value_comp() const;

    Effects: Returns an object of value_compare constructed out of the comparison object.

    Complexity: Constant.

44.     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.

45.     const_iterator find(const key_type & x) const;

    Returns: Allocator const iterator pointing to an element with the key equivalent to x, or end() if such an element is not found.

    Complexity: Logarithmic.

46.     size_type count(const key_type & x) const;

    Returns: The number of elements with key equivalent to x.

    Complexity: log(size())+count(k)

47.     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

48.     const_iterator lower_bound(const key_type & x) const;

    Returns: Allocator 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

49.     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

50.     const_iterator upper_bound(const key_type & x) const;

    Returns: Allocator const iterator pointing to the first element with key not less than x, or end() if such an element is not found.

    Complexity: Logarithmic

51.     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

52.     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