Learn Multiset in C++: Properties and Key Functions

A set in C++ is a part of the Standard Template Library (STL) and stores unique elements in a sorted manner. It does not allow duplicate values; therefore, it is useful when you need a collection with distinct elements. Sets are implemented using self-balancing binary search trees like Red-Black Trees. with the operations such as insertion, deletion, and searching run in O(log n) time complexity.

A set automatically arranges its elements in ascending order by default. But, a custom comparator can be used for different sorting orders. Since duplicates are not allowed, any attempt to insert an already existing element will be ignored. The set container provides methods like insert(), erase(), and find() to manage elements.

Let’s look at this example where the number 25 is inserted into the set of numbers: 

Code

#include <iostream>
#include <set>
 
int main() {
	std::set<int> numbers = {10, 20, 30, 40, 50};
 
	numbers.insert(25);  // Inserts 25 into the set
 
	std::cout << "Set elements: ";
	for (int num : numbers) {
    	std::cout << num << " ";
	}
 
	return 0;
}

Output

Set elements: 10 20 25 30 40 50
 
=== Code Execution Successful ===

How this code works

• A set named numbers is initialised with {10, 20, 30, 40, 50}.
• The insert(25) function adds 25 while maintaining the sorted order.
• Since sets store unique elements in ascending order, 25 is placed correctly.
• The for loop iterates through the set and prints all elements.
• The final output is: "Set elements: 10 20 25 30 40 50".

Properties of Sets

Here are some of the properties of sets in C++ :

• A set does not allow duplicate values. If you try to insert a value that already exists, the operation is ignored.
• The elements in a set are stored in ascending order by default. You can use std::greater<T> to maintain a descending order set.
• Unlike arrays or vectors, a set does not provide direct access to elements using an index. You must use iterators or search operations to retrieve values.
• Operations like insertion, deletion, and searching take logarithmic time (O(log n)) due to the underlying tree structure.
• Once an element is inserted, it cannot be modified directly. To change a value, you need to remove the old value and insert a new one.
• Sets provide iterators to traverse elements efficiently. However, since elements are sorted, modifying them via iterators is not allowed.

Sets vs Multiset

Sets and multisets have a lot of similarities and some differences:

Bitset in C++

A bitset in C++ is a container which represents a fixed-size sequence of bits (0s and 1s). It is memory-efficient and useful for tasks like bit manipulation, boolean operations, and optimization problems. A bitset offers direct access to individual bits which increases the speed of operations.

Key Features of Bitset:

1. The size of a bitset is defined at compile time.

2. Uses bits instead of bytes, reducing memory usage.

3. Supports operations like AND (&), OR (|), XOR (^), and bit shifting.

• Associative: As an associative container, a multiset stores its items according to a key comparison function. It enables quick insertion, deletion, and searching—usually in logarithmic time. 
• Sorted: The elements are automatically arranged according to the key comparison function. Custom sorting is possible, but they are placed in ascending order by default. 
• Equivalent Keys: Unlike a set, a multiset allows multiple occurrences of the same element. This makes it useful when you need to store duplicates while maintaining order.‍
• Immutable: The elements in a multiset cannot be modified directly through iterators. Any changes must be made by erasing and reinserting elements, ensuring the container's integrity and ordering.

In this program, we see how to declare a C++ multiset, insert elements, and iterate through them. Since a multiset maintains a sorted order by default, the output will display the elements in ascending order. This holds good even if they were inserted in a different sequence.

Syntax

#include <set>
 
std::multiset<type> multiset_name;

Algorithm

1. Declare an empty multiset<int> ms to store the integers.
2. Insert the elements 4, 8, 9, 2, and 1 into the multiset using the insert() function.
3. Iterate through the multiset using a range-based for loop.
4. Print each element in ascending order as the multiset automatically sorts them.
5. End the program after all elements are printed.

#include <iostream>
#include <set>

int main() {
    // Declare a multiset
    std::multiset<int> ms;

    // Inserting elements into the multiset
    ms.insert(4);
    ms.insert(8);
    ms.insert(9);
    ms.insert(2);
    ms.insert(1);

    // Printing elements in ascending order (default sorting)
    std::cout << "Elements in ascending order: ";
    for (int num : ms) {
        std::cout << num << " ";
    }

    return 0;
}

How this Code Works

1. Initialisation: The code begins by creating an empty multiset<int> called ms, which will store integers.
2. Inserting Elements: The insert() function is used to add the integers 4, 8, 9, 2, and 1 into the multiset. Since a multiset automatically sorts its elements, the numbers will be stored in sorted order.
3. Iteration and Printing: The numbers are printed one at a time while the for loop iterates through each multiset element. The elements are then shown in ascending order. 
4. End of Program: Once all elements are printed, the program terminates.

Output

Elements in ascending order: 1 2 4 8 9 

=== Code Execution Successful ===

Complexity 

Time Complexity: Insertion into a C++ multiset takes O(log n) per element, so for n elements, it is O(n log n). Iteration and printing take O(n).

Space Complexity: The multiset stores n elements, so the space complexity is O(n).

‍1. begin(): Returns an iterator to the first element in the multiset. It allows iteration from the beginning of the container. The iterator can be used to access or modify the first element in the multiset. If the container is empty, calling begin() returns end().

// Input: {5, 2, 8, 2, 9}
std::multiset<int> ms = {5, 2, 8, 2, 9}; 
std::cout << *ms.begin();  
// Output: 2

2. end(): Returns an iterator pointing to the position one past the last element in the multiset. It marks the end of the container and is used to stop iteration. The end() iterator cannot be dereferenced. It helps define the range for loops or other container operations.

// Input: {3, 7, 1, 4}
std::multiset<int> ms = {3, 7, 1, 4}; 
std::cout << *(--ms.end());  
// Output: 7

3. size(): Returns the number of elements currently stored in the multiset. It provides the total count of elements, including duplicates. This function checks the container size before performing operations like insertion or removal.

// Input: {10, 20, 10, 30, 10}
std::multiset<int> ms = {10, 20, 10, 30, 10}; 
std::cout << ms.size();  
// Output: 5

‍4. max_size(): Returns the maximum number of elements that the multiset can hold, which is determined by the system's memory limitations. This value can be helpful to check if the container can handle more elements before running out of space. It's not the current size but the theoretical limit.

// Input: Empty multiset
std::multiset<int> ms;  
std::cout << ms.max_size();  
// Output: A very large number (system-dependent)

5. empty(): Checks whether the multiset is empty. It returns true if the container has no elements; otherwise, it returns false. This function is often used as a condition in loops or to ensure that operations like erase() or find() are safe to call on a non-empty container.

// Input: Empty multiset
std::multiset<int> ms;  
std::cout << ms.empty();  
// Output: 1 (true)

6. insert(const g): Inserts an element g into the multiset. If g already exists, it will still be inserted, as the multiset allows duplicate values. The function returns a pair of an iterator to the inserted element and a bool indicating whether the insertion was successful (which will always be true for multiset).

// Input: Insert 4, 8, 4
std::multiset<int> ms;  
ms.insert(4);  
ms.insert(8);  
ms.insert(4);  
for (int x : ms) std::cout << x << " ";  
// Output: 4 4 8

7. insert(iterator position, const g): Inserts the element g at the specified position given by the iterator position. This allows inserting an element into a specific place in the multiset, providing more control. If the element is already present, the multiset will still insert it, maintaining duplicates.

// Input: Insert 3 at a specific position
std::multiset<int> ms = {1, 2, 4, 5};  
auto it = ms.begin();  
ms.insert(it, 3);  
for (int x : ms) std::cout << x << " ";  
// Output: 1 2 3 4 5

8. erase(iterator position): Removes the element at the specified position in the multiset. The iterator position should point to a valid element in the container. After the element is erased, the iterator is invalidated, and the subsequent element will shift to take its place. This operation decreases the size of the container.

// Input: {2, 3, 3, 5}, erase first 3
std::multiset<int> ms = {2, 3, 3, 5};  
ms.erase(ms.find(3));  
for (int x : ms) std::cout << x << " ";  
// Output: 2 3 5

9. erase(const g): Removes all occurrences of the element g from the multiset. If multiple copies of g exist, all will be erased. It is useful for cleaning up specific elements in a container. After calling erase(g), any iterator to the removed elements becomes invalid.

// Input: {1, 2, 2, 3, 3}, erase all 3s
std::multiset<int> ms = {1, 2, 2, 3, 3};  
ms.erase(3);  
for (int x : ms) std::cout << x << " ";  
// Output: 1 2 2

10. clear(): Removes all elements from the multiset. After calling clear(), the container is empty, and its size is zero. This is useful for resetting the container while keeping its allocated memory available for reuse. It is faster than repeatedly erasing individual elements.

// Input: {6, 7, 8}
std::multiset<int> ms = {6, 7, 8};  
ms.clear();  
std::cout << ms.size();  
// Output: 0

11. key_comp() / value_comp(): These functions return the comparison object used to order the elements in the multiset. key_comp() returns a function object that compares keys, and value_comp() is used when accessing the value types in more complex containers. These can be used to determine the order of elements during comparisons.

// Input: {3, 6, 9}
std::multiset<int> ms = {3, 6, 9};  
auto comp = ms.key_comp();  
std::cout << comp(3, 6);  
// Output: 1 (true, 3 < 6)

12. find(const g): Searches for the element g in the multiset and returns an iterator to it if found. If the element is not present, it returns end(). Unlike other containers, a multiset allows multiple occurrences of g, and the iterator points to the first occurrence of the element.

// Input: {4, 5, 6}, find 5
std::multiset<int> ms = {4, 5, 6};  
auto it = ms.find(5);  
std::cout << *it;  
// Output: 5

13. count(const g): Returns the number of times an element g appears in the multiset. Since multiset allows duplicates, this function can return values greater than one. It's helpful in determining the frequency of specific elements without needing to iterate manually.

// Input: {2, 2, 2, 3}, count 2s
std::multiset<int> ms = {2, 2, 2, 3};  
std::cout << ms.count(2);  
// Output: 3

14. lower_bound(const g): Returns an iterator to the first element in the multiset that is not less than g. This is useful for finding the first occurrence of a value or the point where a value should be inserted to maintain sorted order. The result is the first element that is greater than or equal to g.

// Input: {2, 4, 6, 8}, find lower_bound of 5
std::multiset<int> ms = {2, 4, 6, 8};  
std::cout << *ms.lower_bound(5);  
// Output: 6

15. upper_bound(const g): Returns an iterator to the first element in the multiset that is greater than g. This is useful when finding the position where a component would be inserted to maintain the order without duplicates.

// Input: {1, 3, 3, 7}, find upper_bound of 3
std::multiset<int> ms = {1, 3, 3, 7};  
std::cout << *ms.upper_bound(3);  
// Output: 7

16. multiset::swap(): Swaps the contents of two multiset containers. After the swap, both containers will have the elements of the other. This function is proper when exchanging data between two multiset objects without creating or copying new containers.

// Input: ms1 {1,2}, ms2 {3,4}
std::multiset<int> ms1 = {1, 2}, ms2 = {3, 4};  
ms1.swap(ms2);  
for (int x : ms1) std::cout << x << " ";  
// Output: 3 4

17. multiset::operator=: Transfers the elements between different multisets. After the operation, the destination multiset will have the same element as the source multiset. The original multiset remains unaffected by this operator, which makes a deep copy of the elements. 

// Input: Assign ms1 to ms2
std::multiset<int> ms1 = {5, 6, 7};  
std::multiset<int> ms2;  
ms2 = ms1;  
for (int x : ms2) std::cout << x << " ";  
// Output: 5 6 7

18. multiset::emplace(): creates an element and adds it to the multiset in-place. It improves performance when adding complex objects. It directly builds the element right at the position where it is to be stored, eliminating the need for an extra copy or move operation.

// Input: {2, 5}, add 3
std::multiset<int> ms = {2, 5};  
ms.emplace(3);  
for (int x : ms) std::cout << x << " ";  
// Output: 2 3 5

19. multiset::emplace_hint(): Similar to emplace(), but with a hint for where the new element might go. The hint is an iterator to a position in the multiset, which helps optimise insertion if the position is close to where the element should be placed.

// Input: {1, 4, 7}, insert 5 with hint
std::multiset<int> ms = {1, 4, 7};  
auto it = ms.begin();  
ms.emplace_hint(it, 5);  
for (int x : ms) std::cout << x << " ";  
// Output: 1 4 5 7

20. multiset::rbegin(): Returns the final element via a reverse iterator. Reverse printing and other procedures that require working backwards through the elements can benefit from its ability to traverse the container in reverse order.

// Input: {3, 5, 8}
std::multiset<int> ms = {3, 5, 8};  
std::cout << *ms.rbegin();  
// Output: 8

21. multiset::rend(): Returns a reverse iterator one past the first element of the multiset. This iterator helps mark the end of the reverse traversal of the container. It’s typically used in reverse iteration loops to stop after reaching the beginning of the multiset.

// Input: {2, 4, 6}
std::multiset<int> ms = {2, 4, 6};  
std::cout << *(--ms.rend());  
// Output: 2

22. multiset::cbegin(): Returns a constant iterator to the first element of the multiset. This iterator cannot be used to modify the elements, making it useful when you want to safely traverse a multiset without accidentally changing its contents.

// Input: {5, 10, 15}
std::multiset<int> ms = {5, 10, 15};  
std::cout << *ms.cbegin();  
// Output: 5

23. multiset::cend(): Returns a constant iterator past the last element of the multiset. It marks the end of the constant iteration and cannot be used to modify the container. It pairs with cbegin() for safe, non-modifying iteration over the multiset.

// Input: {1, 3, 5}
std::multiset<int> ms = {1, 3, 5};  
std::cout << *(--ms.cend());  
// Output: 5

24. multiset::crbegin(): Returns a constant reverse iterator to the last element in the multiset. This iterator is used for reverse iteration, and like cbegin(), it does not allow modifications of the container’s elements.

// Input: {9, 7, 5}
std::multiset<int> ms = {9, 7, 5};  
std::cout << *ms.crbegin();  
// Output: 9

25. ultiset::crend(): Returns a constant reverse iterator before the first element of the multiset. This iterator marks the end of reverse iteration and is used with crbegin() to safely iterate in reverse without modifying the container.

// Input: {4, 6, 8}
std::multiset<int> ms = {4, 6, 8};  
std::cout << *(--ms.crend());  
// Output: 4

26. multiset::get_allocator(): Returns the allocator used by the multiset to allocate memory. It provides access to the memory management system behind the multiset container, allowing you to customise memory allocation behaviour or inspect the allocation strategy used.

// Input: Create a multiset
std::multiset<int> ms;  
std::cout << typeid(ms.get_allocator()).name();  
// Output: Allocator type (system-dependent)

By default, a C++ multiset stores elements in ascending order. However, you can modify the sorting order to descending using a custom comparator. This is useful when you need to process the largest elements first or when implementing priority-based data handling. The multiset achieves this by using greater<int> as the comparison function.

Algorithm

1. Declare a multiset using greater<int> to store elements in descending order.

2. Insert multiple elements into the multiset.

3. Iterate through the multiset using a range-based for loop.

4. Print the elements, which will appear in descending order.

Code

#include <iostream>
#include <set>
 
int main() {
	std::multiset<int, std::greater<int>> ms = {4, 8, 9, 2, 1};
 
	std::cout << "Multiset in Descending Order: ";
	for (int num : ms) {
    	std::cout << num << " ";
	}
 
	return 0;
}

Output

Multiset in Descending Order: 9 8 4 2 1
 
=== Code Execution Successful ===

How the Code Works

• The multiset is declared with greater<int>, which ensures elements are sorted in descending order.
• Elements {4, 8, 9, 2, 1} are inserted into the multiset, maintaining order automatically.
• A range-based for loop is used to iterate and print the elements.
• Since the multiset sorts elements upon insertion, the output appears in descending order without additional sorting.

The C++ multiset is a powerful container that allows storing multiple occurrences of the same element in a sorted manner. It is perfect for handling duplicate elements since it offers effective actions, including insertion, deletion, and searching. Its associative and sorted nature ensures fast access to elements, while its ability to store equivalent keys distinguishes it from other containers like a set. With a range of useful functions, a multiset is a versatile and efficient tool for managing ordered collections of data in C++.

1. What is a multiset in C++?

In C++, an associative container known as a multiset permits duplicate elements while keeping a sorted order. 

2. How does multiset differ from set in C++?

In contrast to a set, which only stores unique values, a multiset permits multiple occurrences of the same element. 

3. Can I modify elements in a multiset directly?

No, elements in a multiset are immutable. You must remove and reinsert elements to modify them.

4. How do I insert elements into a multiset?

You can use the insert() function to add elements, and it allows duplicates to be inserted automatically.

5. Is multiset sorting customisable in C++?

Yes, you can customise the sorting order of a multiset using a comparison function or by using a custom comparator.