Set & Multiset

In the world of programming, managing collections of data is a fundamental task. The C++ Standard Template Library (STL) provides several containers to help with this, including set and multiset. These containers are particularly useful when you need to store unique sorted elements or handle duplicates efficiently.

Introduction

A set is an associative container that stores unique elements following a specific order. By default, the elements in a set are stored in ascending order based on their values. This makes sets ideal for scenarios where you need to ensure uniqueness and maintain a sorted collection.

A multiset, on the other hand, is similar to a set but allows duplicate elements. It also maintains the elements in a sorted order. Multisets are useful when duplicates are necessary, such as counting occurrences of items.

In this tutorial, we will explore how to use set and multiset containers in C++. We'll cover operations like insertion, finding, counting, and erasing elements, and understand the differences between these two containers.

Core Content

Set Basics

A set is a container that stores unique elements following a specific order. The default sorting criterion is less than (<). Here's how you can declare and initialize a set:

1#include <iostream>
2#include <set>
3 
4int main() {
5  std::set<int> mySet = {5, 2, 9, 1, 5};
6  
7  for (const auto& elem : mySet) {
8      std::cout << elem << " ";
9  }
10  
11  return 0;
12}

Explanation:

• The duplicate 5 is automatically ignored by the set.

Finding Elements

To find an element in a set, you can use the find() method. This method returns an iterator to the element if found, or end() if not found:

1#include <iostream>
2#include <set>
3 
4int main() {
5  std::set<int> mySet = {5, 2, 9, 1};
6  
7  auto it = mySet.find(5);
8  if (it != mySet.end()) {
9      std::cout << "Element found: " << *it << std::endl;
10  } else {
11      std::cout << "Element not found" << std::endl;
12  }
13  
14  return 0;
15}

Explanation:

• The count() method checks for the presence of an element and returns the number of times it appears, which is either 0 or 1.

Erasing Elements

To remove an element from a set, you can use the erase() method. Here's how:

1#include <iostream>
2#include <set>
3 
4int main() {
5  std::set<int> mySet = {5, 2, 9, 1};
6  
7  mySet.erase(5);
8  
9  for (const auto& elem : mySet) {
10      std::cout << elem << " ";
11  }
12  
13  return 0;
14}

Explanation:

• The multiset stores duplicates and maintains the elements in sorted order.

Inserting Elements

Inserting elements into a multiset works similarly to a set:

1#include <iostream>
2#include <set>
3 
4int main() {
5  std::multiset<int> myMultiset;
6  
7  myMultiset.insert(5);
8  myMultiset.insert(2);
9  myMultiset.insert(9);
10  myMultiset.insert(1);
11  myMultiset.insert(5); // Duplicate element
12  
13  for (const auto& elem : myMultiset) {
14      std::cout << elem << " ";
15  }
16  
17  return 0;
18}

Explanation:

• The find() method returns an iterator to the first occurrence of the element.

Counting Elements

The count() method in a multiset can return more than one if there are duplicate elements:

1#include <iostream>
2#include <set>
3 
4int main() {
5  std::multiset<int> myMultiset = {5, 2, 9, 1, 5};
6  
7  int count = myMultiset.count(5);
8  std::cout << "Count of element 5: " << count << std::endl;
9  
10  return 0;
11}

Explanation:

• The erase() method removes all occurrences of the element.

Practical Example

Let's create a practical example that demonstrates the use of both set and multiset. We'll implement a simple program to count the frequency of words in a text input:

1#include <iostream>
2#include <string>
3#include <set>
4#include <map>
5 
6int main() {
7  std::multiset<std::string> wordMultiset;
8  std::set<std::string> uniqueWords;
9  
10  std::cout << "Enter some text (type 'done' to finish):" << std::endl;
11  std::string input;
12  while (true) {
13      std::cin >> input;
14      if (input == "done") break;
15      wordMultiset.insert(input);
16      uniqueWords.insert(input);
17  }
18  
19  std::cout << "
20Unique words and their frequencies:" << std::endl;
21  for (const auto& word : uniqueWords) {
22      int count = wordMultiset.count(word);
23      std::cout << word << ": " << count << std::endl;
24  }
25  
26  return 0;
27}

Explanation:

• We use a multiset to store all words, allowing duplicates.
• A set is used to store unique words for easy iteration and counting.

Summary

What's Next?

In the next tutorial, we will explore Unordered Map & Unordered Multimap containers. These containers provide average constant-time complexity for most operations and are useful when order is not a concern.

Stay tuned!