Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
unordered set

Unordered sets in C++

Educative Answers Team

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)O(1).

%19 node_2 Key 3 node_1 Key 2 node_1_1 Val 2 node_1->node_1_1 node_1_2 Val 3 node_1_1->node_1_2 node_0 Key 1 node_0_1 Val 1 node_0->node_0_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("Apple"); //add elements to set
  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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring