In the C++ Standard Template Library (STL), associative containers are a very important class of containers that provide a key-value pair storage method. This article will detail three commonly used associative containers: <span>set</span>, <span>map</span>, and <span>multiset</span>, and demonstrate their efficient operations through code examples.
1. set
1.1 Overview
<span>set</span> is a collection that only allows unique elements and automatically sorts the elements. Its underlying implementation is usually a red-black tree, so the time complexity for insertion, deletion, and search operations is O(log n).
1.2 Basic Operations
Here are some examples of basic operations:
#include <iostream>#include <set>
int main() { std::set<int> mySet;
// Insert elements mySet.insert(5); mySet.insert(3); mySet.insert(8);
// Attempt to insert a duplicate element auto result = mySet.insert(3); // Will not insert successfully if (!result.second) { std::cout << "Element 3 already exists in the set." << std::endl; }
// Iterate through the set for (const int& num : mySet) { std::cout << num << " "; }
std::cout << "\n";
// Find an element if (mySet.find(5) != mySet.end()) { std::cout << "Found element 5 in the set." << std::endl; }
// Delete an element mySet.erase(3);
return 0;}1.3 Output Result
Element 3 already exists in the set.3 5 8 Found element 5 in the set.2. map
2.1 Overview
<span>map</span> is a collection of key-value pairs, where each key is unique and can be quickly accessed to retrieve the corresponding value. Similar to <span>set</span>, the underlying implementation is also a red-black tree, so the time complexity for search, insertion, and deletion operations is O(log n).
2.2 Basic Operations
Here is a basic usage example of <span>map</span>:
#include <iostream>#include <map>
int main() { std::map<std::string, int> ageMap;
// Insert key-value pairs ageMap["Alice"] = 30; ageMap["Bob"] = 25;
// Update value ageMap["Alice"] = 31;
// Iterate through the map for (const auto& pair : ageMap) { std::cout << pair.first << ": " << pair.second << "\n"; }
// Check if a key exists and get its value auto it = ageMap.find("Bob");
if (it != ageMap.end()) { std::cout << "Bob's age is: " << it->second << "\n"; } else { std::cout<< "Bob not found.\n"; }
return 0;}Output Result:
Alice:31 Bob:25 Bob's age is:25 ## 3. multiset
### 3.1 Overview
A multiset is similar to a set but allows duplicate elements. This makes it very useful when you need to store multiple identical items.
### 3.2 Basic Operations
Here is a basic usage example of multiset:
#include <iostream> #include <set>
int main() { std::multiset<int> multiSet;
// Insert multiple identical elements multiSet.insert(10); multiSet.insert(20); multiSet.insert(10);
// Iterate through the multiset and output each number and its occurrence count for(const int &num : multiSet){ std::cout<< num << " "; }
std::cout<< "\n";
// Get the count of a specific number int countOfTen = multiSet.count(10); std::cout<< "Number of times '10' appears: "<< countOfTen<<"\n";
return 0; }Output Result:
10 10 20 Number of times '10' appears: 2Conclusion
This article introduced three commonly used associative containers in C++ STL: <span>set</span>, <span>map</span>, and <span>multiset</span>. Each has unique structural characteristics and applicable scenarios. In actual development, choosing the appropriate data structure based on requirements can improve program performance and readability. I hope this article helps you better understand these data structures and their efficient usage methods!