C++中STL容器的分类和基本功能（二）：集合(set) 映射(map)

关联容器


特点：
每个关联容器都有一个键(key)
每个元素按键的取值升序排列（对于一个关联容器，使用迭代器s在区间[s.begin(), s.end())内遍历，访问到的序列总是升序）

优势：
可以根据键值高效地查找元素

要求：键值的类型必须能够用 < 比较
int、double等基本数据类型
其他重载了 < 运算符的类型

例：学生表的存储
class Student{...};
map<string, Student> student;

最简单的关联容器：
集合set


数学中的集合
一些同质元素的共同体
不含重复的元素
不讲究顺序
有限集合/无限集合

STL中的set
存储一组数据
无重复的元素
有序（为了进行高效的查找）

有限集合

#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>
#include <set>
#include <utility>
using namespace std;

int main()
{
	set <double> s;
	pair<set<double>::iterator, bool> r;
	while(true)
	{
		double v;
		cin >> v;
		if(v == 0)
		{
			break;
		}
		r = s.insert(v);
		if(!r.second)  //当输入出现相同的元素时 r.secong将会出现false 重复的元素并不会插入到集合r中
		{
			cout << v << "duplicated" << endl;
		}
	}
	
	set<double>::iterator iter1 = s.begin();
	set<double>::iterator iter2 = s.end();
	double medimun = (*iter1 + *(--iter2)) / 2;
	cout << "medimun" << medimun << endl;
	cout << "<=medimun";
	copy(s.begin(), s.upper_bound(medimun), ostream_iterator<double>(cout));
	/*ForwardIter lower_bound(ForwardIter first, ForwardIter last, const_Tp& val)算法返回一个非递减序列[first,last)中第一个大于等于值val的位置*/
	cout << endl;
	cout << ">=medimun";
	copy(s.lower_bound(medimun), s.end(), ostream_iterator<double>(cout));
	/*ForwardIter upper_bound(ForwardIter first, ForwardIter last, const_Tp& val)算法返回一个非递减序列[first,last)中第一个大于值val的位置*/
	cout << endl;
	
	system("pause");
	return 0;
}

输出： 1 2 3 3 5 4 2 0
3duplicated
2duplicated
medimun3
<= medimun 123
>= medimun 345
/************************************************************************************************************/

映射(map)


映射与集合相同点：
一组无重复有序数据

映射与集合的主要区别
集合的元素类型是键本身
映射的元素类型是由键和附加数据所构成的二元组
map<string, int>courses;


在映射中按照键查找一个元素时，除了能确定它的存在性外，还可以得到形影的附加数据


map的元素类型(pair)
template<class T1, class T2>
struct pair
{
T1 first;
T2 second;
...
}

#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <algorithm>  
#include <string>
#include <map>
#include <utility>
using namespace std;

int main()
{
	map<string, int> courses;
	courses.insert(make_pair("C++", 3));   //make_pair返回结构体数据
	courses.insert(make_pair("C", 2));
	courses.insert(make_pair("C++", 10));
	courses.insert(make_pair("C++", 10));
	courses.insert(make_pair("COMPILER", 1));
	courses.insert(make_pair("ENGLISH", 3));
	courses.insert(make_pair("OS", 4));
	
	int n = 3;
	int sum = 0;
	string name;
	map<string, int>::iterator iter;
	//从中选3门课 计算学分
	while(n > 0)
	{
		cin >> name;
		iter = courses.find(name);
		if(iter == courses.end())
		{
			cout << "can not find name" << name << endl;
		}
		else
		{
			sum += iter->second;
			courses.erase(iter);
			n--;
		}
	}	
	
	cout << "total credit: " << sum << endl;
	system("pause");
	return 0;
}

输出：
C C++ OS
total credit: 9

/************************************************************************************************************/

关联容器分类


简单关联容器：
容器只有一个类型参数(set<T>)
容器的元素就是键本身

二元关联容器：
容器只有两个类型参数，分别表示键和附加数据的类型
容器的元素类型是pair<K,V>，即由键类型和元素类型符合而成的二元组

单重关联容器(set和map):
键值是唯一的，一个键值只能对应一个元素


多重关联容器(多重集合：multiset 和 多重映射multimap)：
键值是不唯一的，一个键值可以对应多个元素
多重集合是允许有重复元素的集合
多重映射是允许一个键对应多个附加数据的映射

#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <algorithm>  
#include <string>
#include <map>
#include <utility>
using namespace std;

int main()
{
	multimap<string, string> courses;
	courses.insert(make_pair("C++", "1-2"));
	courses.insert(make_pair("C", "1-6"));
	courses.insert(make_pair("C++", "2-2"));
	courses.insert(make_pair("C++", "3-2"));
	courses.insert(make_pair("COMPILER", "3 -2"));
	courses.insert(make_pair("COMPILER", "4-2"));
	courses.insert(make_pair("ENGLISH", "5-2"));
	courses.insert(make_pair("OS", "5-6"));
	
	int count;
	string name;
	map<string, int>::iterator iter;
	//输入课程名称 输出每周上课的次数与时间
	do
	{
		cin >> name;
		count = courses.count(name);
		if(count == 0)
		{
			cout << "can not find this course" << endl;
		}
	} while(count == 0);
	cout << count << " " << "lesson per week" << endl;
	typedef multimap<string, string>::iterator CourseIter;
	pair<CourseIter, CourseIter> range;
	range = courses.equal_range(name);  //返回结构体数据
	for(CourseIter iter = range.first; iter != range.second; ++iter)
	{
		cout << iter->second << " " << endl;
	}
	
	system("pause");
	return 0;
}

输出： D 
can not find this course
C
1 lesson per week
1-6