Set in C++ (STL)

In this lecture, we will discuss all about std::set in C++ Standard Template Library and how to use it.

What is std::set in STL?

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.

Features of std::set

  • A Set in C++, doesn’t allow duplicate elements i.e. it only contains unique elements.
  • A Set in C++, can contain element of any specified type. You can decide what type of items to store in Set and provide that as the template argument while creating the set object.
  • A std::set internally uses the balanced binary tree to store elements
  • By default std::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 <.
  • A 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).
  • Once an element is added to a 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.

How to create a Set object in C++ ?

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

  1. Include the Necessary Header:
#include <set>
  1. Declare a 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.

    How to Insert elements in a Set in C++ ?

    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.

    How to iterate through std::set in C++ ?

    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, 
    

    How to search an element in a Set in C++ ?

    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
    

    Why prefer 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.

    How Set compares the elements internally?

    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, 
    

    How to Remove Elements from Set in C++ ?

    The std::set offers three different ways to remove elements using the erase function:

    1. Erase Elements by Position in Set in C++:
    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}
    
    1. Erase Element by Value from a Set in C++:
    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}
    
    1. Erase Elements by Range from a Set C++:
    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.

    Summary

    We learned about the basic usage details of a Set in C++.

    Scroll to Top