| Home | Libraries | People | FAQ | More

## Class template flat_multimap

boost::interprocess::flat_multimap

## Synopsis

    template<typename Key, typename T, typename Pred, typename Alloc>
    class flat_multimap {
    public:
      // types
      typedef tree_t::key_type               key_type;
      typedef tree_t::value_type             value_type;
      typedef tree_t::pointer                pointer;
      typedef tree_t::const_pointer          const_pointer;
      typedef tree_t::reference              reference;
      typedef tree_t::const_reference        const_reference;
      typedef tree_t::value_compare          value_compare;
      typedef T                              mapped_type;
      typedef tree_t::key_compare            key_compare;
      typedef tree_t::iterator               iterator;
      typedef tree_t::const_iterator         const_iterator;
      typedef tree_t::reverse_iterator       reverse_iterator;
      typedef tree_t::const_reverse_iterator const_reverse_iterator;
      typedef tree_t::size_type              size_type;
      typedef tree_t::difference_type        difference_type;
      typedef tree_t::allocator_type         allocator_type;
      typedef tree_t::stored_allocator_type  stored_allocator_type;

      // construct/copy/destruct
      flat_multimap(const Pred & = Pred(),
                    const allocator_type & = allocator_type());
      template<typename InputIterator>
        flat_multimap(InputIterator, InputIterator, const Pred & = Pred(),
                      const allocator_type & = allocator_type());
      flat_multimap(const flat_multimap< Key, T, Pred, Alloc > &);
      flat_multimap(unspecified);
      flat_multimap& operator=(const flat_multimap< Key, T, Pred, Alloc > &);
      flat_multimap& operator=(unspecified);

      // public member functions
      key_compare key_comp() const;
      value_compare value_comp() const;
      allocator_type get_allocator() const;
      const stored_allocator_type & get_stored_allocator() const;
      stored_allocator_type & get_stored_allocator() ;
      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;
      bool empty() const;
      size_type size() const;
      size_type max_size() const;
      void swap(flat_multimap< Key, T, Pred, Alloc > &) ;
      void swap(unspecified) ;
      iterator insert(const value_type &) ;
      iterator insert(unspecified) ;
      iterator insert(iterator, const value_type &) ;
      iterator insert(iterator, unspecified) ;
      template<typename InputIterator> void insert(InputIterator, InputIterator) ;
      iterator erase(const_iterator) ;
      size_type erase(const key_type &) ;
      iterator erase(const_iterator, const_iterator) ;
      void clear() ;
      void shrink_to_fit() ;
      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;
      size_type capacity() const;
      void reserve(size_type) ;
    };

## Description

A flat_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 flat_multimap class supports random-access iterators.

A flat_multimap satisfies all of the requirements of a container and of a reversible container and of an associative container. For a flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T> (unlike std::multimap<Key, T> which value_type is std::pair<const Key, T>).

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

Alloc is the allocator to allocate the value_types (e.g. boost::interprocess:allocator< std::pair<Key, T>).

### `flat_multimap` public construct/copy/destruct

1.     flat_multimap(const Pred & comp = Pred(),
                     const allocator_type & a = allocator_type());

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

   Complexity: Constant.

2.     template<typename InputIterator>
         flat_multimap(InputIterator first, InputIterator last,
                       const Pred & comp = Pred(),
                       const allocator_type & a = allocator_type());

   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 comp and otherwise N logN, where N is last - first.

3.     flat_multimap(const flat_multimap< Key, T, Pred, Alloc > & x);

   Effects: Copy constructs a flat_multimap.

   Complexity: Linear in x.size().

4.     flat_multimap(unspecified x);

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

   Complexity: Construct.

   Postcondition: x is emptied.

5.     flat_multimap& operator=(const flat_multimap< Key, T, Pred, Alloc > & x);

   Effects: Makes *this a copy of x.

   Complexity: Linear in x.size().

6.     flat_multimap& operator=(unspecified mx);

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

   Complexity: Constant.

### `flat_multimap` public member functions

1.     key_compare key_comp() const;

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

   Complexity: Constant.

2.     value_compare value_comp() const;

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

   Complexity: Constant.

3.     allocator_type get_allocator() const;

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

   Complexity: Constant.

4.     const stored_allocator_type & get_stored_allocator() const;

5.     stored_allocator_type & get_stored_allocator() ;

6.     iterator begin() ;

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

   Throws: Nothing.

   Complexity: Constant.

7.     const_iterator begin() const;

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

   Throws: Nothing.

   Complexity: Constant.

8.     iterator end() ;

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

   Throws: Nothing.

   Complexity: Constant.

9.     const_iterator end() const;

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

   Throws: Nothing.

   Complexity: Constant.

10.     reverse_iterator rbegin() ;

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

    Throws: Nothing.

    Complexity: Constant.

11.     const_reverse_iterator rbegin() const;

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

    Throws: Nothing.

    Complexity: Constant.

12.     reverse_iterator rend() ;

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

    Throws: Nothing.

    Complexity: Constant.

13.     const_reverse_iterator rend() const;

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

    Throws: Nothing.

    Complexity: Constant.

14.     bool empty() const;

    Effects: Returns true if the container contains no elements.

    Throws: Nothing.

    Complexity: Constant.

15.     size_type size() const;

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

    Throws: Nothing.

    Complexity: Constant.

16.     size_type max_size() const;

    Effects: Returns the largest possible size of the container.

    Throws: Nothing.

    Complexity: Constant.

17.     void swap(flat_multimap< Key, T, Pred, Alloc > & x) ;

    Effects: Swaps the contents of *this and x. If this->allocator_type() != x.allocator_type() allocators are also swapped.

    Throws: Nothing.

    Complexity: Constant.

18.     void swap(unspecified x) ;

    Effects: Swaps the contents of *this and x. If this->allocator_type() != x.allocator_type() allocators are also swapped.

    Throws: Nothing.

    Complexity: Constant.

19.     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 it's inserted it might invalidate elements.

20.     iterator insert(unspecified x) ;

    Effects: Inserts a new value move-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 it's inserted it might invalidate elements.

21.     iterator insert(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 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 it's inserted it might invalidate elements.

22.     iterator insert(iterator position, unspecified x) ;

    Effects: Inserts a 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 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 it's inserted it might invalidate elements.

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

    Requires: i, j are not iterators into *this.

    Effects: inserts each element from the range [i,j) .

    Complexity: N log(size()+N) (N is the distance from i to j) search time plus N*size() insertion time.

    Note: If an element it's inserted it might invalidate elements.

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

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

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

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

27.     void clear() ;

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

    Postcondition: size() == 0.

    Complexity: linear in size().

28.     void shrink_to_fit() ;

    Effects

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

    Complexity: Linear to size().

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

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

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

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

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

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

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

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

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

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

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

38.     size_type capacity() const;

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

    Throws: Nothing.

    Complexity: Constant.

39.     void reserve(size_type count) ;

    Effects: If n is less than or equal to capacity(), 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 "count", iterators and references to to values might be invalidated.