Arrays are collections of elements of the same type stored in contiguous memory regions in C++. Sets, on the other hand, are containers that keep unique components in sorted order. Converting an array to a set is a handy method for removing duplicates and sorting elements. There are various methods through which the array can be converted to a set in C++.
In terms of efficiency, memory utilisation, and order preservation, each approach offers advantages and downsides. The strategy chosen is determined by the specific requirements of your program.
Why is there a need to convert an array to a set in C++?
Here are the reasons:
- Sets automatically sort elements in a specific order and remove duplicates, making data more accurate and easier to work with.
- Sets are optimised for searching and inserting elements, making them more efficient than arrays for certain operations.
- In database administration and financial data analysis, converting arrays to sets can help remove duplicates and enhance data accuracy.
- Sets can be particularly useful in software development areas like cryptography and network programming, where element order is not significant.
- Sets offer a more efficient solution than arrays when working with large datasets.
Approaches :
- Using std::set constructor
- Using std::vector and std::set
- Using std::unordered_set
- Using a for loop and std::set
Approach 1: Using std::set constructor
Approach 1 involves using the constructor of the std::set class to directly convert an array to a set. The constructor accepts two iterators, which can be pointers to the array’s start and end. The elements in the array are inserted into the set in ascending order
Advantages:
- A quick and easy way to convert an array to a set.
- Elements are inserted in ascending order.
- The time complexity takes O(n log n) time.
Disadvantages:
- It may not be as flexible as other ways because it does not allow for any additional modification or filtering of the pieces.
- The order of the elements may be lost if the array is not sorted.
Code :
#include <iostream>
#include <set>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
std::set<int> s(arr, arr + n);
for (int x : s) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
Output :
1 2 3 4 5 Explanation :
- An array of integers arr is initialised with 5 values.
- The number of elements in the arr array is calculated using the sizeof operator and the result is stored in the variable n.
- A std::set container s is defined and initialised with the elements of the arr array using iterators.
- The elements of the s set are printed to the console using a range-based for loop and a std::cout statement.
- A newline character is printed to the console using another std::cout statement.
- The main() function returns 0, indicating successful completion.
Approach 2 : Using std::vector and std::set
Approach 2 involves converting an array to a set by combining std::vector and std::set. The array’s elements are first entered into a vector, which is then used to form a set. This approach is more flexible than approach 1 because it allows for the items to be sorted, filtered, or manipulated before they are introduced into the set.
Advantages:
- Provides more flexibility than Method 1, as it allows for sorting, filtering, or manipulation of the elements before they are inserted into the set.
- Preserves the order of elements in the array, even if they are not sorted.
- Time complexity of O(n log n) to construct the set.
Disadvantages:
- Requires more code and potentially more computation.
Code :
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
int main() {
int arr[] = {5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
std::vector<int> v(arr, arr + n);
std::sort(v.begin(), v.end(), std::greater<int>());
v.erase(std::unique(v.begin(), v.end()), v.end());
std::set<int> s(v.begin(), v.end());
for (int x : s) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
Output:
1 2 3 4 5 Explanation :
- Sorts the vector v in descending order using std::greater<int>() as the comparison function.
- Removes duplicates from the vector v using std::unique(v.begin(), v.end()).
- Initialises a set s with the unique elements in the vector v.
- Prints the contents of the set s to the console.
- Returns 0, indicating successful execution of the program.
Approach 3 : Using std::unordered_set
Approach 3 involves using the std::unordered_set class to convert an array to a set. The std::unordered_set is an implementation of a hash set, which provides fast average-case lookup and insertion operations, but may not preserve the order of elements.
Advantages:
- Provides fast average-case lookup and insertion operations.
- Can handle large arrays efficiently.
- May be more efficient than Method 1 or Method 2 for large arrays.
Disadvantages:
- May not preserve the order of elements.
- Hash sets may have collisions, which can result in slower worst-case performance.
- May not be suitable for elements that cannot be hashed.
Code :
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <set>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
std::unordered_set<int> us(arr, arr + n);
std::set<int> s(us.begin(), us.end());
for (int x : s) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
Output :
1 2 3 4 5Explanation :
- A std::unordered_set<int> named us is created using the range constructor, which inserts all elements from arr into the unordered set.
- A std::set<int> named s is created using the range constructor, which copies all elements from us into a sorted set.
- The program prints the elements of the set s.
- Finally, the program returns 0 to indicate successful execution.
Approach 4 : Using a for loop and std::set
Approach 4 involves using a for loop to iterate over the array and insert each element into a std::set. This method is straightforward and can handle small to medium sized arrays efficiently. However, it may not be as efficient as the previous methods for large arrays.
Advantages:
- Can handle small to medium sized arrays efficiently.
- Preserves the order of elements.
- Simple and straightforward implementation.
Disadvantages:
- May not be as efficient as other methods for large arrays.
- Requires extra code for inserting elements into the set.
- May be slower than other methods for large arrays due to repeated insertions into the set.
Code :
#include <iostream>
#include <set>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// Insert array elements into set
std::set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
// Print elements of set
for (int x : s) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
Output :
1 2 3 4 5Explanation :
- The program first declares an integer array arr and initialises it with some values. The array’s size is then calculated with the sizeof operator, which returns the number of bytes filled by the array.
- The programme then generates an empty set of integers. It then uses a for loop to run through the array and put each element into the set using the insert method. Due to the fact that sets only hold unique elements, duplicates in the array are automatically removed when they are placed into the set.
- Finally, the programme uses a range-based for loop to loop through the set’s elements. The output shows the elements of the set, which are sorted in ascending order due to the internal ordering of the set.
Best Approach : Using std::unordered_set
The most efficient method for converting an array to a set in C++ is probably Using std::unordered_set. This is because:
- The time complexity is O(nlogn).
- It is useful when we need a quick and straightforward way to convert an array to a set without having to care about the elemental order of the set.
- This method makes use convenient by automatically removing duplicates from the array.
- The std::set constructor offers an easy-to-read syntax for building sets out of arrays.
- The usage of std::vector and std::set is a more flexible solution, but it can be overkill if the order of the set’s members is unimportant.
Sample Problem :
Sample Problem 1:
Suppose John has an array of employee records with the following structure:
struct Employee {
std::string name;
std::string id;
int age;
};
John wants to convert this array into a set so that he can easily perform operations like search, insertion, and deletion efficiently. What modifications should he make to the provided code to accommodate for the id field in the employee records?
Solution:
- First, a custom data type Employee is defined, which has two members – name and age. Then a custom comparison function employeeCompare is defined that compares two employees based on their names. This function will be used to sort the employees in the std::set.
- In the main function, an array of Employee objects called employees is defined and initialised with some data. The number of employees is calculated using sizeof operator.
- Then a std::set called employeeSet is defined with the custom comparison function employeeCompare. The employeeSet is initialised with the data from the employees array using iterators.
- Finally, the sorted list of employees is printed to the console using a range-based for loop.
Code :
#include <iostream>
#include <set>
#include <string>
struct Employee {
std::string name;
int age;
};
bool employeeCompare(const Employee& lhs, const Employee& rhs) {
return lhs.name < rhs.name;
}
int main() {
Employee employees[] = {
{"Alice", 25},
{"Bob", 30},
{"Charlie", 35},
{"David", 40},
{"Emma", 45}
};
const int numEmployees = sizeof(employees) / sizeof(employees[0]);
std::set<Employee, decltype(&employeeCompare)> employeeSet(
employees, employees + numEmployees, &employeeCompare);
for (const auto& employee : employeeSet) {
std::cout << employee.name << " (" << employee.age << ")" << std::endl;
}
return 0;
}
Output :
Bob (30)
Charlie (35)
David (40)
Emma (45)
Sample Problem 2:
The names of customers who have purchased things from Sarah’s store are contained in a significant amount of data that she is working on. The study of the client base is being complicated by human error, which resulted in some customer names being duplicated in the data. To adequately analyse the data, Sarah has to delete the duplicate client names.
Solution:
- An array of strings called products is defined with duplicate values.
- productVector is defined as a vector of strings using the std::vector constructor, which takes in two iterators – std::begin(products) and std::end(products). This is done to convert the products array to a vector.
- uniqueProducts is defined as a set of strings using the std::set constructor, which takes in two iterators – productVector.begin() and productVector.end(). This is done to convert the productVector vector to a set and remove any duplicates.
- The unique products are printed to the console using a for loop.
Code :
#include <iostream>
#include <vector>
#include <set>
#include <string>
int main() {
std::string products[] = {"apple", "orange", "banana", "orange", "grape", "apple", "banana"};
std::vector<std::string> productVector(std::begin(products), std::end(products));
std::set<std::string> uniqueProducts(productVector.begin(), productVector.end());
std::cout << "Unique product names: ";
for (const auto& product : uniqueProducts) {
std::cout << product << " ";
}
std::cout << std::endl;
return 0;
}
Output :
Unique product names: apple banana grape orangeSample Problem 3:
Misa is working on a project where she needs to keep track of the unique IP addresses that visit a website. She has a C++ array of IP addresses, but the array contains some duplicates. She needs to convert this array to a set to efficiently remove the duplicates and keep track of the unique IP addresses.
Solution:
- The code defines an array named ipAddressArray which contains a list of IP addresses as strings.
- It creates a std::set named uniqueIPAddresses that stores unique IP addresses from the ipAddressArray.
- The set is constructed using the array, ipAddressArray and the sizeof() operator to determine the size of the array.
- By dividing the size of a std::string by the sizeof() method, which determines the ipAddressArray’s size in bytes, the number of entries in the array is determined.
- The for loop repeatedly writes the set’s unique IP addresses to the console using std::cout.
- The std::endl function is called to output a newline character to the console after the unique IP addresses have been printed.
Code :
#include <iostream>
#include <set>
#include <string>
int main() {
std::string ipAddressArray[] = {"192.168.0.1", "192.168.0.2", "192.168.0.1", "192.168.0.3", "192.168.0.2"};
std::set<std::string> uniqueIPAddresses(ipAddressArray, ipAddressArray + sizeof(ipAddressArray) / sizeof(std::string));
std::cout << "Unique IP addresses: ";
for (const auto& ipAddress : uniqueIPAddresses) {
std::cout << ipAddress << " ";
}
std::cout << std::endl;
return 0;
}
Output :
Unique IP addresses: 192.168.0.1 192.168.0.2 192.168.0.3 Sample Problem 4:
John is working on a project that involves merging two arrays of employee names. Each array may contain duplicate names, and he needs to remove duplicates from the merged array.
Solution:
- First, two arrays of strings “employees1” and “employees2” are declared and initialised with some employee names.
- The sizes of both arrays are then determined with the sizeof operation and saved in the “size1” and “size2” variables.
- A new string array “mergedEmployees” with the size of the sum of “employees1” and “employees2” is generated.
- A for loop is used to copy the elements of “employees1” array to “mergedEmployees” array.
- Another for loop is used to copy the elements of “employees2” array to “mergedEmployees” array.
- Next, a std::set of strings “uniqueEmployees” is declared, which will be used to store unique employee names.
- A range-based for loop is used to iterate over the “mergedEmployees” array and insert each element into the “uniqueEmployees” set using the insert() method.
- Finally, another range-based for loop is used to print out the unique employee names using cout statement.
Code :
#include <iostream>
#include <set>
#include <string>
int main() {
std::string employees1[] = {"John", "Mary", "David", "John", "Lisa"};
std::string employees2[] = {"David", "Sarah", "Lisa", "John", "Peter", "Lisa"};
int size1 = sizeof(employees1) / sizeof(std::string);
int size2 = sizeof(employees2) / sizeof(std::string);
std::string mergedEmployees[size1 + size2];
int index = 0;
for (int i = 0; i < size1; i++) {
mergedEmployees[index++] = employees1[i];
}
for (int i = 0; i < size2; i++) {
mergedEmployees[index++] = employees2[i];
}
std::set<std::string> uniqueEmployees;
for (const auto& employee : mergedEmployees) {
uniqueEmployees.insert(employee);
}
std::cout << "Unique employee names: ";
for (const auto& employee : uniqueEmployees) {
std::cout << employee << " ";
}
std::cout << std::endl;
return 0;
}
Output :
Unique employee names: David John Lisa Mary Peter SarahConclusion :
In conclusion, choosing the best way for the particular use case is crucial. The methods presented for converting an array to a set in C++ each have different benefits and drawbacks.The std::set constructor is the quickest and most straightforward method for converting an array to a set. However, this method does not let you customise the set’s element order.
With the knowledge and understanding of these methods, developers can efficiently and effectively convert arrays to sets in their C++ programs.
24×7 Live C++ Homework Help From Expert Tutors!
