Set in C++ STL

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 45 minutes

A set is an Associative container which contains a sorted set of unique objects of type Key. Each element may occur only once, so duplicates are not allowed.
There are four kind of Associative containers: set, multiset, map and multimap.
The value of the elements in a set cannot be modified once in the container, i.e., the elements are always constant. But they can be inserted or removed from the container.
set containers are generally slower than unordered_set containers in accessing individual elements by their key, but they allow the direct iteration on subsets based on their order.

Syntax

Below is definition of std::set from <set> header file :

template < 
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

Parameter :-

Key − Type of the element contained.
Key may be substituted by any other data type including user-defined type.
Allocators - These are objects responsible for encapsulating memory management. std::allocator is used when you want to separate allocation and do construction in two steps. It is also used when separate destruction and deallocation is done in two steps.All the STL containers in C++ have a type parameter Allocator that is by default std::allocator. The default allocator simply uses the operators new and delete to obtain and release memory.
Compare - A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines.
The set object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a set container can be equivalent.
This can be a function pointer or a function object. This defaults to less < Key>, which returns the same as applying the less-than operator (a < b). Aliased as member types set::key_compare and set::value_compare.

Member types

Following member types can be used as parameters or return type by member functions:

1.   key_type                   : Key-First template parameter   
2.   value_type                 : Key-First template parameter  
3.   reference                  : Allocator::reference     
                                 value_type& (for the default allocator:value_type&) 
4.   const_reference	        : Allocator::const_reference  
                                  const value_type& 
5.   pointer                    : Allocator::pointer 
                                  std::allocator_traits <Allocator>::pointer     
6.   const_pointer              : Allocator::const_pointer 
                                  std::allocator_traits <Allocator>::const_pointer
7.   iterator                   : BidirectionalIterator 
8.   const_iterator             : constant BidirectionalIterator    
9.   reverse_iterator           : std::reverse_iterator <iterator>   
10.  const_reverse_iterator     : std::reverse_iterator <const_iterator>  
11.  size_type                  :  Unsigned Integer Type (std::size_t)  
12.  difference_type            : Signed Integer Type (std::ptrdiff_t) 
13.  13.  key_compare	            : Compare   
14.  value_compare              : Compare   
15.  allocator_type             : Allocator

Basic functions associated with Set:

The commonly used functions are:

begin()
cbegin()
end()
size()
max_size()
empty()
insert()
erase()
emplace()
emplace_hint()

1. `begin()` :

begin() function is used to return an iterator pointing to the first element of the set container. begin() function returns a bidirectional iterator to the first element of the container.

Syntax :

setname.begin()

Parameters : No parameters are passed.
Returns : This function returns a bidirectional iterator pointing to the first element.

Errors and Exceptions :

It has a no exception throw guarantee.
Shows error when a parameter is passed.

Example :

#include <iostream> 
#include <set> 
using namespace std; 
   
int main() 
{ 
    // declaration of set container 
    set<int> myset{1, 2, 3, 4, 5}; 
      
    // using begin() to print set 
    for (auto it=myset.begin(); it != myset.end(); ++it) 
        cout << ' ' << *it; 
    return 0; 
}

Output:

1 2 3 4 5

2. `cbegin()` :

It is a built-in function in C++ STL which returns a constant iterator pointing to the first element in the container. The iterator cannot be used to modify the elements in the set container. The iterators can be increased or decreased to traverse the set accordingly.

Syntax :

constant_iterator set_name.cegin()

Parameters: The function does not accept any parameters.
Return value: The function returns a constant iterator pointing to the first element in the container.

Errors and Exceptions :

It never throws exceptions.

Example :

#include <iostream>
#include <set>

int main () {
   std::set<int> myset = {50,40,30,20,10};

   std::cout << "myset contains:";
   for (auto it = myset.cbegin(); it != myset.cend(); ++it)
      std::cout << ' ' << *it;

   std::cout << '\n';

   return 0;
}

Output :

myset contains: 10 20 30 40 50

3. `end()` :

It returns an iterator pointing to past the last element of the set container. Since it does not refer to a valid element, it cannot de-referenced end() function returns a bidirectional iterator.

Syntax :

setname.end()

Parameters : No parameters are passed.
Returns : This function returns a bidirectional iterator pointing to next of the last element.

Errors and Exceptions :

It has a no exception throw guarantee.
Shows error when a parameter is passed.

Example :

#include <iostream>
#include <set>

int main () {
   int myints[] = {50,40,30,20,10};
   std::set<int> myset (myints,myints+10);

   std::cout << "myset contains:";
   for (std::set<int>::iterator it = myset.begin(); it!=myset.end(); ++it)
      std::cout << ' ' << *it;

   std::cout << '\n';

   return 0;
}

Output :

myset contains: -107717047 0 1 10 20 30 40 50 29015

4. `size()` :

size() function is used to return the size of the set container or the number of elements in the set container.

Syntax:

set_name.size()

Return Value : It returns the number of elements in the set container.

Errors and Exceptions

It has a no exception throw guarantee.
Shows error when a parameter is passed.

Example :

#include <iostream>
#include <set>

int main () {
   std::set<int> myints;
   std::cout << "0. size: " << myints.size() << '\n';

   for (int i = 0; i < 5; ++i) myints.insert(i);
   std::cout << "1. size: " << myints.size() << '\n';

   myints.insert (200);
   std::cout << "2. size: " << myints.size() << '\n';

   myints.erase(10);
   std::cout << "3. size: " << myints.size() << '\n';

   return 0;
}

Output

0. size: 0
1. size: 5
2. size: 6
3. size: 6

5. `max_size()` :

It is a built-in function in C++ STL which returns the maximum number of elements a set container can hold.

Syntax:

set_name.max_size()

Parameters : This function does not accept any parameters.
Return Value : This function returns the maximum number of elements a set container can hold.

Errors and Exceptions

It never throws exceptions.

Example :

#include <iostream>
#include <set>

int main () {
   int i;
   std::set<int> myset;

   if (myset.max_size()>100) {
      for (i = 0; i < 100; i++) myset.insert(i);
      std::cout << "The set contains 100 elements.\n";
   }
   else std::cout << "The set could not hold 100 elements.\n";

   return 0;
}

Output :

The set contains 100 elements.

6. `empty()` :

empty() function is used to check if the set container is empty or not.

Syntax:

setname.empty()

Parameters : No parameters are passed.
Returns : True, if set is empty & False, Otherwise

Errors and Exceptions

It has a no exception throw guarantee.
Shows error when a parameter is passed.

Example :

#include <iostream>
#include <set>

int main () {
   std::set<int> myset;

   myset.insert(0);
   myset.insert(10);
   myset.insert(20);

   std::cout << "myset contains:";
   while (!myset.empty()) {
      std::cout << ' ' << *myset.begin();
      myset.erase(myset.begin());
   }
   std::cout << '\n';

   return 0;
}

Output :

   myset contains: 0 10 20

7. `insert()` :

It is a built-in function in C++ STL which insert elements in the set container or inserts the elements from a position to another position in the set to a different set.

Errors and Exceptions :

If a single element is to be inserted, there are no changes in the container in case of exception.

There are 3 ways to use thise set function :

i. `insert(const g)` :

Syntax:

iterator set_name.insert(element)

Parameters : The function accepts a mandatory parameter element which is to be inserted in the set container.
Return Value : The function returns an iterator pointing to the inserted element in the container.

Example :

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
  
    set<int> s; 
  
    // Function to insert elements 
    // in the set container 
    s.insert(1); 
    s.insert(4); 
    s.insert(2); 
    s.insert(5); 
    s.insert(3); 
  
    cout << "The elements in set are: "; 
    for (auto it = s.begin(); it != s.end(); it++) 
        cout << *it << " "; 
  
    return 0; 
}

Output :

The elements in set are: 1 2 3 4 5

ii. `iterator insert (iterator position, const g)` :

Syntax :

iterator set_name.insert(iterator position, element)

Parameters : The function accepts two parameter which are described below:
a. element : It specifies the element to be inserted in the set container.
b. position : It does not specify the position where the insertion is to be done, it only points to a position from where the searching operation is to be started for insertion to make the process faster. The insertion is done according to the order which is followed by the set container.
Return Value : The function returns an iterator pointing to the inserted element in the container.

Example :

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
  
    set<int> s; 
  
    // Function to insert elements 
    // in the set container 
    auto itr = s.insert(s.begin(), 1); 
  
    // the time taken to insertion 
    // is very less as the correct 
    // position for isnertion is given 
    itr = s.insert(itr, 4); 
    itr = s.insert(itr, 2); 
    itr = s.insert(itr, 5); 
    itr = s.insert(itr, 3); 
  
    cout << "The elements in set are: "; 
    for (auto it = s.begin(); it != s.end(); it++) 
        cout << *it << " "; 
  
    return 0; 
}

Output :

The elements in set are: 1 2 3 4 5

iii. `iterator insert(iterator position1, iterator position2)` :

Syntax :

iterator set_name.insert(iterator position1, iterator position2)

Parameters : The function accepts two parameters position1 and position2 which specifies the range of elements. All the elements in the range [position1, last) are inserted in another set container.
Return Value : The function returns a set which has all the elements in range [position1, last).

Example :

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
  
    set<int> s1; 
  
    // Function to insert elements 
    // in the set container 
    s1.insert(1); 
    s1.insert(4); 
    s1.insert(2); 
    s1.insert(5); 
    s1.insert(3); 
  
    cout << "The elements in set1 are: "; 
    for (auto it = s1.begin(); it != s1.end(); it++) 
        cout << *it << " "; 
  
    set<int> s2; 
  
    // Function to insert one set to another 
    // all elements from where 3 is to end is 
    // inserted to set2 
    s2.insert(s1.find(3), s1.end()); 
  
    cout << "\nThe elements in set2 are: "; 
    for (auto it = s2.begin(); it != s2.end(); it++) 
        cout << *it << " "; 
  
    return 0; 
}

Output :

The elements in set1 are: 1 2 3 4 5 
The elements in set2 are: 3 4 5

8. `erase()` :

erase() function is used to remove elements from a container from the specified position or range.

Syntax :

1. setname.erase(position)
2. setname.erase(startingposition, endingposition)

Parameters : Position of the element to be removed in the form of iterator or the range specified using start and end iterator.
**Result :**Elements are removed from the specified position of the container.

Errors and Exceptions :

It has a no exception throw guarantee, if the position is valid.
Shows undefined behaviour otherwise.

Example :

Removing element from particular position :-

#include <iostream> 
#include <set> 
  
using namespace std; 
  
int main() 
{ 
    // set declaration 
    set<int> myset{ 1, 2, 3, 4, 5 }; 
    set<int>::iterator it1, it2; 
  
    // defining it1 pointing to the first 
    // element and it2 to the last element 
    it1 = myset.begin(); 
    it2 = myset.end(); 
  
    // decrementing the it2 two times 
    it2--; 
    it2--; 
  
    // erasing elements within the range 
    // of it1 and it2 
    myset.erase(it1, it2); 
  
    // Printing the set 
    for (auto it = myset.begin(); 
        it != myset.end(); ++it) 
        cout << ' ' << *it; 
    return 0; 
}

Output:

4 5

Removing elements within a range :

#include <iostream> 
#include <set> 
  
using namespace std; 
  
int main() 
{ 
    // set declaration 
    set<int> myset{ 1, 2, 3, 4, 5 }; 
    set<int>::iterator it; 
  
    // defining iterator pointing 
    // to the first element 
    it = myset.begin(); 
  
    // erasing the first element 
    myset.erase(it); 
  
    // Printing the set 
    for (auto it = myset.begin(); 
        it != myset.end(); ++it) 
        cout << ' ' << *it; 
    return 0; 
}

Output:

2 3 4 5

9. `emplace()` :

This function is used to insert a new element into the set container, only if the element to be inserted is unique and does not already exists in the set.

Syntax

setname.emplace(value)

Parameters : The element to be inserted into the set is passed as the parameter.
**Result :**The parameter is added to the set if the set does not contain that element already.

Errors and Exceptions

It has a strong exception guarantee, therefore, no changes are made if an exception is thrown
Parameter should be of the same type as that of the container otherwise, an error is thrown

Example

#include <iostream>
#include <set>
#include <string>

int main () {
   std::set<std::string> myset;

   myset.emplace("foo");
   myset.emplace("bar");
   auto ret = myset.emplace("bar");

   if (!ret.second) std::cout << "bar already exists in myset\n";

   return 0;
}

Output

bar already exists in myset

10. `emplace_hint()` :

It is a built-in function in C++ STL which inserts a new element in the set. A position is passed in the parameter of the function which acts as a hint from where the searching operation starts before inserting the element at its current position. The position only helps the process to get faster, it does not decide where the new element is to be inserted. The new element is inserted following the property of the set container only.

Syntax:

set_name.emplace_hint(iterator position, value)

Parameters : The function accepts two mandatory parameters which are described below:
a. position : This parameter acts as a hint from where the searching operation is done before inserting the element at its current position. The position only helps the process to be faster, it does not decide where the new element is to be inserted. The new element is inserted following the property of the set container only.
b.value : This specifies the element to inserted in the set container. The value is inserted into the set if it is not present before.
Return Value : The function returns an iterator pointing to the position where the insertion is done. If the element passed in the parameter already exists, then it returns an iterator pointing to the position where the existing element is.

Errors and Exceptions

If an exception is thrown, there are no changes in the container.

Example

#include <iostream>
#include <set>
#include <string>

int main () {
   std::set<std::string> myset;
   auto it = myset.cbegin();

   myset.emplace_hint (it,"rabbit");
   it = myset.emplace_hint (myset.cend(),"floor");
   it = myset.emplace_hint (it,"parrot");
   it = myset.emplace_hint (it,"Mammal");

   std::cout << "myset contains:";
   for (const std::string& x: myset)
      std::cout << ' ' << x;
   std::cout << '\n';

   return 0;
}

Output

myset contains: Mammal floor parrot rabbit

Syntax

Parameter :-

Member types

Basic functions associated with Set:

1. begin() :

Syntax :

Errors and Exceptions :

Example :

Output:

2. cbegin() :

Syntax :

Errors and Exceptions :

Example :

Output :

3. end() :

Syntax :

Errors and Exceptions :

Example :

Output :

4. size() :

Syntax:

Errors and Exceptions

Example :

Output

5. max_size() :

Syntax:

Errors and Exceptions

Example :

Output :

6. empty() :

Syntax:

Errors and Exceptions

Example :

Output :

7. insert() :

Errors and Exceptions :

i. insert(const g) :

Syntax:

Example :

Output :

ii. iterator insert (iterator position, const g) :

Syntax :

Example :

Output :

iii. iterator insert(iterator position1, iterator position2) :

Syntax :

Example :

Output :

8. erase() :

Syntax :

Errors and Exceptions :

Example :

Output:

Output:

9. emplace() :

Syntax

Errors and Exceptions

Example

Output

10. emplace_hint() :

Syntax:

Errors and Exceptions

Example

Output

1. `begin()` :

2. `cbegin()` :

3. `end()` :

4. `size()` :

5. `max_size()` :

6. `empty()` :

7. `insert()` :

i. `insert(const g)` :

ii. `iterator insert (iterator position, const g)` :

iii. `iterator insert(iterator position1, iterator position2)` :

8. `erase()` :

9. `emplace()` :

10. `emplace_hint()` :