Introduction
The unorderedmultiset is a part of the C++ Standard Library, defined in the <unorderedset> header. It is an associative container that allows for the storage of multiple elements with the same value, and it maintains these elements in no particular order. Unlike std::set or std::multiset, which are typically implemented as binary search trees, an unordered_multiset is implemented using hash tables, offering average constant-time complexity for insertions, deletions, and lookups.
Characteristics of unordered_multiset:
Hash Table-Based: Elements are stored in buckets based on their hash values, which allows for fast average-time complexity for insertions and lookups.
Multiple Elements: It can store multiple elements with the same value (i.e., duplicates are allowed).
No Order: The elements are not stored in any particular order.
Use Case:
Erasing elements based on a specific condition is a common operation when working with containers like unordered_multiset. For instance, you might want to remove all elements that satisfy a particular predicate, such as all even numbers or all strings of a certain length.
To erase elements from an unordered_multiset based on a condition, you can use a combination of standard library algorithms and the container's member functions.
Iterate through the container: Use an iterator to traverse through the unordered_multiset.
Check the condition: For each element, check if it satisfies the given condition.
Erase the element: If the condition is met, erase the element from the container.
Approach-1: Iterative Erase Using Iterator
This Method involves manually iterating through the unordered_multiset and erasing elements that satisfy a specific condition. The key is to handle the iterator correctly when elements are erased to ensure they remain valid throughout the operation.
Template Parameters:
The Function uses template parameters to handle different types of unordered_multiset, accommodating various element types, hash functions, and equality operators.
Predicate Flexibility:
The predicate can be a lambda function, function pointer, or functor, providing flexibility in defining the condition for element removal.
Iterator Management:
The Function carefully manages the iterator to ensure it remains valid after each erase operation. The erase Method returns an iterator to the next element, preventing invalidation issues.
Program:
#include <iostream>
#include <unordered_set>
#include <string>
#include <functional>
// Template function to erase elements satisfying a given condition from an unordered_multiset
template<typename T, typename Hash, typename KeyEqual, typename Predicate>
void erase_if(std::unordered_multiset<T, Hash, KeyEqual>& container, Predicate pred) {
for (auto it = container.begin(); it != container.end(); ) {
if (pred(*it)) {
it = container.erase(it); // Erase and get the next iterator
} else {
++it; // Move to the next element
}
}
}
int main() {
// Example 1: Removing even numbers from an unordered_multiset of integers
std::unordered_multiset<int> intSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// Define a lambda function to check for even numbers
auto is_even = [](int value) { return value % 2 == 0; };
// Call the erase_if Function with the integer set and the predicate
erase_if(intSet, is_even);
// Print the remaining elements
std::cout << "After removing even numbers: ";
for (const auto& elem : intSet) {
std::cout << elem << " ";
}
std::cout << std::endl;
// Example 2: Removing short strings from an unordered_multiset of strings
std::unordered_multiset<std::string> stringSet = {"apple", "banana", "cherry", "date", "fig", "grape"};
// Define a lambda function to check for strings shorter than 5 characters
auto is_short = [](const std::string& value) { return value.length() < 5; };
// Call the erase_if Function with the string set and the predicate
erase_if(stringSet, is_short);
// Print the remaining elements
std::cout << "After removing short strings: ";
for (const auto& elem : stringSet) {
std::cout << elem << " ";
}
std::cout << std::endl;
// Example 3: Removing specific custom objects from an unordered_multiset
struct Person {
std::string name;
int age;
// Define equality operator for Person
bool operator==(const Person& other) const {
return name == other.name && age == other.age;
}
};
// Define a hash function for Person
struct PersonHash {
std::size_t operator()(const Person& p) const {
return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
}
};
// Create an unordered_multiset of Person objects
std::unordered_multiset<Person, PersonHash> personSet = {
{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}, {"David", 25}
};
// Define a lambda function to check for people older than 30
auto is_older_than_30 = [](const Person& p) { return p.age > 30; };
// Call the erase_if Function with the person set and the predicate
erase_if(personSet, is_older_than_30);
// Print the remaining elements
std::cout << "After removing people older than 30: ";
for (const auto& person : personSet) {
std::cout << person.name << " (" << person.age << ") ";
}
std::cout << std::endl;
return 0;
}
Output:
After removing even numbers: 9 7 5 3 1
After removing short strings: grape, cherry banana apple
After removing people older than 30: David (25) Bob (25) Alice (30)
Explanation:
The provided code demonstrates how to remove elements from an unorderedmultiset based on specific conditions using an iterative erase approach with an iterator. It showcases three examples: removing even integers, removing short strings , and removing custom objects that represent people older than a certain age. The key Function is eraseif, which iterates through the container and erases elements that satisfy the given predicate.
- Template Function erase_if:
The eraseif Function is templated to accept an unorderedmultiset with specific types for elements, hash function, and key equality function.
The Function iterates through the container using an iterator. For each element, it checks if the predicate (a condition defined by the user) returns true. If true, it erases the element and updates the iterator to the next valid position. If false, it simply increments the iterator to continue to the next element. This ensures that the iteration remains valid and efficient even as elements are removed.
- Removing Even Integers:
An unorderedmultiset of integers is created. A lambda function iseven checks if an integer is even. The eraseif Function is called with the integer set and the iseven predicate. The remaining elements are printed, showing only odd numbers.
- Removing Short Strings:
An unorderedmultiset of strings is initialized. A lambda function isshort determines if a string has fewer than five characters. The eraseif Function is invoked with the string set and the isshort predicate. The output displays strings with five or more characters, having removed the shorter ones.
- Removing Custom Objects:
Name and age attributes and an equality operator define a person struct. A custom hash function, PersonHash , is provided to hash Person objects based on their name and age. An unordered_multiset of Person objects is created.
A lambda function isolderthan30 checks if a person's age is greater than 30. The eraseif Function is used to remove persons older than 30 from the set. The remaining elements are printed, showing persons aged 30 or younger.
Complexity Analysis:
Time Complexity:
Iterating Through the Container
The primary operation in the eraseif Function involves iterating through the elements of the unorderedmultiset. The time complexity for this iteration is O(n), where n is the number of elements in the container. This is because each element is visited exactly once.
Predicate Evaluation
For each element, the predicate is evaluated. If the predicate function is O(1) (which is typical for simple conditions like checking if a number is even or if a string length is below a certain threshold), the overall time complexity remains O(n). If the predicate function were more complex, its complexity would need to be considered, but for typical use cases provided in the example, the predicate evaluation does not significantly affect the overall complexity.
Erase Operation
The erase operation in an unordered_multiset has an average time complexity of O(1) due to the hash table structure used internally. This assumes a good hash function with few collisions. In the worst-case scenario, where many elements hash to the same bucket (leading to collisions), the complexity could degrade to O(n) for each erase operation. However, with a well-designed hash function and reasonable distribution of elements, the average complexity is O(1).
Combining these operations, the overall time complexity for the erase_if Function remains O(n) on average because:
Iteration over all elements: O(n)
Predicate evaluation: O(n) (if each evaluation is O(1))
Erase operation: O(n) * O(1) = O(n) on average
Space Complexity
Container Storage
The primary space complexity for the unordered_multiset is O(n), where n is the number of elements stored in the container. This Space is required to store the elements themselves and the underlying hash table structure.
Additional Space in erase_if
The erase_if function itself does not use any additional space proportional to the size of the input. The Function uses a constant amount of extra Space (O(1)) for the iterator and any temporary variables. No additional data structures are created that depend on the size of the input.
Hash Table Overhead
Internally, the unordered_multiset maintains a hash table with buckets. The space complexity for this structure is also O(n), considering both the elements and the buckets. The exact overhead depends on the load factor and how the hash table resizes as elements are added or removed.
Example-Specific Analysis
Removing Even Integers:
Time Complexity: O(n) is used to iterate and check each integer.
Space Complexity: O(n) is used to store the integers.
Removing Short Strings:
Time Complexity: O(n) for iterating and checking each string's length.
Space Complexity: O(n) is used to store the strings.
Removing Custom Objects:
Time Complexity: O(n) for iterating and checking each person's age.
Space Complexity: O(n) is used to store the custom objects and the hash table overhead.
Approach-2: Using the remove_if Algorithm with Erase-Remove Idiom
Using the removeif algorithm with the erase-remove idiom is a common technique in C++ for removing elements from containers that support random access iterators, like std::vector. However, std::unorderedmultiset does not support this directly because it does not provide random access iterators, and its elements are not stored in a contiguous block of memory. Despite this limitation, we can adapt the erase-remove idiom to work with std::unordered_multiset by manually iterating over the container and removing elements that match a given condition.
In standard containers like std::vector, the erase-remove idiom works as follows:
remove_if Algorithm:
This algorithm reorders the elements in the range [first, last) in such a way that the elements that do not satisfy the given predicate are moved to the beginning of the range. The algorithm returns an iterator to the new logical end of the range (where the removed elements begin).
erase Method:
The container's erase method is then used to remove the elements that were logically removed by remove_if.
In containers like std::unordered_multiset, we do not have the luxury of random access iterators, so we need to adapt the approach.
Program:
#include <iostream>
#include <unordered_set>
#include <string>
// Template function to erase elements satisfying a given condition from an unordered_multiset
template<typename T, typename Hash, typename KeyEqual, typename Predicate>
void erase_if(std::unordered_multiset<T, Hash, KeyEqual>& container, Predicate pred) {
for (auto it = container.begin(); it != container.end(); ) {
if (pred(*it)) {
it = container.erase(it); // Erase and get the next iterator
} else {
++it; // Move to the next element
}
}
}
//Function to print the contents of an unordered_multiset
template<typename T>
void print_set(const std::unordered_multiset<T>& container) {
for (const auto& elem : container) {
std::cout << elem << " ";
}
std::cout << std::endl;
int main() {
// Example 1: Removing even numbers from an unordered_multiset of integers
std::unordered_multiset<int> intSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// Define a lambda function to check for even numbers
auto is_even = [](int value) { return value % 2 == 0; };
// Print the original set
std::cout << "Original integer set: ";
print_set(intSet);
// Call the erase_if Function with the integer set and the predicate
erase_if(intSet, is_even);
// Print the remaining elements
std::cout << "After removing even numbers: ";
print_set(intSet);
// Example 2: Removing short strings from an unordered_multiset of strings
std::unordered_multiset<std::string> stringSet = {"apple", "banana", "cherry", "date", "fig", "grape"};
// Define a lambda function to check for strings shorter than 5 characters
auto is_short = [](const std::string& value) { return value.length() < 5; };
// Print the original set
std::cout << "Original string set: ";
print_set(stringSet);
// Call the erase_if Function with the string set and the predicate
erase_if(stringSet, is_short);
// Print the remaining elements
std::cout << "After removing short strings: ";
print_set(stringSet);
// Example 3: Removing specific custom objects from an unordered_multiset
struct Person {
std::string name;
int age;
// Define equality operator for Person
bool operator==(const Person& other) const {
return name == other.name && age == other.age;
}
};
// Define a hash function for Person
struct PersonHash {
std::size_t operator()(const Person& p) const {
return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
}
};
// Create an unordered_multiset of Person objects
std::unordered_multiset<Person, PersonHash> personSet = {
{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}, {"David", 25}, {"Eve", 40}
};
// Define a lambda function to check for people older than 30
auto is_older_than_30 = [](const Person& p) { return p.age > 30; };
// Print the original set
std::cout << "Original person set: ";
for (const auto& person : personSet) {
std::cout << person.name << " (" << person.age << ") ";
}
std::cout << std::endl;
// Call the erase_if Function with the person set and the predicate
erase_if(personSet, is_older_than_30);
// Print the remaining elements
std::cout << "After removing people older than 30: ";
for (const auto& person : personSet) {
std::cout << person.name << " (" << person.age << ") ";
}
std::cout << std::endl;
// Example 4: Removing floats greater than a certain threshold
std::unordered_multiset<float> floatSet = {1.5, 2.3, 3.7, 4.1, 5.6, 6.8, 7.2, 8.9};
// Define a lambda function to check for floats greater than 4.0
auto is_greater_than_4 = [](float value) { return value > 4.0; };
// Print the original set
std::cout << "Original float set: ";
print_set(floatSet);
// Call the erase_if Function with the float set and the predicate
erase_if(floatSet, is_greater_than_4);
// Print the remaining elements
std::cout << "After removing floats greater than 4.0: ";
print_set(floatSet);
return 0;
}
Output:
Original integer set: 10 9 8 7 6 5 4 3 2 1
After removing even numbers: 9 7 5 3 1
Original string set: grape fig date cherry banana apple
After removing short strings: grape cherry banana apple
Original person set: David (25) Charlie (35) Bob (25) Eve (40) Alice (30)
After removing people older than 30: David (25) Bob (25) Alice (30)
Original float set: 7.2 5.6 8.9 4.1 6.8 3.7 2.3 1.5
After removing floats greater than 4.0: 3.7 2.3 1.5
Explanation:
- Template Function erase_if
This Function is designed to remove elements from an unordered_multiset based on a given condition (predicate).
Template Parameters:
T: The type of elements in the unordered_multiset.
Hash: The hash function used by the unordered_multiset.
KeyEqual: The equality comparison function used by the unordered_multiset.
Predicate: The type of the predicate function that will be used to check the condition for each element.
- Function Parameters:
container: A reference to the unordered_multiset from which elements will be removed.
pred: The predicate function that returns true for elements that should be removed and false otherwise.
Function Body:
The Function iterates over the unorderedmultiset using an iterator. For each element, it checks the predicate. If the predicate returns true, the element is erased using the erase Method of the unorderedmultiset, which also updates the iterator to the next element. If the predicate returns false, the iterator is simply incremented to move to the next element.
Helper Function print_set
This Function is a utility to print the contents of an unordered_multiset. It iterates through the container and prints each element, followed by a space.
Main Function
The main Function demonstrates the usage of the eraseif Function with different types of unorderedmultisets and various predicates.
Example 1: Removing Even Numbers from an unordered_multiset of Integers
An unorderedmultiset of integers is created and initialized with some values. A lambda function iseven is defined to check if an integer is even (value % 2 == 0). The original set is printed. The eraseif Function is called with the integer set and the iseven predicate. The modified set, after removing even numbers , is printed.
Example 2: Removing Short Strings from an unordered_multiset of Strings
An unorderedmultiset of strings is created and initialized with some values. A lambda function isshort is defined to check if the length of a string is less than 5 characters. The original set is printed. The eraseif Function is called with the string set and the isshort predicate . The modified set, after removing short strings, is printed.
Example 3: Removing Custom Objects from an unordered_multiset
A Person struct is defined with name and age attributes, and an equality operator is provided. A custom hash function, PersonHash, is defined for hashing Person objects based on their name and age. An unorderedmultiset of Person objects is created and initialized with some values. A lambda function isolderthan30, which is defined to check if a person's age is greater than 30. The original set is printed, showing the name and age of each Person. The eraseif Function is called with the person set and the isolderthan30 predicate. The modified set, after removing persons older than 30, is printed.
Example 4: Removing Floats Greater Than a Certain Threshold
An unorderedmultiset of floats is created and initialized with some values. A lambda function isgreaterthan4 is defined to check if a float is greater than 4.0. The original set is printed. The eraseif Function is called with the float set and the isgreaterthan4 predicate. The modified set, after removing floats greater than 4.0, is printed.
Complexity Analysis:
Template Function erase_if
The eraseif Function is designed to remove elements from a std::unorderedmultiset based on a predicate. Here, we analyze the complexity of time and Space in this function.
Time Complexity
Iteration Over Elements:
The Function iterates over each element in the unorderedmultiset using an iterator. This loop runs in O(n) time, where n is the number of elements in the unorderedmultiset.
Predicate Evaluation:
For each element, the predicate is evaluated. Assuming the predicate evaluation takes constant time, O(1), the total time for evaluating the predicate across all elements is O(n).
Erase Operation:
The erase operation in an unorderedmultiset has an average time complexity of O(1). This is because std::unorderedmultiset uses hash tables, allowing average O(1) complexity for insertion, deletion, and lookup operations. In the worst case, due to hash collisions, the time complexity of the erase operation can degrade to O(n), but this is rare and typically doesn't affect average case analysis.
If we assume the average case, the total time for all erase operations is O(k), where k is the number of elements that satisfy the predicate. Since k ≤ n , the worst-case time for erase operations in average scenarios remains O(n).
Combining these factors, the overall average time complexity of the erase_if Function is O(n).
Space Complexity
Auxiliary Space:
The eraseif Function does not use any additional data structures that scale with the input size. It operates directly on the given unorderedmultiset and modifies it in place. The Space used by the iterators and the predicate is constant, O(1).
Space Within unordered_multiset:
The space complexity of the unorderedmultiset itself is O(n), as it needs to store all elements. This Space is not considered additional Space used by the algorithm since it is part of the input. Therefore, the additional space complexity of the eraseif Function is O(1), making it an in-place operation.