Related Tags

c++
unordered set

# Unordered sets in C++

Unordered sets can be defined for any inbuilt or user-defined data structure.

These sets are implemented using hash tables, where each entry is randomly added to the table to achieve a time complexity of $O(1)$.

## Methods

### 1. Using predefined Data Structures

The following code shows how unordered sets can be defined for strings.

A similar method can be used for any predefined data structure.

• data_type is the predefined data type e.g., string
• set_name is the name of the set
//declaring a set
unordered_set <data_type> set_name; 

The complete code for declaring and inserting values in an unordered set is given below.

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

int main() {
unordered_set <string> fruits; // declare string

cout<< fruits.empty() << endl; //check if set is empty

fruits.insert("Banana");
fruits.insert("Cantaloupe");

for (auto i: fruits) // print all the elemnts in set
cout<< i <<endl;

return 0;
}

### 2. Using user-defined Data Structures

Unordered sets can be implemented on user-defined data structures as well.

The following code shows how to declare an unordered set using user-defined data structures.

One key thing to remember is that the comparison function needs to be defined to let the compiler know how the keys will be compared. Without the function, the compiler will generate an error.

Hash functions also need to be defined for the given data type.

Unordered sets can be created in the following way:

• data_type is the user-defined data structure
• data_hash_function is the hash function that will be used
• set_name is the name of the set
// This method declares an unordered set using the user-defined data type and user-defined hash function
unordered_set (data_type, data_hash_function) set_name; 

The complete code for defining and inserting elements is given below.

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

class fruits{ //declare a class
public:
string name;
string color;
//This is the comparison operator.
bool operator==(const fruits &f) const
{
return (this->name == f.name);
}
};
//create a class to produce the hash that we will use
class fruits_hash{
public:
size_t operator() (const fruits & f) const
{
return f.name.length();
}
};
int main() {
//declare objects of class fruits
fruits f1 {"Apple", "red"};
fruits f2 {"Banana", "yellow"};
//declare unordered set
unordered_set <fruits, fruits_hash> my_fruits;
//insert objects to set
my_fruits.insert(f1);
my_fruits.insert(f2);
//print set
for (auto i: my_fruits)
cout<< "Name: " << i.name << ", Color: " << i.color <<endl;

return 0;
}

RELATED TAGS

c++
unordered set