In this lecture, we will discuss all about std::set
in C++ Standard Template Library and how to use it.
std::set
is an associative container in C++, provided by Standard Template Library. It holds items in a sorted way. It makes sure that each item is unique, meaning no duplicates are allowed.
std::set
internally uses the balanced binary tree to store elementsstd::set
uses the less than operator i.e. operator <
for comparing two elements while sorting them. Whereas, if user gives an external sorting criteria i.e. a comparator, while creating the set object, then it uses that instead of defaultless than operator i.e. operator <
.std::set
will keep the inserted elements in sorted order based on the assigned sorting criteria i.e. either by default criteria i.e. operator <
or by passed comparator (if passed).std::set
, it cannot be modified. This is because the value of the element in Set determines its position in the set. If we coluld modify an element directly, it could violate the set’s internal ordering based on the sorting criterion, leading to undefined behavior.To create a std::set
object in C++, first include the <set>
header and then declaring a set with a specific data type. Here’s how you can create set objects in C++:
#include <set>
std::set
with a Specific Type:std::set<data_type> setObject;
Here, the data_type
denotes the type of elements this set object can hold. It can be an int, string, char, or any other data type. Let’s see a practical example,
1. Creating an empty set of integers:
Here, we will create a empty set of integers.
#include <set> int main() { std::set<int> intSet; return 0; }
We can also create a set of strings like this,
std::set<std::string> words;
2. Initializing a set with some values:
We can also initialize a set object while creating using the default values in an initializer list. Like this,
#include <iostream> #include <set> int main() { // Create & Initialize a Set of Integers std::set<int> intSet = {1, 2, 3, 4, 5}; return 0; }
3. Creating a set of strings:
Let’s create a Set of Strings and initialize it.
#include <iostream> #include <set> #include <string> int main() { std::set<std::string> stringSet = {"apple", "banana", "cherry"}; return 0; }
Remember, elements in a std::set
are always sorted and unique, so if you add duplicates, they won’t be stored multiple times.
In C++, the std::set
class offers a member function named insert()
. This function takes a value as its argument and places it into the set. If the value already exists within the set, the insertion has no effect. Let’s see a complete example,
#include<iostream> #include<set> #include<string> int main() { std::set<std::string> setOfWords; // Lets insert four elements setOfWords.insert("first"); setOfWords.insert("second"); setOfWords.insert("third"); setOfWords.insert("first"); // Only 3 elements will be inserted std::cout<<"Set Size ="<< setOfWords.size() <<std::endl; // Iterate through all the elements // in a set and display the value. for (const auto& elem: setOfWords) { std::cout << elem << ", "; } std::cout<<"\n"; return 0; }
Output:
Set Size =3 first, second, third,
The set
class in C++ includes a size()
function, which gives the total count of elements in the set.
In the above example, when we called the setOfNumbers.size()
function, it returned 3. This is because std::set
ensures all elements are unique. We tried adding the string “first” twice, it only accepted once.
Additionally, std::set
utilizes the <
operator to compare elements. As a result, all elements are maintained in a sorted order. You can observe this in the output, where all strings appear in a sequence.
To iterate over each element in a set, we use iterators. Start with an iterator pointing at the beginning of the set using set::begin()
. Then, in a loop, keep moving the iterator forward until it reaches the point just after the last element, indicated by set::end()
. As you loop through, you can access and work with each element one by one. Let’s see the complete example,
#include<iostream> #include<set> int main() { // Create & Initialize a Set of Integers std::set<int> setObj = {11, 45, 33, 23, 10}; for (std::set<int>::iterator it = setObj.begin(); it!=setObj.end(); ++it) { std::cout << *it << ", "; } std::cout<< "\n"; return 0; }
Output:
10, 11, 23, 33, 45,
We can also iterate over a set using the range based for loop. For example,
#include<iostream> #include<set> int main() { // Create & Initialize a Set of Integers std::set<int> setObj = {11, 45, 33, 23, 10}; // Loop over set element using range based for-loop for (const auto& elem: setObj) { std::cout << elem << ", "; } std::cout<< "\n"; return 0; }
Output:
10, 11, 23, 33, 45,
If you want to find an element in a std::set
, you can use its find()
function:
iterator find (const value_type& val) const;
This function looks for an item in the set that matches val
. If it finds one, it gives back an iterator pointing to that item. If not, it gives an iterator pointing to the spot just after the last item, which is what set::end()
represents.
Let’s see the complete example,
#include<iostream> #include<set> #include<string> int main() { std::set<std::string> setOfWords; // Insert four elements in Set setOfWords.insert("first"); setOfWords.insert("second"); setOfWords.insert("third"); setOfWords.insert("first"); // Example 1: // Search for element "second in set using find() member function std::set<std::string>::iterator it = setOfWords.find("second"); // Check if iterator is valid if(it != setOfWords.end()) std::cout<<"'first' found"<<std::endl; else std::cout<<"'first' not found"<<std::endl; // Example 2: // Search for element "fourth" in set using find() member function it = setOfWords.find("fourth"); // Check if iterator is valid if(it != setOfWords.end()) std::cout<<"'fourth' found"<<std::endl; else std::cout<<"'fourth' not found"<<std::endl; return 0; }
Output:
'first' found 'fourth' not found
std::set::find
over the generic std::find
algorithm?The std::set::find
member function is specifically tailored for std::set
. Since std::set
internally uses a balanced binary search tree, its find
method can search more efficiently by leveraging this structure. On the other hand, the standard std::find
algorithm works linearly across containers. As a result, std::set::find
is typically much faster than std::find
when used with sets.
By default, std::set
in C++ uses the <
operator for element comparisons.
Internally, std::set
relies on a balanced binary tree. When inserting a new element, the container compares the new element with existing nodes to determine the correct position within the tree. If the element already exists in the tree, the insertion is skipped.
But, How Does it Determine Equality Using <
Alone?
You might wonder: if std::set
primarily uses the <
operator, how does it ascertain if two elements, say a
and b
, are identical? The answer lies in a simple logic:
– If both a < b
and b < a
are false, then std::set
concludes that a
and b
are equal.
A Practical Example:
Here’s a quick example to demonstrate how insertion works in std::set
:
#include <iostream> #include <set> void checkAndInsert(std::set<int>& setObj, int num) { if (setObj.insert(num).second) std::cout << "Number " << num << " inserted sucessfuly\n"; else std::cout << "Number " << num << " was already present in set\n"; } int main() { std::set<int> setOfNumbers; checkAndInsert(setOfNumbers, 2); checkAndInsert(setOfNumbers, 3); checkAndInsert(setOfNumbers, 2); checkAndInsert(setOfNumbers, 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,
The std::set
offers three different ways to remove elements using the erase
function:
iterator erase(const_iterator position);
This version removes the element pointed to by the given iterator position
.
Example:
std::set<int> numbers = {1, 2, 3, 4, 5}; auto it = numbers.find(3); if (it != numbers.end()) { numbers.erase(it); } // set now contains {1, 2, 4, 5}
size_type erase(const value_type& val);
This version removes the element with the specified value val
from the set. It returns the number of elements removed (which can be 0 or 1 since sets don’t have duplicates).
Example:
std::set<int> numbers = {1, 2, 3, 4, 5}; numbers.erase(3); // set now contains {1, 2, 4, 5}
iterator erase(const_iterator first, const_iterator last);
This version removes all elements in the range [first, last)
, i.e., starting from first
up to (but not including) last
.
Example:
std::set<int> numbers = {1, 2, 3, 4, 5}; auto start = numbers.find(2); auto end = numbers.find(4); numbers.erase(start, end); // numbers now contains {1, 4, 5}
All these overloaded versons of erase()
function in std::set
offers flexibility in erasing elements based on different requirements.
We learned about the basic usage details of a Set in C++.