C++ STL入门教程(7) multimap、multiset的使用

一、multimap(一对多索引)

C++ multimap和map所支持的操作相同（除了multimap不支持下标运算），但是multimap允许重复的元素。

完整程序代码：

				?

									/*请务必运行以下程序后对照阅读*/

									///头文件依旧是map 

									#include <map> 

									#include <string> 

									#include <iostream> 

									using namespace std; 

									int main() 

									{ 

									  ///1. 初始化 

									  multimap<int, string> mapStudent; 

									  multimap<int, string>::iterator iter, beg, end; 

									  ///2. 添加元素 

									  ///multimap不支持下标操作 

									  mapStudent.insert(pair<int, string>(0, "student_one")); 

									  mapStudent.insert(pair<int, string>(0, "student_one_copy"));///一对多 

									  mapStudent.insert(pair<int, string>(1, "student_two")); 

									  mapStudent.insert(pair<int, string>(5, "Fear Kubrick")); 

									  mapStudent.insert(pair<int, string>(2, "Akemi Homura")); 

									  mapStudent.insert(pair<int, string>(-1, "Eren Jaeger")); 

									  mapStudent.insert(pair<int, string>(99, "lin")); 

									  cout << mapStudent.size() << endl; 

									  cout << endl; 

									  ///3. 遍历 

									  for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) 

									    cout << iter->first << " " << iter->second << endl; 

									  cout << endl; 

									  ///4. 单键查询与范围查询 

									  ///单键查询 

									  int count = mapStudent.count(0); 

									  iter = mapStudent.find(0); 

									  for (int i = 0; i < count; i++, iter++) 

									    cout << iter->first << " " << iter->second << endl; 

									  cout << endl; 

									  ///范围查询 

									  beg = mapStudent.lower_bound(1);/// >=1 

									  end = mapStudent.upper_bound(5);/// <=5 

									  for (; beg != end; beg++) 

									    cout << beg->first << " " << beg->second << endl; 

									  cout << endl; 

									  ///5. 删除 

									  iter = mapStudent.find(1); 

									  mapStudent.erase(iter); 

									  cout << mapStudent.size() << endl; 

									  for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) 

									    cout << iter->first << " " << iter->second << endl; 

									  cout << endl; 

									  ///6. 判空与清空 

									  if (!mapStudent.empty()) 

									    mapStudent.clear(); 

									}

二、multiset(多元集合)

多元集合(multiset)和集合(set)所支持的操作相同，只不过支持重复对象。
它是<set>库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(log n)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。
PS：与priority_queue(优先队列)相比，multiset取出任意一个元素要O(log n)，但priority_queue要O(n)。（这就是它叫做queue的原因）

C++ STL入门教程(7) multimap、multiset的使用

完整程序代码：

				?

									/*请务必运行以下程序后对照阅读*/

									///头文件依旧为set 

									#include <set> 

									#include <iostream> 

									using namespace std; 

									int main() 

									{ 

									  ///1. 初始化 

									  multiset<int> num; 

									  multiset<int>::iterator iter,beg,end; 

									  cout << num.max_size() << endl;///multiset容纳上限 

									  cout << endl; 

									  ///2. 添加元素 

									  for (int i = 0; i < 10; i++) 

									    num.insert(i); 

									  cout << num.size() << endl; 

									  cout << endl; 

									  ///3. 遍历 

									  for (iter = num.begin(); iter != num.end(); iter++) 

									    cout << *iter << " " ; 

									  cout << endl; 

									  cout << endl; 

									  ///4. 查询 

									  iter = num.find(1); 

									  if (iter != num.end()) 

									    cout << *iter << endl; 

									  else

									    cout << -1 << endl; 

									  iter = num.find(99); 

									  if (iter != num.end()) 

									    cout << *iter << endl; 

									  else

									    cout << -1 << endl; 

									  cout << endl; 

									  beg=num.lower_bound(2); 

									  end=num.upper_bound(7); 

									  for (; beg != end; beg++) 

									    cout << *beg << " " ; 

									  cout << endl; 

									  ///5. 删除 

									  iter = num.find(1); 

									  num.erase(iter); 

									  cout << num.size() << endl; 

									  for (iter = num.begin(); iter != num.end(); iter++) 

									    cout << *iter << " " ; 

									  cout << endl; 

									  cout << endl; 

									  ///6. 判空与清空 

									  if (!num.empty()) 

									    num.clear(); 

									}