Mastering Fundamentals: C++ and Data Structures

A Set Data Structure (STL) In C++

Board Infinity
Board Infinity
A Set Data Structure (STL) In C++

    Header in C++

    C++ Pointers

    Displaying A to Z characters using a loop: C++ Program

    Working of Jump Statements in C++

    Inline Functions in C++

    Understanding Substr() Function in C++

    Constructor vs Destructor in C++

    Understanding Copy Constructor in C++

    Becoming Friends with Friend Function in C++

    How File Handling Works in C++

    A Detailed Overview of Macros in C++

    List in C++

    A Set Data Structure (STL) In C++

    A Quick Guide to Circular Linked List in C++

    Stack using Linked List in C++

    How to Sort a Vector in C++

    What are Priority Queues in C++?

    Guide To 5 Data Structures In C++

Introduction

In this post, we will discover what a set is, when and how to utilize it, as well as how it functions internally and the many set actions. With the help of examples, we will learn about the many STL functions that may be applied to the set. In C++, a set is just a standard template library (STL) container that is used anytime we need to keep distinct items (no duplicate values) and store them in a certain order. The set's elements can be added or deleted, but once they are added, they cannot be changed.

Syntax and Definition

To define a set, we must first utilize the STL set, then declare the data type of the set's elements in the angle brackets ( <>), followed by the set's name.

set<datatype> name_of_set;

If you want the elements to be sorted in descending order instead of ascending order, you must add greaterdatatype > along with the data type. By default, the set maintains the elements in ascending order.

Syntax:

set<datatype, greater<datatype>> name_of_set;

Since each value in the set serves as a key and the set doesn't enable indexing, each element of the set is distinct, meaning that no duplicate values may be placed in it. Since there can only be one index, the elements/values (keys) themselves are the indexes. Additionally, just the keys and values must be used to access the values in the set. The components of a set are also kept in sorted order. Whether the components are sorted in ascending or descending order may be specified by altering the syntax during the set definition.

In logarithmic time complexity, the elements in the set may be added, deleted, and searched. As soon as an element is added to a set, it becomes a constant and cannot be changed (its value cannot be altered). The binary search tree in C++ internally implements the set STL.

Begin and End functions of Set

#include<bits/stdc++.h>
using namespace std;

int main()
{
    set<int> s = {12,43,234,65,34,54,3,2,87,213,76,454};

    set<int>::iterator it;  // Creating iterator.
    it = s.begin();
    cout << "using begin() = "<<*it<<"\n";
    it = s.end();it--;
    cout << "using end() = "<<*it<<"\n";

    set<int>::reverse_iterator rit;  // Creating reverse iterator.
    rit = s.rbegin();
    cout << "using rbegin() = "<< *rit <<"\n";
    rit = s.rend();rit--;
    cout << "using rend() = "<< *rit <<"\n";

    return 0;
}



Output

using begin() = 2
using end() = 454
using rbegin() = 454
using rend() = 2

Insert, Delete and Swapping Operations

#include<bits/stdc++.h>
using namespace std;

int main() {
   
  set<int> s = {12,43,234,65,34,54,3,2,87,213,76,454};

  s.insert(9);
  cout << "set after inserting 9 is - " << "\n";
  for (auto i: s) {
    cout << i << " ";
  }
  cout << "\n";

  s.erase(234);
  cout << "set after removing 234 is - " << "\n";
  for (auto i: s) {
    cout << i << " ";
  }
  cout << "\n";

  s.emplace(69);
  cout << "set after emplacing 69 is - " << "\n";
  for (auto i: s) {
    cout << i << " ";
  }
  cout << "\n";

  set<int>s2 = {23,43,54,12,67,87,9,54,32,87,3,1}; // Creating a new set.
  swap(s, s2); // Swapping the contents of both the sets.
  cout << "the set s after swapping" << "\n";
  for (auto i: s) {
    cout << i << " ";
  }
  cout << "\n";
  cout << "the set s2 after swapping" << "\n";
  for (auto i: s2) {
    cout << i << " ";
  }
  cout << "\n";

  cout << "Size of the set before using set.clear() = " << s.size() << "\n";
  s.clear();
  cout << "Size of the set after using set.clear() = " << s.size() << "\n";
  return 0;
}

Output:
set after inserting 9 is -
2 3 9 12 34 43 54 65 76 87 213 234 454
set after removing 234 is -
2 3 9 12 34 43 54 65 76 87 213 454
set after emplacing 69 is -
2 3 9 12 34 43 54 65 69 76 87 213 454
the set s after swaping
1 3 9 12 23 32 43 54 67 87
the set s2 after swapping
2 3 9 12 34 43 54 65 69 76 87 213 454
Size of the set before using set.clear() = 10
Size of the set after using set.clear() = 0

find(), count(), upper_bound(), lower_bound() Functions

#include<bits/stdc++.h>
using namespace std;

int main() {
   
  set<int> s ={12,43,234,65,34,54,3,2,87,213,76,454};

  set<int>::iterator it;

  it = s.find(54);
  cout << "The iterator is pointing to - " << * it << "\n";

  if (s.count(234)) {
    cout << "The value is present in the set" << "\n";
  } else {
    cout << "The value is not present in the set" << "\n";
  }

  it = s.lower_bound(10);
  cout << "The lower_bound of 10 is " << * it << "\n";

  it = s.upper_bound(12);
  cout << "The upper_bound of 12 is " << * it << "\n";

  return 0;
}

Output

The iterator is pointing to - 54
The value is present in the set
The lower_bound of 10 is 12
The upper_bound of 12 is 34

write your code here: Coding Playground

Things to Remember

  • In C++, a set is a container from the standard template library (STL). The set's elements are distinct, ordered, and immutable.
  • The STL set should be used first when defining a set, followed by the name of the set and the data type of its components in angle brackets ( >).
  • The set holds the entries by default in descending order. For descending order, use greaterdatatype> in conjunction with the data type.
  • The BSTs in C++ serve as the internal implementation of the set STL.
  • Use the insert function and the set name to insert data: name of set.insert(data);
  • Erase function with the set name and the location(s) in the form of an iterator to delete data (s). name of set.erase(iterator);
  • Operations like begin, end, size, and empty in a set require O(1) time.
  • O(Log N)-time operations include insert, find, count, and upper bound and lower bound
  • In O(N) time, operations like erase and clear
  • In C++, operations like insertion and deletion in the set typically have a time complexity ofO(log n)