Understanding Multiset, Unordered Sets and Bit Sets in C++

In C++, a set is a data structure that stores unique elements of the same type in a sorted order. For situations when you need to track different elements, it automatically makes sure that no duplicate data are recorded. With a temporal complexity of O(log n), sets are implemented as balanced binary trees, enabling effective insertion, deletion, and search operations.

C++ sets are perfect for handling unique and ordered data because of their unique features. These characteristics specify how sets effectively arrange, store, and work with elements. Let's examine some of the key characteristics that give sets in C++ their strength and adaptability.

• Storing Order: A set's items are kept in a sorted order, usually by default in ascending order. This makes range-based searches and actions simple by guaranteeing that all data are arranged. 
• Values Characteristics: C++ sets can only hold one value at a time. To guarantee that every value appears in the set only once, duplicate elements are immediately eliminated.
• Values Nature: A set's constituent parts are unchangeable by nature. An element's value cannot be directly altered once it has been added. Elements must be removed and then reinserted with the updated values in order to change a set.
• Search Technique: C++ sets store elements in binary trees, such as Red-Black Trees, to enable effective searching. Checking for the existence of a component is quick since lookup operations are completed in O(log n) time.
• Arranging Order: The set uses the default comparison operator (usually <) to sort its elements automatically. Every time an element is added or withdrawn from the set, this order is preserved. 
• Unique Elements: All values are distinct, meaning duplicates are disregarded.

Syntax

For using a set, you have to include the <set> header file:

#include <set>

set<type> set_name;

Example Code

Algorithm

1. Declare a set called City to store strings (city names).
2. Insert the cities "Lucknow", "Delhi", "Mumbai", and "Chennai" into the set.
3. Loop through each element in the set and print the city names.

#include <iostream>
#include <set>
#include <string>

int main() {
    // Declare a set of strings to store city names
    std::set<std::string> City;

    // Adding elements to the set
    City.insert("Lucknow");
    City.insert("Delhi");
    City.insert("Mumbai");
    City.insert("Chennai");

    // Printing the elements of the set (it will be sorted by default)
    std::cout << "Cities in the set: " << std::endl;
    for (const std::string& city : City) {
        std::cout << city << std::endl;
    }

    return 0;
}

Output

Cities in the set: 
Chennai
Delhi
Lucknow
Mumbai
=== Code Execution Successful ===

How This Code Works

1. A set named City is created to store strings, specifically city names.
2. The cities "Lucknow", "Delhi", "Mumbai", and "Chennai" are added to the set using the insert() method. Since sets automatically store unique elements, no duplicates can be added.
3. The for loop iterates over the set and each city name is printed on a new line. The cities are displayed in lexicographical (alphabetical) order, as std::set automatically sorts the elements.
4. The program outputs each city name, ensuring the set’s sorted order is respected.

Example 1: Storing and Sorting Bike Names Using std::set in C++

Algorithm

1. Declare a set called bikes to store strings (bike names).

2. Insert the bike names "Yamaha", "Honda", "Suzuki", "Kawasaki", and "Ducati" into the set.

3. Loop through each element in the set and print the bike names.

Code 

#include <iostream>
#include <set>
#include <string>
 
int main() {
	// Declare a set of strings to store bike names
	std::set<std::string> bikes;
 
	// Adding elements to the set
	bikes.insert("Yamaha");
	bikes.insert("Honda");
	bikes.insert("Suzuki");
	bikes.insert("Kawasaki");
	bikes.insert("Ducati");
 
	// Printing the elements of the set (it will be sorted alphabetically)
	std::cout << "Bikes in the set: " << std::endl;
	for (const std::string& bike : bikes) {
    	std::cout << bike << std::endl;
	}
 
	return 0;
}

Output

Bikes in the set:
Ducati
Honda
Kawasaki
Suzuki
Yamaha
 
 
=== Code Execution Successful ===

How This Code Works

• A set named bikes is created to store bike names as strings.
• The insert() method is used to add five bike names: "Yamaha", "Honda", "Suzuki", "Kawasaki", and "Ducati".
• Since std::set automatically stores unique elements, duplicates are not allowed.
• The for loop iterates through the set and prints each bike name.
• std::set maintains a sorted order, so the bike names appear in alphabetical order in the output.

Example 2: Numerical Sorting Using A Set In C++

Algorithm

1. Declare a set called numbers to store integers.

2. Insert the numbers 50, 10, 30, 20, and 40 into the set.

3. Loop through each element in the set and print the numbers.

Code

#include <iostream>
#include <set>
 
int main() {
	// Declare a set of integers
	std::set<int> numbers;
 
	// Adding elements to the set
	numbers.insert(50);
	numbers.insert(10);
	numbers.insert(30);
	numbers.insert(20);
	numbers.insert(40);
 
	// Printing the elements of the set (it will be sorted in ascending order)
	std::cout << "Numbers in the set: " << std::endl;
	for (int num : numbers) {
    	std::cout << num << " ";
	}
	
	return 0;
}

Output

Numbers in the set:
10 20 30 40 50
 
=== Code Execution Successful ===

How This Code Works

• A set named numbers is created to store integer values.
• The insert() method is used to add five numbers: 50, 10, 30, 20, and 40.
• Since std::set stores only unique values, duplicates are ignored if inserted.
• The for loop iterates through the set and prints each number.
• std::set maintains elements in sorted order, so the numbers appear in ascending order in the output.

Example 3: Showcasing Unique Elements

Elements within a set are distinct, meaning they cannot be repeated or duplicated. Here, we’ll see how sets store only unique elements in C++.

Algorithm

• Declare a set called numbers to store integers.
• Insert the numbers 10, 20, 30, 20, 40, 10, and 50 into the set.
• Since sets store only unique elements, duplicate values will be automatically removed.
• Loop through the set and print the elements.

Code

#include <iostream>
#include <set>
 
int main() {
	// Declare a set of integers
	std::set<int> numbers;
 
	// Adding elements to the set (some duplicates included)
	numbers.insert(10);
	numbers.insert(20);
	numbers.insert(30);
	numbers.insert(20); // Duplicate
	numbers.insert(40);
	numbers.insert(10); // Duplicate
	numbers.insert(50);
 
	// Printing the elements of the set
	std::cout << "Unique numbers in the set: " << std::endl;
	for (int num : numbers) {
        std::cout << num << " ";
	}
 
	return 0;
}

Output

Unique numbers in the set:
10 20 30 40 50
 
=== Code Execution Successful ===

How This Code Works

• A set named numbers is created to store integers.
• The insert() method is used to add values: 10, 20, 30, 20, 40, 10, 50.
• Duplicate values (10 and 20) are ignored, as sets only store unique elements.
• The for loop iterates through the set and prints each number.
• The numbers are displayed in ascending order, as std::set automatically sorts elements.

1. insert(): The insert() function is used to add a new element to the set. Since sets store only unique elements, if an element is already present, it won't be inserted again. This function ensures that the set maintains its property of containing distinct values.

Example:

std::set<int> s; s.insert(10); // Inserts 10 into the set

2. erase(): The erase() function removes a specific element from the set. If the element exists, it is deleted; otherwise, nothing happens. This operation helps in dynamically managing elements within the set.

Example:

std::set<int> s = {10, 20, 30}; s.erase(20); // Removes 20 from the set 

3. begin(): The begin() function returns an iterator pointing to the first element in the set. It allows traversal of the set from the start. You can use this iterator to access and manipulate elements sequentially. If the set is empty, it returns the same value as the end().

Example:

std::set<int> s = {10, 20, 30}; auto it = s.begin(); // Points to 10

4. end(): The end() function returns an iterator pointing just past the last element of the set. It marks the end of the set, making it useful for iteration when combined with begin(). It indicates where the iteration should stop, as no valid elements exist beyond it. For an empty set, begin() and end() return the same iterator.

Example:

std::set<int> s = {10, 20, 30}; auto it = s.end(); // Points past the last element

5. size(): The size() function returns the number of elements currently stored in the set. It helps determine how many unique elements are in the set. This function runs constantly, making it efficient even for large sets. An empty set will return 0.

Example:

std::set<int> s = {10, 20, 30}; std::cout << s.size(); // Output: 3

6. max_size(): The max_size() function returns the maximum number of elements that the set can hold. This limit depends on system memory and architecture. It provides a useful indication of how large a set can grow, especially when working with large data. The function does not return the actual size but an upper bound on it.

Example:

std::set<int> s; std::cout << s.max_size(); // Outputs the max possible size

7. empty(): The empty() function checks if the set is empty. It returns true if the set contains no elements and false if it contains at least one element. This is particularly useful for avoiding errors during set operations that require a non-empty set. It runs in constant time, making it efficient for frequent checks.

Example:

std::set<int> s; std::cout << s.empty(); // Output: 1 (true)

8. set precision(): C++ set precision() function allows you to adjust how many significant digits are shown for floating-point data. It is applicable to output streams such as std::cout and is a component of the library. You can change the number of significant digits that set precision(), which is shown by default, up to six. It modifies the output's formatting without altering the number's actual value. 

Example:

std::cout << std::setprecision(3) << 3.14159; // Output: 3.14

9. clear(): The clear() function removes all elements from the set, leaving it empty. This operation reduces the size of the set to zero and frees up memory used by its elements. After calling clear(), the set no longer contains any elements. It is useful for resetting the set when you no longer need its contents.

Example:

std::set<int> s = {10, 20, 30}; s.clear(); // Empties the set

10. swap(): The swap() function exchanges the contents of two sets. It allows you to swap the elements without copying or re-inserting them efficiently. This function is useful when you need to swap sets in algorithms or change data dynamically. The operation runs in constant time.

Example:

std::set<int> s1 = {1, 2}, s2 = {3, 4}; s1.swap(s2); // s1 now has {3, 4}

11. cbegins(): The cbegin() function returns a constant iterator pointing to the first element of the set. This iterator cannot be used to modify the set elements.

Example:

std::set<int> s = {10, 20, 30}; auto it = s.cbegin(); // Points to 10 (read-only)

12. cend(): The cend() function returns a constant iterator pointing just past the last element of the set. It is mainly used in iterations where modification is not required.

Example:

std::set<int> s = {10, 20, 30}; auto it = s.cend(); // Points past the last element

13. rbegin(): The rbegin() function returns a reverse iterator pointing to the last element of the set. This allows traversal of the set in reverse order from the largest element to the smallest.

Example:

std::set<int> s = {10, 20, 30}; auto it = s.rbegin(); // Points to 30

14. rend(): The rend() function returns a reverse iterator pointing just before the first element of the set. It marks the stopping point for the reverse iteration.

Example:

std::set<int> s = {10, 20, 30}; auto it = s.rend(); // Points before the first element

15. bucket_size(): The bucket_size() function returns the number of elements in a specific bucket of an unordered_set. Since std::set does not use buckets, this function is only applicable to unordered sets.

Example:

std::unordered_set<int> s = {10, 20, 30}; size_t size = s.bucket_size(0); // Gets bucket size

16. emplace(): The emplace() function inserts a new element into the set directly without creating a temporary object, making it more efficient than insert().

Example:

std::set<int> s; s.emplace(10); // Inserts 10 into the set

17. max_bucket_count(): The max_bucket_count() function returns the maximum number of buckets that an unordered_set can have. This function helps determine the capacity of an unordered set.

Example:

std::unordered_set<int> s; std::cout << s.max_bucket_count(); // Outputs max bucket count

In C++, a multiset is comparable to a set but permits duplicate elements. Multisets can hold numerous instances of the same element, in contrast to sets, which only store unique values. They provide effective insertions, deletions, and searches because they are constructed using balanced binary trees. When managing collections where duplicates are permitted, like when counting occurrences in a dataset or when you need to monitor the frequency of elements, multisets come in handy. 

Syntax

// declare a multiset
std::multiset<data_type> multiset_name = {key1, key2, key3, ...};

A bitset is a container in C++ that provides effective bit-level manipulation by storing a fixed-size sequence of bits. Setting, resetting, flipping, and carrying out bitwise operations like AND, OR, and XOR are among the simple actions it permits. Compared to arrays of booleans, bit set c++ is more memory economical and is especially helpful in applications that prioritise speed and memory optimisation, such as algorithms that require quick bit-level operations or embedded devices. 

Syntax

bitset<size> variable_name(initialization);

An unordered set does not preserve any particular elemental order. Although there is no assurance of order, it has faster average-case performance for search, insertion, and deletion operations (usually O(1)) since it stores elements in a hash table. An unordered collection has unique elements as well. While unordered sets offer faster operations but lack element order, ordered sets offer sorted data at the expense of somewhat slower operations. 

Syntax

std::unordered_set<data_type> name;

The set data structure in C++ stores elements in ascending order by default. However, there are cases where sorting elements in descending order is required. To achieve this, we can use the std::set with a custom comparator or use std::multiset, which allows custom sorting criteria.

Unlike std::set, which stores only unique elements, C++ multiset allows duplicate values while maintaining a sorted order. When sorting in descending order, a custom comparator (std::greater<T>) is passed while defining the set. In this way the elements are stored from highest to lowest rather than the default ascending order.

One more approach to sorting a set in descending order is by copying its elements into a std::vector or std::deque. Then it is sorted manually using std::sort(). However, using std::set with a custom comparator is the most efficient method.

Algorithm to Sort a Set in Descending Order

1. Declare a std::set<int, std::greater<int>> to store elements in descending order.

2. Insert multiple integer values into the set.

3. Use a loop to iterate over the set and print its elements.

4. Since std::set maintains a sorted order, elements will be displayed from largest to smallest.

Code

#include <iostream>
#include <set>
 
int main() {
	// Define a set in descending order using std::greater<int>
	std::set<int, std::greater<int>> numbers;
 
	// Inserting elements into the set
	numbers.insert(50);
	numbers.insert(10);
	numbers.insert(30);
	numbers.insert(20);
	numbers.insert(40);
 
	// Display elements in descending order
	std::cout << "Elements in descending order:" << std::endl;
	for (int num : numbers) {
    	std::cout << num << " ";
	}
	std::cout << std::endl;
 
	return 0;
}

Output

Elements in descending order:
50 40 30 20 10
 
 
=== Code Execution Successful ===

How This Code Works

1. Declaring the Set

• Instead of a regular std::set<int>, we use std::set<int, std::greater<int>> to store elements in descending order.
• The std::greater<int> comparator instructs the set to order values from highest to lowest.

2. Inserting Elements

• Values {50, 10, 30, 20, 40} are added to the set.
• Since std::set stores unique values, any duplicate elements will be ignored.

3. Iterating Through the Set

• A for loop prints each value.
• Since we used std::greater<int>, the output appears in descending order (largest to smallest).

Sorting Using C++ Multiset

If duplicate values need to be maintained in descending order, we can use C++ multiset instead of std::set. The multiset structure allows multiple occurrences of the same value.

Code 

#include <iostream>
#include <set>
 
int main() {
	// Define a multiset with descending order
	std::multiset<int, std::greater<int>> numbers = {50, 10, 30, 20, 40, 10, 30};
 
	// Display elements (duplicates allowed)
	std::cout << "Multiset elements in descending order:" << std::endl;
	for (int num : numbers) {
    	std::cout << num << " ";
	}
	std::cout << std::endl;
 
	return 0;
}

Output

Multiset elements in descending order:
50 40 30 30 20 10 10
 
 
=== Code Execution Successful ===

How This Code Works

Both methods can store and retrieve elements in a sorted descending order while using the set data structure in C++.

1. Declaring the Multiset

• Instead of a regular std::set, we use std::multiset<int, std::greater<int>>.
• The std::greater<int> comparator ensures that elements are stored in descending order.
• Unlike std::set, a C++ multiset allows duplicate values to be stored.

2. Inserting Elements

• The multiset is initialised with {50, 10, 30, 20, 40, 10, 30}.
• Both 10 and 30 appear twice, demonstrating how a multiset retains duplicate elements while maintaining sorting order.

3. Iterating Through the Multiset

• A for loop prints each value in descending order.
• The duplicates appear in sorted order, making std::multiset useful when keeping duplicate values is necessary.

To sum up, C++ sets are substantial, effective containers that provide special benefits for data management. Sets offer the perfect answer for activities requiring quick lookups and ordered data since they guarantee that elements are saved in sorted order and remove duplicates. Common set operations, including insertion, deletion, and searching, have been covered, along with significant functions and recommended practices. Knowing how ordered and unordered sets behave enables you to choose the best kind for your particular requirements. Gaining proficiency with sets in C++ will enable you to manage data more skillfully, increasing the effectiveness and readability of your programs. 

1. What is the difference between a set and a multiset in C++?

Whereas a multiset permits duplicates, a set retains unique pieces. Although they are both sorted containers, multisets can hold many instances of the same value.

2. How do you insert elements into a set in C++?

To add items to a set, utilise the insert() function. The element is added if it isn't already there; if it is, the set stays the same.

3. Can a set contain duplicate elements?

No, sets guarantee that every element is distinct by default. A duplicate is disregarded if you try to insert one.

4. How can you check if a set is empty in C++?

Make use of the empty() method. If the set is empty, it returns true; if it contains elements, it returns false.

5. What is the time complexity of searching in a set?

Because of its underlying balanced tree structure, searching in a set usually takes O(log n) time, which makes it effective for big data sets.