set

Overview

The standard library provides set to store ordered unique elements.

Details

set is basically a sorted array of unique 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 = less<Key>, 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

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

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

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the set. Example: set<int> v{1,2,3,4,5}; //prints 1 2 3 4 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 set. Example: set<int> v{1,2,3,4,5}; //prints 5 4 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 set. Example: set<int> v{1,2,3,4,5}; //prints 1 2 3 4 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 set. Example: set<int> v{1,2,3,4,5}; //prints 5 4 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 set. Example: set<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 set is empty.

Element Access

Name	Description
iterator find(const value_type& val)	Returns iterator to the first element or end if not found. Example: set<int> v{1,2,3,4,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: set<int> v{1,2,3,4,5}; //knt=1 auto knt =v.count(2); //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: set<int> v{1,2,3,4,5}; //itr = v.begin()+1 auto itr = v.lower_bound(2); //itr = v.begin()+2 itr = v.upper_bound(2); //itr = v.begin()+4 itr = v.lower_bound(5); //itr = v.end() itr = v.upper_bound(5); //itr = v.end() itr = v.lower_bound(6); //itr = v.end() itr = v.upper_bound(6);
pair<iterator,iterator>  equal_range ( const value_type& val)	Returns a pair object containing lower_bound and upper_bound iterators matching value val. Example: set<int> v{1,2,3,4,5}; //p.first = v.begin()+1 //p.second = v.begin()+2 auto p = v.equal_range(2); //p.first = v.begin()+4 //p.second = v.end() p = v.equal_range(5); //p.first = v.end() //p.second = 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) pair<iterator,bool>  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. 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}; set<int> v{}; //(1) v:{1,2,3,4} v.insert(begin(a),end(a)); //(2) v:{1,2,3,4} //it=begin(v)+3 auto it = v.insert(v.end(),4); //(3) v:{1,2,3,4,5} //p=<begin(v)+4,true> auto p = v.insert(5); //(4) v:{1,2,3,4,5,6} v.insert({6});
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: template<typename T> T operator+ (T it, typename T::difference_type i) { advance(it,i); return it; } set<int> v{1,2,3,4,5}; //(1) // v:{2,3,4,5} //it = begin(v) auto it = v.erase(cbegin(v)); //(2) // v:{2,3} //it = begin(v)+2 it = v.erase(begin(v)+2,cend(v)); //(3) // v:{3} //knt=1 auto knt = v.erase(2);
void swap(set& v)	Swap content with v. Note T has to be same. Example: set<int> v{1,2,3,4,5}; set<int> v2{5,4,3,2,1}; //v2:{1,2,3,4,5} //v:{1,2,3,4,5} v2.swap(v);
void clear()	Clear contents of set. Example: set<int> v{1,2,3,4,5}; //v:{} v.clear();
pair<iterator,bool> emplace(Args ...arg)	Constructs and inserts an element using arg. Returns a pair object containing an iterator and a boolean. If the insertion succeeded, the iterator points to the inserted element and the boolean will be true if. Otherwise the iterator points to the existing element and the boolean will be false. Example: set<int> v{1,2,3,4,5}; //p.first = v.begin()+2 //p.second = false auto p = v.emplace(2); //p.first = v.begin()+5 //p.second = true auto p = v.emplace(6);
iterator emplace_hint(iterator hintpos, Args ...arg)	Constructs and attempts to insert an element at the hintpos using arg. It returns an iterator to the new 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. Example: set<int> v{1,2,3,4,5}; //itr = v.begin()+1 auto itr = v.emplace_hint(begin(v), 2); //itr = v.begin()+5 itr = v.emplace_hint(begin(v), 6);