C++ Set STL

 

The C++ Set is an associative container that contains a sorted set of unique objects.


Set Operators
  • begin - returns a reference iterator to the beginning of the set
  • clear - deletes all elements from the set
  • count - return the number of elements matching a given key
  • empty - returns 1 ( true ) if there is no element in the set else return 0 ( false ).
  • end - returns a reference iterator just past the last element of a set
  • equal_range - returns a reference iterators to the first and just past of the elements matching a specific key.
  • erase - deletes elements from a set
  • find - returns a reference iterator to specific elements which is given by the user.
  • insert - insert an item into a set
  • key_comp - returns the function that compares keys
  • lower_bound - returns a reference iterator to the first element greater than or equal to a certain value
  • max_size - outputs the maximum number of elements that the set can hold
  • rbegin - returns a reverse_iterator to the end of the set
  • rend - returns a reverse_iterator to the beginning of the set
  • size - outputs the number of items in the set
  • swap - swap the contents of this set with another set.
  • upper_bound - returns a reference iterator to the first element greater than a certain value
  • value_comp - returns the function that compares values

Implementation of clear(), empty(), insert(), begin(), end(), count(), lower_bound(), upper_bound()


#include<iostream>
#include<set>
using namespace std;

int main(){
// Create set named si-interger_set.
set<int> si;

// using clear()
si.clear();

cout<<"Is set is empty: "<<si.empty()<<"\n\n";
// insert 5 Element 4,6,7,9,1
si.insert(4);
si.insert(6);
si.insert(7);
si.insert(9);
si.insert(1);

// Printing all element from the set:
cout<<"Printing all the element from the set.\n";
set<int>::iterator iter;
for(iter=si.begin(); iter!=si.end(); iter++){
cout<<*iter<<" ";
}
cout<<"\n\n";
// lower_bound()
cout<<"Lower bound for 3: "<<*(si.lower_bound(3))<<"\n";
// upper_bound()
cout<<"Upper bound for 6: "<<*(si.upper_bound(6))<<"\n\n";
// Counting number of occurances of 7;
cout<<"Occurances of 7 in given set: "<<si.count(7)<<"\n";
return 0;
}

Output:


Is set is empty: 1

Printing all the element from the set.
1 4 6 7 9

Lower bound for 3: 4
Upper bound for 6: 7

Occurances of 7 in given set: 1

begin()

  • The begin() returns a reference iterator to the first element of the set. 
  • begin() runs in constant time O(1).

clear()

  • The clear() deletes all of the elements in the set. clear() runs in linear time O(n).

count()

  • This count() returns the number of occurrences of a given key value in the set. In a set, it will return 1 if the element is present else 0. In multiset, it will return the occurrences of a given key value in the multiset.
  • clear() runs in linear time O(1).

empty()

  • The empty() returns true (1) if the set has no elements, false(0) otherwise.

end()

  • The end() returns a reference iterator just past the end of the set.
  • Note that before you can access the last element of the set using an iterator that you get from a call to end(), you'll have to decrement the iterator first.

equal_range()

  • This function returns two reference iterators- one to the first element that contains the key, another to a point just after the last element that contains the key.

erase()

  • The erase() either erase the element at the position, erases the elements between start and end or erases all elements that have a value of key.

find()

  • The find() function returns a reference iterator to key, or an iterator to the end of the set if the key is not found.
  • find() runs in logarithmic time.

Implementation of erase() and find()


#include<iostream>
#include<set>
using namespace std;


int main(){
// Create set named si-interger_set.
set<int> si;


// insert 5 Element 4,6,7,9,1
si.insert(4);
si.insert(6);
si.insert(7);
si.insert(9);
si.insert(1);


// Let's erase the occurance of 6
if(find(si.begin(), si.end(), 6) != si.end()){
si.erase(find(si.begin(), si.end(), 6));
}


for(auto c: si){
cout<<c<<" ";
}
cout<<endl;

return 0;
}

Output:


1 4 7 9

insert()

  • The function insert() either:
    • inserts value after the element at position (where the position is really just a suggestion as to where the value should go since sets and maps are ordered) and return a reference iterator to that element.
    • inserts a range of elements from start to end.
    • inserts value, but only if the value doesn't already exist. The return value is an iterator to
    • the element inserted, and a boolean describing whether an insertion took place.

key_comp()

  • The key_comp() returns the function that compares keys.
  • key_comp() runs in constant time O(1).

lower_bound()

  • The lower_bound() returns an iterator to the first element which has a value greater than or equal to key.
  • lower_bound() runs in logarithmic time O(logn).

max_size()

  • The max_size() outputs the maximum number of elements that the set can hold.
  • The max_size() should not be confused with the size() or (C++ Strings) capacity()

rbegin()

  • The rbegin() function returns a reverse_iterator to the end of the current set.
  • rbegin() runs in constant time.

rend()

  • The rend() returns a reverse_iterator to the beginning of the current set.
  • rend() runs in constant time.

size()

  • The size() outputs the number of elements in the current set.

Implementation of size()


#include<iostream>
#include<set>
using namespace std;


int main(){
// Create set named si-interger_set.
set<int> si;


// insert 5 Element 4,6,7,9,1
si.insert(4);
si.insert(6);
si.insert(7);
si.insert(9);
si.insert(1);

cout<<"The size of set: "<<si.size()<<endl;

return 0;
}

Output:


The size of set: 5

swap()

  • The swap() function exchanges the elements of the current set with another set. 
  • This function operates in constant time.

Implementation of swap()


#include <iostream>
#include <set>
using namespace std;

int main() {
// Create set named si-interger_set.
set<int> si1, si2;

// insert 5 Element 4,6,7,9,1
si1.insert(4);
si1.insert(6);
si1.insert(7);
si1.insert(9);
si1.insert(1);

si2.insert(2);
si2.insert(5);

cout<<"Element in si1: ";
for(auto c: si1) cout<<c<<" ";
cout<<endl;

cout<<"Element in si2: ";
for(auto c: si2) cout<<c<<" ";
cout<<endl;

// swapping si1 with si2
si1.swap(si2);

cout<<"Element in after swap si1: ";
for(auto c: si1) cout<<c<<" ";
cout<<endl;

cout<<"Element in after swap si2: ";
for(auto c: si2) cout<<c<<" ";
cout<<endl;

return 0;
}

Output:


Element in si1: 1 4 6 7 9
Element in si2: 2 5
Element in after swap si1: 2 5
Element in after swap si2: 1 4 6 7 9

upper_bound()

  • Thi function upper_bound() returns a reference iterator to the first element in the set with a key greater than key.

value_comp()

  • The value_comp() returns the function that compares values.
  • value_comp() runs in constant time.

This is all for this article, if you have any doubt or there is an error in the content then do comment for which we will be thankful to you.

Thank You for Reading.


Related Pages which you may like to Read:

  1. std::lower_bound in C++ STL
  2. std::upper_bound in C++ STL
  3. std::equal_range in C++ STL
  4. std::binary_search in C++ STL