Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is an old version of boost. Click here for the latest version's documentation home page.
PrevUpHomeNext

Class template multimap

boost::interprocess::multimap

Synopsis

template<typename Key, typename T, typename Pred, typename Alloc> 
class 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 T                              mapped_type;           
  typedef Pred                           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; 
  typedef value_compare_impl             value_compare;         

  // construct/copy/destruct
  multimap(const Pred & = Pred(), const allocator_type & = allocator_type());
  template<typename InputIterator> 
    multimap(InputIterator, InputIterator, const Pred & = Pred(), 
             const allocator_type & = allocator_type());
  multimap(const multimap< Key, T, Pred, Alloc > &);
  multimap(unspecified);
  multimap& operator=(const multimap< Key, T, Pred, Alloc > &);
  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(multimap< Key, T, Pred, Alloc > &) ;
  void swap(unspecified) ;
  iterator insert(const value_type &) ;
  iterator insert(const std::pair< key_type, mapped_type > &) ;
  iterator insert(unspecified) ;
  iterator insert(iterator, const value_type &) ;
  iterator insert(iterator, const std::pair< key_type, mapped_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() ;
  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 &) ;
  std::pair< iterator, iterator > equal_range(const key_type &) ;
  const_iterator upper_bound(const key_type &) const;
  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>.

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<const Key, T>).

multimap public construct/copy/destruct

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

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

    Complexity: Constant.

  2. template<typename InputIterator> 
      multimap(InputIterator first, InputIterator last, 
               const Pred & comp = Pred(), 
               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.

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

    Effects: Copy constructs a multimap.

    Complexity: Linear in x.size().

  4. multimap(unspecified x);

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

    Complexity: Construct.

    Postcondition: x is emptied.

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

    Effects: Makes *this a copy of x.

    Complexity: Linear in x.size().

  6. multimap& operator=(unspecified x);

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

    Complexity: Constant.

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

  20. iterator insert(const std::pair< key_type, mapped_type > & x) ;

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

    Complexity: Logarithmic.

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

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

  23. iterator insert(iterator position, 
                    const std::pair< key_type, mapped_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.

  24. iterator insert(iterator position, unspecified 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.

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

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

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

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

  29. void clear() ;

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

    Postcondition: size() == 0.

    Complexity: linear in size().

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

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

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

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

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

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

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

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

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

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


PrevUpHomeNext