Introduction
The unorderedmultiset is a component of the C++ Standard Library, specified in the <unorderedset> header file. It serves as an associative container that enables the storage of numerous elements sharing identical values, while preserving no specific sequence for these elements. In contrast to std::set or std::multiset, often structured as binary search trees, an unordered_multiset utilizes hash tables for its implementation, providing an average constant-time complexity for operations like insertions, deletions, and searches.
Characteristics of unordered_multiset:
Hash Table-Based: Items are organized into buckets according to their hash values, enabling efficient average-case performance for insertions and retrieval operations.
It has the capability to store numerous elements containing identical values, meaning duplicates are permitted.
The items are not arranged in any specific sequence.
Use Case:
Deleting elements based on a specific condition is a typical task when dealing with data structures like unordered_multiset. For example, you may need to eliminate all elements that meet a specific criteria, like removing all even integers or all strings with a specific length.
To remove items from an unordered_multiset according to a specific criterion, a mix of standard library algorithms and the container's built-in methods can be employed.
Iterate over the collection: Employ an iterator to navigate through the unordered_multiset.
Verify the condition: Evaluate whether each item meets the specified criteria.
If the criteria are satisfied, remove the element from the collection.
Approach-1: Iterative Erase Using Iterator
This technique requires manually looping through the unordered_multiset and removing elements that meet a particular criterion. The crucial aspect is managing the iterator properly after deleting elements to maintain their validity throughout the process.
Template Parameters:
The Function leverages template parameters to manage diverse types of unordered_multiset, supporting a range of element types, hash functions, and equality operators.
Predicate Flexibility:
The predicate offers versatility as it can be a lambda function, function pointer, or functor, allowing for various ways to define the criteria for removing elements.
Iterator Management:
The Function diligently handles the iterator to guarantee its validity post each erase operation. The erase Method provides an iterator to the subsequent element, thus avoiding any problems with invalidation.
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 given code illustrates the process of eliminating elements from an unorderedmultiset by applying certain criteria through an iterative erase technique involving an iterator. It displays three instances: elimination of even numbers, deletion of short strings, and removal of custom objects representing individuals above a specified age threshold. The central function is eraseif, which traverses the collection and deletes items that meet the specified condition.
- Generic Function erase_if:
The eraseif Function is designed to work with an unorderedmultiset that has particular types specified for its elements, hash function, and key equality function.
The function loops through the collection using an iterator. For every item, it validates a user-defined condition, known as the predicate. When the predicate evaluates to true, the function eliminates the item and adjusts the iterator to the subsequent valid location. If the predicate is false, the iterator is incremented to proceed to the next item. This methodology guarantees that the iteration process remains effective and accurate, especially during element deletions.
- Eliminating Even Numbers:
An unorderedmultiset containing integers is established. A lambda expression named iseven is defined to verify whether an integer is divisible by two. Subsequently, the eraseif function is invoked on the integer set along with the iseven predicate. The resultant elements are then displayed, exclusively exhibiting odd numbers.
Deleting Custom Instances:
To remove custom instances from a container, a similar approach can be taken as with strings or basic data types. This involves utilizing a lambda function that evaluates a specific condition, such as a custom property of the objects. By invoking the erase_if function with the container of custom objects and the corresponding predicate, instances that meet the specified condition can be efficiently eliminated.
The person struct is defined with attributes for name and age, along with an equality operator. A custom hashing function, PersonHash, is implemented to hash Person instances according to their name and age. Subsequently, an unordered_multiset containing Person objects is instantiated.
A lambda expression named isolderthan30 is created to verify if an individual's age exceeds 30. The eraseif method is employed to eliminate individuals aged over 30 from the collection. Subsequently, the remaining items are displayed, exhibiting individuals aged 30 or below.
Complexity Analysis:
Time Complexity:
Iterating Through the Container
The main task within the eraseif Function consists of traversing the elements of the unorderedmultiset. The time complexity associated with this traversal is O(n), with n representing the count of elements within the container. This efficiency stems from the fact that each element is accessed precisely once.
Predicate Evaluation
For every element, the predicate undergoes evaluation. In scenarios where the predicate function operates at O(1) efficiency, as is common for basic checks like verifying number parity or comparing string lengths against a specific limit, the total time complexity continues to be O(n). In cases where the predicate function is more intricate, its specific complexity must be taken into account. However, in the given examples, the impact of predicate evaluation on overall complexity remains minimal.
Erase Operation
The delete process in an unordered_multiset has an average computational complexity of O(1) because of the hash table organization utilized internally. This is based on the assumption of a proficient hash function with minimal collisions. In a situation where numerous elements map to the same bucket (resulting in collisions), the efficiency may decrease to O(n) for every delete action in the worst-case. Nonetheless, by employing a properly crafted hash function and a balanced distribution of elements, the mean complexity remains O(1).
By merging these actions, the total time complexity for the erase_if Function stays at O(n) on average due to:
Iteration over all elements: O(n)
Predicate evaluation: The time complexity for evaluating predicates is O(n) when each individual evaluation takes O(1) time.
Erase operation: O(n) * O(1) = O(n) on average
Space Complexity
Container Storage
The main space complexity of the unordered_multiset is O(n), with n representing the quantity of elements held within the container. This storage is essential for holding both the elements and the foundational hash table structure.
Additional Space in erase_if
The erase_if function does not require extra space relative to the input size. It only utilizes a fixed amount of additional space (O(1)) for the iterator and temporary variables. There are no data structures generated based on the input size.
Hash Table Overhead
Internally, the unordered_multiset stores elements in a hash table with buckets. The space complexity of this data structure is O(n), accounting for both the elements and the buckets. The specific space overhead varies based on the load factor and the hash table's resizing behavior during element insertions and deletions.
Example-Specific Analysis
Removing Even Integers:
The time complexity of O(n) is employed to iterate through and verify each integer.
Space Complexity: O(n) is required to store the integer values.
Removing Short Strings:
Time Complexity: O(n) is required for traversing the array and verifying the length of each string.
The space complexity of O(n) is required for storing the string data.
Removing Custom Objects:
The time complexity is O(n) for looping through and verifying the age of each individual.
Space Complexity: O(n) is allocated for storing the custom objects along with the additional space required for the hash table overhead.
Approach-2: Using the remove_if Algorithm with Erase-Remove Idiom
Employing the removeif algorithm in conjunction with the erase-remove idiom is a frequently employed method in C++ for eliminating elements from containers that have random access iterators, such as std::vector. Nevertheless, std::unorderedmultiset does not offer direct support for this technique due to the absence of random access iterators and the non-contiguous storage of its elements. Notwithstanding this constraint, we can modify the erase-remove idiom to function with std::unordered_multiset by iteratively traversing the container and discarding elements that meet specific criteria.
In typical containers such as std::vector, the erase-remove idiom operates in the following manner:
remove_if Algorithm:
This algorithm rearranges the items within the range [first, last) so that the items failing to meet the specified condition are relocated to the start of the range. The function provides an iterator pointing to the updated end of the range, indicating where the excluded elements start.
erase Method:
The erase function of the container is subsequently employed to eliminate the elements that were logically marked for removal by the remove_if function.
In containers such as std::unordered_multiset, random access iterators are not available, necessitating a different approach to be taken.
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 has been created to eliminate elements from an unordered_multiset according to a specified condition (predicate).
Template Parameters:
The category of items within the unordered_multiset.
Hash: The hashing algorithm employed by the unordered_multiset.
KeyEqual: The comparison function for equality utilized by the unordered_multiset data structure.
Predicate: The category of the predicate function that will be employed to evaluate the condition for every single element.
- Function Parameters:
A pointer to the unordered_multiset from which elements are to be deleted.
The predicate function determines which elements should be excluded by returning true for those elements and false for others.
Function Body:
The function loops through the unorderedmultiset using an iterator. With each element, it evaluates the predicate. If the predicate evaluates to true, the element is removed using the erase function of the unorderedmultiset, which automatically shifts the iterator to the next element. If the predicate evaluates to false, the iterator is advanced to the next element without any modifications.
Helper Function print_set
This utility function is designed to display the contents of an unordered_multiset by iterating through the container and printing each element, separated by a space.
Main Function
The primary Function showcases how to utilize the eraseif Function with diverse unorderedmultisets types and various predicates.
Example 1: Eliminating Even Numbers from an unordered_multiset Containing Integer Values
An unorderedmultiset containing integer values is instantiated and initialized with certain elements. A lambda function named iseven is established to verify whether an integer is even by checking if the remainder of the division by 2 is equal to 0. The initial multiset is displayed. Subsequently, the eraseif function is invoked with the integer multiset and the iseven predicate. Finally, the updated multiset, from which even numbers have been eliminated, is shown.
Removing brief strings from an unorderedmultiset of strings can be achieved by utilizing the eraseif algorithm. This algorithm removes elements from the container that satisfy a specific condition, which, in this case, is the length of the string being less than a certain threshold. By specifying a lambda function as the condition, we can easily filter out the short strings from the unordered_multiset.
An unorderedmultiset containing strings is instantiated and initialized with specific values. A lambda function named isshort is created to determine whether a string's length is under 5 characters. The initial multiset is displayed. The eraseif function is invoked, passing the string multiset and the isshort predicate. The updated multiset, with short strings removed, is then displayed.
Removing Custom Objects from an unordered_multiset involves the following steps:
- Iterate over the elements in the unordered_multiset.
- Check each element against the one to be removed.
- If a match is found, erase the element from the unordered_multiset.
A structure named Person is declared with attributes for name and age, along with an equality operator. A specialized hash function, PersonHash, is implemented to hash Person instances based on their name and age. An unorderedmultiset containing Person instances is instantiated and populated with initial values. A lambda function named isolderthan30 is created to evaluate if a person's age exceeds 30. The initial multiset is displayed, presenting both the name and age of each Person object. Subsequently, the eraseif function is invoked with the person multiset and the isolderthan30 predicate. Finally, the updated multiset, having individuals aged over 30 removed, is showcased.
Example 4: Eliminating Floats Exceeding a Specified Threshold
An unorderedmultiset containing floating-point numbers is instantiated and initialized with certain values. A lambda expression named isgreaterthan4 is declared to validate whether a floating-point number exceeds 4.0. The initial set of numbers is displayed. Subsequently, the eraseif function is invoked with the floating-point set and the isgreaterthan4 predicate. Finally, the adjusted set, with values above 4.0 removed, is showcased.
Complexity Analysis:
Template Function erase_if
The eraseif Function is specifically crafted to eliminate elements from a std::unorderedmultiset using a predicate. Let's delve into the time and space complexity analysis of this function.
Time Complexity
Iteration Over Elements:
The operation loops through every item in the unorderedmultiset by utilizing an iterator. This iteration process operates in O(n) time complexity, with n representing the total count of elements within the unorderedmultiset.
Predicate Evaluation:
For every individual element, the predicate undergoes evaluation. Given that the evaluation of the predicate is of constant time complexity, denoted as O(1), the overall time complexity for evaluating the predicate for all elements amounts to O(n).
Erase Operation:
The delete function in an unorderedmultiset has an average computational complexity of O(1). This efficiency is achieved by utilizing hash tables in std::unorderedmultiset, resulting in an average O(1) complexity for delete, insert, and search functions. In rare instances of hash collisions, the delete operation's time complexity can deteriorate to O(n) in the worst-case scenario, although this occurrence is uncommon and generally does not impact average case evaluation.
If we consider the typical scenario, the overall duration for all erase actions is O(k), where k represents the count of elements meeting the condition. Given that k ≤ n, the maximum time complexity for erase operations under average conditions stays at O(n).
By combining these elements, the erase_if Function achieves an overall average time complexity of O(n).
Space Complexity
Auxiliary Space:
The eraseif Function does not rely on any extra data structures that grow with the input size. It works directly on the provided unorderedmultiset and makes changes within it. The memory utilized by the iterators and the predicate remains constant at O(1).
Space Within unordered_multiset:
The unorderedmultiset's space complexity is O(n) as it must store all elements, which is considered part of the input and not additional space used by the algorithm. Consequently, the eraseif function has an additional space complexity of O(1), classifying it as an in-place operation.
