multiset

 Overview

The standard library provides multiset to store ordered elements with duplicates.

Details

multiset is basically a sorted array of duplicate elements that can be used to search and retrieve elements. Sorting is done by the Compare function provided in the template. 

Syntax

The syntax is as below. Template parameter T represents the datatype to store, Compare represents comparison function to compare elements and Alloc represents the allocator used for storage.

template <class Key, class Compare, class Alloc = allocator<Key> > 
class set;

Members

 It defines following types

Name	Description
key_type	The first template parameter (Key)
value_type	The first template parameter (Key)
key_compare	The second template parameter (Compare)
value_compare	The second template parameter (Compare)
allocator_type	The third template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	a bidirectional  iterator to value_type convertible to const_iterator
const_iterator	a bidirectional  iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

multiset can be graphically represented as below. It's basically a red-black tree. It holds values [1,2,3,4,5,1,3].

New elements can be added or removed or searched in the set. The default comparison function is less.

Complexity

The cost of Insertion or removal or search is O(Log(n)).

Functionality

Constructors

In following constructors use default allocator. Custom compare operations can be supplied. Custom allocators can be used by passing them as an additional argument. 

Name	Description
multiset()	Default Constructor. Example: //v:{} multiset<int> v();
multiset(InputIterator first, InputIterator last)	Constructs a multiset and copies the elements in the range. Example: int a[]{1,2,3,4,5,3,4,5}; //v:{1,2,3,3,4,4,5,5} multiset<int> v(begin(a),end(a));
multiset(const multiset& x)	copy constructor.
multiset(multiset&& x)	move constructor.
multiset(initializer_list<value_type> il)	initializer_list constructor. Example: //v:{1,2,3,3,4,4,5,5} multiset<int> v{1,2,3,4,5,3,4,5};

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the multiset. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //prints 1,2,3,3,4,4,5,5 for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
reverse_iterator  rbegin() reverse_iterator  rend()	Returns reverse_iterator   to reverse beginning and reverse end of the multiset. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //prints 5 5 4 4 3 3 2 1 for (auto itr=v.rbegin(); itr!=v.rend(); ++itr) cout << *itr << ' ';
const_iterator cbegin() const_iterator cend()	Returns const_iterator to beginning and end of the multiset. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //prints 1,2,3,3,4,4,5,5 for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Return const_reverse_iterator to reverse beginning and reverse end of the multiset. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //prints 5 5 4 4 3 3 2 1 for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements in the multiset. Example: multiset<int> v{1,2,3,4,5}; //prints 5 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether multiset is empty.

Element Access

Name	Description
iterator find(const value_type& val)	Returns iterator to the first element or end if not found. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //itr = v.begin()+1 auto itr = v.find(2); //itr = v.end() itr = v.find(6);
size_type count (const value_type& val)	Returns number of elements matching val. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //knt=2 auto knt =v.count(3); //knt=0 knt =v.count(6);
iterator lower_bound(const value_type& val) iterator upper_bound(const value_type& val)	Returns iterator to the first element matching val or end Returns iterator next to the last  element matching val or end. Note that end will be returned if matching element is the last in the set.
Example: multiset<int> v{1,2,3,3,4,4,5,5}; //itr = v.begin()+2 auto itr = v.lower_bound(3); //itr = v.begin()+4 itr = v.upper_bound(3);
pair<iterator,iterator>  equal_range(const value_type& val)	Returns a pair object containing lower_bound and upper_bound iterators matching value val. Example: multiset<int> v{1,2,3,3,4,4,5,5}; //p = {v.begin()+1,v.begin()+2} auto p = v.equal_range(2); //p = {v.begin()+6,v.end()} p = v.equal_range(5); //p = {v.end(),v.end()} p = v.equal_range(6);

Modifiers

Name	Description
void insert(InputIterator first, InputIterator last) iterator insert(const_iterator hintpos, const value_type& val) iterator  insert(const value_type& val) void insert(initializer_list<value_type> il)	Inserts the  elements in the range. Inserts an element initialized with val. hintpos, is used to scout for location.  Returns an iterator to the inserted element or existing element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted. Insert an element initialized with with val.  Returns a pair object containing iterator to the inserted element or existing element and bool with value true if a new value is inserted otherwise false. Insert elements with the contents of initializer_list.
Example: int a[]{1,2,3}; multiset<int> v{}; //(1) v:{1,2,3} v.insert(begin(a),end(a)); //(2) v:{1,2,3,3} //it=begin(v)+3 auto it = v.insert(v.end(),3); //(3) v:{1,2,3,3,4} //it=<begin(v)+4 it = v.insert(4); //(4) v:{1,2,3,3,4,4,5} v.insert({4,5});
iterator erase(const_iterator pos) iterator erase(const_iterator first, const_iterator last) size_type erase( const value_type& val)	Erases element at pos. Returns an iterator that points to the element that was  located after the last erased element. Erases elements in the range. Returns an iterator that points to the element that was  located after the last erased element.  Erases the elements of value val. Returns number of elements erased.
Example: T operator+ (T it, typename T::difference_type i) { advance(it,i); return it; } multiset<int> v{1,2,3,3,4,4,5,5}; //(1) // v:{1,2,3,4,4,5,5} //it = begin(v)+2 auto it = v.erase(cbegin(v)+2); //(2) // v:{1,2,3,5,5} //it = begin(v)+3 it = v.erase(v.lower_bound(4),v.upper_bound(4)); //(3) // v:{1,2,3} //knt=2 auto knt = v.erase(5);
void swap(multiset& v)	Swap content with v. Note T has to be same. Example: multiset<int> v{1,2,3}; multiset<int> v2{5,4}; //v2:{1,2,3} //v:{4,5} v2.swap(v);
void clear()	Clear contents of multiset. Example: multiset<int> v{1,2,3,4,5}; //v:{} v.clear();
iterator  emplace(Args ...arg)	Constructs and inserts an element using arg. After insertion, it returns an iterator to the  new element. Example: multiset<int> v{1,2,3,4,5}; //v:{1,2,3,3,4,5} //itr = v.begin()+3 auto itr = v.emplace(2); //v:{1,2,3,3,4,5,6} //itr = v.begin()+6 itr = v.emplace(6);
iterator emplace_hint(iterator hintpos, Args ...arg)	Constructs and attempts to insert an element at the hintpos using arg. After insertion, it returns an iterator to the first element of same value or to the new element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted. Example: multiset<int> v{1,2,3,4,5}; //v:{1,2,3,3,4,5} //itr = v.begin()+2 auto itr = v.emplace_hint(begin(v), 3); //v:{1,2,3,3,4,5,6} //itr = v.begin()+6 itr = v.emplace_hint(begin(v), 6);