Class template flat_multiset

boost::interprocess::flat_multiset

Synopsis

// In header: <boost/interprocess/containers/flat_set.hpp>

template<typename T, typename Pred, typename Alloc> 
class flat_multiset {
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::key_compare            key_compare;           
  typedef tree_t::value_compare          value_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_multiset(const Pred & = Pred(), 
                const allocator_type & = allocator_type());
  template<typename InputIterator> 
    flat_multiset(InputIterator, InputIterator, const Pred & = Pred(), 
                  const allocator_type & = allocator_type());
  flat_multiset(const flat_multiset< T, Pred, Alloc > &);
  flat_multiset(flat_multiset< T, Pred, Alloc > &&);
  flat_multiset& operator=(const flat_multiset< T, Pred, Alloc > &);
  flat_multiset& operator=(flat_multiset< T, Pred, Alloc > &&);

  // 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;
  const_iterator cbegin() const;
  iterator end() ;
  const_iterator end() const;
  const_iterator cend() const;
  reverse_iterator rbegin() ;
  const_reverse_iterator rbegin() const;
  const_reverse_iterator crbegin() const;
  reverse_iterator rend() ;
  const_reverse_iterator rend() const;
  const_reverse_iterator crend() const;
  bool empty() const;
  size_type size() const;
  size_type max_size() const;
  void swap(flat_multiset &&) ;
  iterator insert(const value_type &) ;
  iterator insert(value_type &&) ;
  iterator insert(const_iterator, const value_type &) ;
  iterator insert(const_iterator, value_type &&) ;
  template<typename InputIterator> void insert(InputIterator, InputIterator) ;
  iterator emplace() ;
  iterator emplace_hint(const_iterator) ;
  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< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
  std::pair< iterator, iterator > equal_range(const key_type &) ;
  size_type capacity() const;
  void reserve(size_type) ;
};

Description

flat_multiset is a Sorted Associative Container that stores objects of type Key. flat_multiset is a Simple Associative Container, meaning that its value type, as well as its key type, is Key. flat_Multiset can store multiple copies of the same key value.

flat_multiset is similar to std::multiset but it's implemented like an ordered vector. This means that inserting a new element into a flat_multiset invalidates previous iterators and references

Erasing an element of a flat_multiset invalidates iterators and references pointing to elements that come after (their keys are equal or bigger) the erased element.

`flat_multiset` public construct/copy/destruct

flat_multiset(const Pred & comp = Pred(), 
              const allocator_type & a = allocator_type());

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

flat_multiset(const flat_multiset< T, Pred, Alloc > & x);

flat_multiset(flat_multiset< T, Pred, Alloc > && x);

flat_multiset& operator=(const flat_multiset< T, Pred, Alloc > & x);

flat_multiset& operator=(flat_multiset< T, Pred, Alloc > && mx);

`flat_multiset` public member functions

```
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.
```
allocator_type get_allocator() const;
```
Effects: Returns a copy of the Allocator that was passed to the object's constructor.

Complexity: Constant.

const stored_allocator_type & get_stored_allocator() const;

stored_allocator_type & get_stored_allocator() ;

```
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() ;
```
Effects: Returns an iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator end() const;
```
Effects: Returns a const_iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cend() const;
```
Effects: Returns a const_iterator to the end of the container.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rbegin() ;
```
Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rend() ;
```
Effects: Returns a reverse_iterator pointing to the end of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rend() const;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crend() const;
```
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.
```
void swap(flat_multiset && x) ;
```
Effects: Swaps the contents of *this and x. If this->allocator_type() != x.allocator_type() allocators are also swapped.

Throws: Nothing.

Complexity: Constant.
```
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.
```
iterator insert(value_type && x) ;
```
Effects: Inserts a new value_type 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.
```
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 search time (constant if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.

Note: If an element it's inserted it might invalidate elements.
```
iterator insert(const_iterator position, 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 search time (constant if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.

Note: If an element it's inserted it might invalidate elements.
```
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.
```
iterator emplace() ;
```

iterator emplace_hint(const_iterator hint) ;

```
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.
```
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 clear() ;
```
Effects: erase(a.begin(),a.end()).

Postcondition: size() == 0.

Complexity: linear in size().
```
void shrink_to_fit() ;
```
Effects
Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to size().
```
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.s
```
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< 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
```
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
```
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.
```
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.

Boost C++ Libraries