Implementing the sets without C++ STL containers

28 Aug 2024 | 5 min read

A set is defined as a collection of elements where each element is unique. It is different from arrays as sets can have variable lengths. The element added to a set once cannot be changed. If we want to add the same modified number, delete the number and add the modified one in the set.

Following are the operations that can be performed on a set -

add(value) - This function adds an element in the set
intersectionSet(S) - Return the intersection of two sets in the set S
toArray() - Converts a set into an array of elements
contains(s) - Returns the set if an element to be searched is present in the set
displaySet() - Print the set from beginning to end
getSize() - To get the size of the set
unionSet(s) - To display the union of two sets with set s

Implementation of sets using BST

The set data structure internally implements BST (Binary Search Tree) data structure. Hence, we will add the elements in the tree and use this tree template to implement the Set.

Create a template of BST

In a tree, we have three members - the data of the node and the left and right pointers to the node. It is given as below -

After creating a tree, we insert the nodes in the tree using the insert() function. In a BST, the data that is less than root lies on the left side of the tree and the greater one lies on the right side of the tree.

The Function containsNode() used are for checking whether a node is present in the tree or not.

The function inorder() is used to print the inorder traversal of the BST.

Implement the BST template in the Set class

After we have created the BST for the internal working of the set, a set template is created to implement the BST. It has a root pointer node to store the data and the size variable returns the size of the set.

The Set class has a default constructor to initialize the root of BST as NULL and a copy constructor to copy a set into another set.

The function add() is used to add values in the set. It does not add the duplicate data in the set by calling the function containsNode(). If there is a new element it adds to the set.

The function contains() checks if a particular element is present in the set or not. It internally calls containsNode() in the BST.

The function displaySet() is used to print the set elements. It internally calls the inorder() function of the BST.

The function getSize() returns the size of the set.

Code

Output

A = { 1 2 3 }
A contains 3
A does not contain 4

Next TopicScope Resolution Operator in C++

← prev next →

We provides tutorials and interview questions of all technology like java tutorial, android, java frameworks

Contact info

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

C++ Tutorial

C++ Control Statement

C++ Functions

C++ Arrays

C++ Classes and Objects

C++ Constructors

C++ Inheritance

C++ Polymorphism

C++ Abstraction

C++ Namespaces

C++ Templates

C++ Strings

C++ Pointers

Signal Handling

C++ Exceptions

C++ File & Stream

C++ STL Tutorial

Interview Question

MCQ

C++ Programs

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ Manipulator

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ Misc

Implementing the sets without C++ STL containers

Implementation of sets using BST

Related Posts

Subscribe to Tpoint Tech

Contact info

Follow us

Tutorials

Interview Questions

Online Compiler