C++ Set example and Tutorial – Part 1

In this article we will discuss how to use std::set with default sorting criteria.

std::set – Introduction

std::set is an associative container and header that need to be include for it is,
#include<set>

Benefits and Features of std::set:

• It’s doesn’t allow duplicate elements i.e. it only contains unique elements.
• Std::set can contain element of any specified type in template argument i.e.

     std::set<int> // contains only int elements.
     class Sample;
     std::set<Sample> // contains only Sample class objects.

• std::set internally store elements in balanced binary tree.
• By default std::set uses the operator < for comparing two elements and but if user passes the external sorting criteria i.e. comparator then it uses that instead of default operator <.
• std::set will keep the inserted elements in sorted order based on the assigned sorting criteria i.e. either by default criteria operator < or by passed comparator (if passed).

Basic Example:

#include<iostream>
#include<set>
#include<string>
int main()
{
	std::set<std::string> setOfNumbers;

	// Lets insert four elements
	setOfNumbers.insert("first");
	setOfNumbers.insert("second");
	setOfNumbers.insert("third");
	setOfNumbers.insert("first");

	// Only 3 elements will be inserted
	std::cout<<"Set Size = "<<setOfNumbers.size()<<std::endl;

	// Iterate through all the elements in a set and display the value.
	for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
	    std::cout << ' ' << *it;
	std::cout<<"n";
	return 0;
}

Output:
Set Size = 3
first second third

setOfNumbers.size() in above example returns 3 because std::set only contains unique elements, so string “first” was added in the set only once and call to again insert “first” string was rejected.

It uses the operator < for comparison and keeps the all the elements in sorted order, in output above you can check that all strings are in sorted order.

[showads ad=inside_post]

How to iterate through std::set:

You can use iterators i.e.

for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
	    std::cout << ' ' << *it;

But you cannot modify the elements using iterators because if you modify the element value then internal data structure of std::set will get corrupt and it will not remain balanced binary search tree. Hence further additions and find operations will not work properly.

How to search an element in std::set:

Using find member function,

iterator find (const value_type& val) const;

It Searches the container for an element equivalent to val and returns an iterator to it if found, otherwise it returns an iterator to set::end.

std::set find example,

#include<iostream>
#include<set>
#include<string>
int main()
{
	std::set<std::string> setOfNumbers;

	// Lets insert four elements
	setOfNumbers.insert("first");
	setOfNumbers.insert("second");
	setOfNumbers.insert("third");
	setOfNumbers.insert("first");

	// Search for element in set using find member function
	std::set<std::string>::iterator it = setOfNumbers.find("second");
	if(it != setOfNumbers.end())
		std::cout<<"'first'  found"<<std::endl;
	else
		std::cout<<"'first' not found"<<std::endl;

	// Search for element in set using find member function
	it = setOfNumbers.find("fourth");
	if(it != setOfNumbers.end())
		std::cout<<"'fourth'  found"<<std::endl;
	else
		std::cout<<"'fourth' not found"<<std::endl;

	return 0;
}

Output:
‘first’ found
‘fourth’ not found

Why should we use std::set::find member method instead of std::find standard generic algorithm?

Because find member function knows its internal data structure is balance binary search tree and hence designed to operate on that only therefore it will take much lesser time then standard algorithm std::find.

How std::set verifies while insertion if element is already added or not:

By default std::set uses the operator < .

It internally maintains a binary balanced tree and during insertion it compares the new element with already present nodes and finds the right position of new element in tree. If that element is already present then it doesn’t insert the new element.

But wait a minute, if it uses the operator < for comparison of two elements then how it checks if two elements are equal or not with operator < ?

It uses the following logic to check if two elements like a and b are equal or not,

If a<b is false and b<a is false
Then it means a and b are equal.

Example to verify insertion in std::set,

#include<iostream>
#include<set>
std::set<int> setOfNumbers;
void checkAndInsert(int num)
{
  if(setOfNumbers.insert(num).second)
     std::cout<<"Number "<<num<<" inserted sucessfulyn";
 else
     std::cout<<"Number "<<num<<" was already present in setn";

}
int main()
{
    checkAndInsert(2);
    checkAndInsert(3);
    checkAndInsert(2);
    checkAndInsert(1);

   // Check the size of set
   std::cout<<setOfNumbers.size()<<std::endl;

   // Iterate through all the elements in a set and display the value.
   for (std::set<int>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
      std::cout << ' ' << *it;
   std::cout<<"n";
 return 0;
}

Output:
Number 2 inserted sucessfuly
Number 3 inserted sucessfuly
Number 2 was already present in set
Number 1 inserted sucessfuly
3
1 2 3

How to remove an element in std::set :

Using member function erase i.e.

There are three overloaded versions of erase member function,

iterator  erase (const_iterator position);
size_type erase (const value_type& val);
iterator  erase (const_iterator first, const_iterator last);

Let’s see an example to erase element in std::set,

#include<iostream>
#include<set>
#include<string>
int main()
{

	std::set<std::string> setOfNumbers;

	// Lets insert four elements
	setOfNumbers.insert("first");
	setOfNumbers.insert("second");
	setOfNumbers.insert("third");
	setOfNumbers.insert("first");

	// Iterate through all the elements in a set and display the value.
	for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
	    std::cout << ' ' << *it;

	std::cout<<std::endl;

	setOfNumbers.erase("third");

	// Iterate through all the elements in a set and display the value.
	for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
		    std::cout << ' ' << *it;

	std::cout<<std::endl;
	return 0;
}

Output:
first second third
first second