unordered_set in C++
In this article, we will discuss the unordered_set in C++ with its properties, syntax, examples, and several methods.
In C++, a hash set is an unordered collection of unique elements implemented as a container that uses a hash function to store and retrieve elements efficiently. It is part of the C++ Standard Library and is provided through the unordered_set class template. A hash set has several advantages, such as fast insertion, deletion, and lookup operations. It makes it suitable for scenarios where fast element retrieval is essential, and the order of elements is not significant.
Properties of the unordered_set:
There are several properties of the unordered_set in C++. Some main properties of the unordered_set are as follows:
Uniqueness: Elements in an unordered_set are unique, meaning duplicate elements are automatically ignored during insertion. It ensures that each element appears in the set only once.
Hash Function: The set uses a hash function to efficiently organize elements based on their values. It enables fast retrieval and searching operations, as elements are stored in buckets corresponding to their hash values.
Constant-Time Operations: On average, insertion, deletion, and search operations take constant time complexity of O(1). It means that the time to perform these operations does not depend on the number of elements in the set.
Unordered Nature: Unlike other containers, like a set, the elements in unordered_set are not sorted in any specific order. The order of elements can change dynamically based on the internal hash table's resizing.
Dynamic Resizing: As the number of elements in the set grows, the internal hash table may need to resize to maintain efficient operations. This process is known as rehashing.
No Indexing: Unlike arrays or vectors, elements in an unordered_set cannot be accessed directly using an index. Instead, you can use iterators or the find method to access and manipulate elements.
Example:
Let's take a program to illustrate the unordered_set in C++.
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
int main() {
unordered_set<string>shoppingList;
// Add items to the shopping list
shoppingList.insert("laptop");
shoppingList.insert("iphone");
shoppingList.insert("earpods");
shoppingList.insert("watch");
// Display the initial shopping list
cout<< "Initial Shopping List:" <<endl;
for (const string&item :shoppingList) {
cout<< item <<endl;
}
// Check if an item is already in the shopping list
string newItem = "earpods";
if (shoppingList.count(newItem) > 0) {
cout<<newItem<< " is already in the shopping list." <<endl;
} else {
cout<<newItem<< " is not in the shopping list. Adding it." <<endl;
shoppingList.insert(newItem);
}
// Remove an item from the shopping list
string removeItem = "iphone";
if (shoppingList.erase(removeItem) > 0) {
cout<<removeItem<< " has been removed from the shopping list." <<endl;
} else {
cout<<removeItem<< " is not in the shopping list." <<endl;
}
// Display the updated shopping list
cout<< "Updated Shopping List:" <<endl;
for (const string&item :shoppingList) {
cout<< item <<endl;
}
return 0;
}
Output:
![unordered_set in C++](https://static.tutorialandexample.com/cpp/unordered-set-in-cpp1.png)
Explanation:
unordered_set<string>shoppingList;: We declare an unordered_set named shoppingList to store a list of items. The unordered_set container ensures that each item in the list is unique and does not store duplicates.
Adding Items to the Shopping List:
We add four items to the shoppingList: "laptop", "iphone", "earpods", and "watch" using the insert() function.
Displaying the Initial Shopping List:
After that, we print the contents of the shoppingList to the console, showing the initial shopping list.
Checking if an Item is Already in the Shopping List:
Next, we check if an item (in this case, "earpods") is already present in the shoppingList using the count() function. If the item is found, we print a message indicating that the item is already in the list. If the item is not found, we print a message indicating that the item is not in the list and add it to the shoppingList using the insert() function.
Removing an Item from the Shopping List:
We attempt to remove an item (in this case, "iphone") from the shoppingList using the erase() function. If the item is found and removed successfully, we print a message confirming the removal. If the item is not found, we print a message indicating that the item is not in the list.
Displaying the Updated Shopping List:
After that, we print the contents of the shoppingList again after adding and removing items, showing the updated shopping list.
The unordered_set provides fast insertion, deletion, and lookup operations. Here, it is used to ensure the shopping list only contains unique items, and we can efficiently check for the presence of an item and remove it from the list if needed. The code demonstrates how the unordered_set container can be useful for managing collections of unique items in a simple shopping list scenario.
Set in C++
In C++, an ordered set is an associative container that stores a collection of unique elements in a sorted order. It is implemented as std::set in the C++ Standard Library and automatically maintains the elements in ascending order by default. The ordered set allows for efficient element retrieval, insertion, and deletion, making it suitable for scenarios where elements need to be sorted and quickly accessed.
Properties of the set:
There are several properties of the set in C++. Some main properties of the set are as follows:
Uniqueness: The set ensures that each element is unique, meaning duplicate elements are automatically ignored during insertion. It enforces a strict one-to-one mapping between elements and keys.
Sorted Order: Elements in the set are always kept in a sorted order according to the comparison function used. By default, elements are sorted in ascending order.
Logarithmic-Time Operations: Insertion, deletion, and search operations in an ordered set have logarithmic time complexity O(log n). It means that the time to perform these operations increases slowly as the number of elements (n) grows.
Ordered Iteration: Iterating through an ordered set returns elements in the sorted order, allowing you to process elements sequentially based on their values.
Example:
Let's take a program to illustrate the set in C++.
#include <iostream>
#include <string>
#include <set>
class ContactBook {
private:
std::set<std::string> contacts;
public:
void addContact(const std::string& name) {
contacts.insert(name);
}
void displayContacts() {
std::cout<< "Contacts in the contact book:" << std::endl;
for (const auto&contact : contacts) {
std::cout<< contact << std::endl;
}
}
};
int main() {
ContactBookcontactBook;
contactBook.addContact("Ramu");
contactBook.addContact("Sita");
contactBook.addContact("Krishna");
contactBook.addContact("Radha");
contactBook.addContact("Rukmini");
contactBook.addContact("Ramu");
// This will not be added since it's a duplicate
// All the contacts will be in sorted according to alphabet
contactBook.displayContacts();
return 0;
}
Output:
![unordered_set in C++](https://static.tutorialandexample.com/cpp/unordered-set-in-cpp2.png)
Explanation:
class ContactBook: We define a class named ContactBook to represent a contact book. It has a private member contacts, which is a std::set<std::string> data structure. The set ensures that each contact name is unique and automatically sorts the contacts in alphabetical order.
void addContact(const std::string& name): This member function allows us to add new contacts to the contact book. When a contact is added, the function inserts the contact name into the contacts set.
void displayContacts(): This member function displays all the contacts in the contact book. It iterates through the contacts set and prints each contact name to the console. Since the std::set is sorted, the contacts will be displayed in alphabetical order.
int main(): In the main() function, we create an instance of the ContactBook class named contactBook.
Adding Contacts: We use the addContact() function to add six contacts to the contactBook. Each contact is added using a unique name. When trying to add a duplicate contact, the set automatically ignores the duplicate entry.
Displaying Contacts: After adding the contacts, we call the displayContacts() function to display all the contacts in the contact book. The contacts will be shown in alphabetical order since the set automatically sorts them.
This code demonstrates how to create a simple contact book using the std::set container. The std::set ensures that each contact is unique and maintains the contacts in sorted order. Adding a duplicate contact is automatically handled, and only unique names are stored in the contact book. The sorted order allows for an easy and organized display of the contacts
Conclusion:
In conclusion, the provided code demonstrates the usage of two important containers in C++: unordered_set and set. Both containers are used to store unique elements, but they differ in their organization and performance characteristics.
The unordered_set is a hash set, providing fast insertion, deletion, and lookup operations with a time complexity of O(1) on average. It is suitable for scenarios where the order of elements is not significant, and quick retrieval of elements is essential. In the example of a shopping list, the unordered_set efficiently handles adding and checking for items, ensuring each item is unique. Additionally, the unordered nature of this container allows for dynamic resizing and rehashing as the number of elements increases, ensuring optimal performance even with large data sets.
On the other hand, the set is an ordered set, maintaining elements in ascending order by default. It provides logarithmic-time operations for insertion, deletion, and search with a time complexity of O(log n). In the case of the contact book example, the set keeps the contacts sorted alphabetically, allowing for ordered iteration through the elements. The set is particularly useful in scenarios where elements need to be stored in a specific order, and the sorted organization enables efficient search operations.
Both containers are powerful tools for managing collections of unique elements in C++. The choice between unordered_set and set depends on the specific requirements of the application. If fast and unordered element retrieval is crucial, unordered_set is the preferred choice. However, when elements need to be kept in a specific order and search operations need to be efficient, the set is the optimal selection.
In summary, the unordered_set and set containers offer excellent options for handling unique data with different performance trade-offs. By leveraging these containers, C++ developers can efficiently manage and manipulate unique collections of elements in their programs. Understanding the properties and behavior of these containers is essential for making informed decisions about which one best suits the needs of a particular application.