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 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:

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.

 

How to iterate through std::set:

You can use iterators i.e.

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,

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,

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,

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

Output:
first second third
first second

 

Click Here to Subscribe for more Articles / Tutorials like this.