...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::container::flat_multiset
// In header: <boost/container/flat_set.hpp> template<typename T, typename Pred = std::less<T>, typename A = std::allocator<T> > 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 explicit flat_multiset(); explicit flat_multiset(const Pred &, const allocator_type & = allocator_type()); template<typename InputIterator> flat_multiset(InputIterator, InputIterator, const Pred & = Pred(), const allocator_type & = allocator_type()); template<typename InputIterator> flat_multiset(ordered_range_t, InputIterator, InputIterator, const Pred & = Pred(), const allocator_type & = allocator_type()); flat_multiset(const flat_multiset &); flat_multiset(BOOST_RV_REF(flat_multiset)); flat_multiset(const flat_multiset &, const allocator_type &); flat_multiset(BOOST_RV_REF(flat_multiset), const allocator_type &); flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset)); flat_multiset& operator=(BOOST_RV_REF(flat_multiset)); // 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(insert_const_ref_type); iterator insert(T &); template<typename U> iterator insert(const U &, unspecified = 0); iterator insert(BOOST_RV_REF(value_type)); iterator insert(const_iterator, insert_const_ref_type); iterator insert(const_iterator, T &); template<typename U> iterator insert(const_iterator, const U &, unspecified = 0); iterator insert(const_iterator, BOOST_RV_REF(value_type)); template<typename InputIterator> void insert(InputIterator, InputIterator); template<typename InputIterator> void insert(ordered_range_t, InputIterator, InputIterator); template<class... Args> iterator emplace(Args &&...); template<class... Args> iterator emplace_hint(const_iterator, Args &&...); 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); };
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/destructexplicit flat_multiset();
Effects: Default constructs an empty flat_multiset
.
Complexity: Constant.
explicit flat_multiset(const Pred & comp, 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());
template<typename InputIterator> flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Pred & comp = Pred(), const allocator_type & a = allocator_type());
Effects: Constructs an empty flat_multiset
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.
flat_multiset(const flat_multiset & x);
Effects: Copy constructs a flat_multiset
.
Complexity: Linear in x.size().
flat_multiset(BOOST_RV_REF(flat_multiset) mx);
Effects: Move constructs a flat_multiset
. Constructs *this using x's resources.
Complexity: Constant.
Postcondition: x is emptied.
flat_multiset(const flat_multiset & x, const allocator_type & a);
Effects: Copy constructs a flat_multiset
using the specified allocator.
Complexity: Linear in x.size().
flat_multiset(BOOST_RV_REF(flat_multiset) mx, const allocator_type & a);
Effects: Move constructs a flat_multiset
using the specified allocator. Constructs *this using x's resources.
Complexity: Constant if a == mx.get_allocator(), linear otherwise
flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x);
Effects: Makes *this a copy of x.
Complexity: Linear in x.size().
flat_multiset& operator=(BOOST_RV_REF(flat_multiset) mx);
Effects: Makes *this a copy of x.
Complexity: Linear in x.size().
flat_multiset
public member functionskey_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.
Throws: Nothing.
Complexity: Constant.
iterator insert(insert_const_ref_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.
iterator insert(T & x);
template<typename U> iterator insert(const U & u, unspecified = 0);
iterator insert(BOOST_RV_REF(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 is inserted it might invalidate elements.
iterator insert(const_iterator p, insert_const_ref_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 is inserted it might invalidate elements.
iterator insert(const_iterator position, T & x);
template<typename U> iterator insert(const_iterator position, const U & u, unspecified = 0);
iterator insert(const_iterator position, BOOST_RV_REF(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 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: At most N log(size()+N) (N is the distance from first to last) search time plus N*size() insertion time.
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 and must be ordered according to the predicate.
Effects: inserts each element from the range [first,last) .This function is more efficient than the normal range creation for ordered ranges.
Complexity: At most N log(size()+N) (N is the distance from first to last) search time plus N*size() insertion time.
Note: Non-standard extension. If an element is inserted it might invalidate elements.
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 if x is inserted right before p) plus insertion linear to the elements with bigger keys than x.
Note: If an element is inserted it might invalidate elements.
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: Tries to deallocate the excess of memory created
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.