STL中set与map的使用

这次写的是STL中set与map的相关知识点以及优先队列的部分补充内容以及重载运算符的使用。
首先介绍一下set与multiset：
set 和 multiset会根据特定的排序准则（set容器内部由红黑树实现，插入删除查找的效率都非常高，而且是自动排序、去重），自动将元素排序，两者的不同之处在于multiset可以允许元素重复而set不允许元素重复（因此set又被称为集合）。
而map与multimap与它们的不同之处是map与multimap是以映射形式存储元素，一下就存储一对关联元素，形成pair：
另外类似的：所有元素都会根据元素的键值自动排序，map的所有元素都是pair，pair的第一个元素被视为键值，第二个元素为实值。map不允许两个元素有相同的键值，但multimap可以。
注意在使用set或map之前都要先定义好对应的头文件。

对于操作的不同：
set与multiset:
s.insert(elem) – 安插一个elem副本，返回新元素位置。类似于堆栈及队列中的push()与向量vector中push_back类似，但是每种数据结构都有它的方式。
s.erase(elem) – 移除与elem元素相等的所有元素，返回被移除的元素个数。
s.erase(pos) – 移除迭代器pos所指位置上的元素，无返回值。
注意erase()中elem与pos是不同的数据类型，pos是迭代器，类似于指针操作，指向一个地址，而elem是存入multiset的数据类型，代表含义不同。
s.clear() – 移除全部元素，将整个容器清空。一般最后选择清空容器。
s.size() – 返回容器大小。
s.empty() – 返回容器是否为空。
在s.earse(elem)中引入了迭代器的概念：
迭代器可以通过以下方式定义：

multiset <int> :: iterator pos;
	for(pos = s.begin(); pos != s.end(); pos++)
		... ...

其中包括数据类型multiset，所指数据类型int，以及迭代器名称pos。
在此定义中，迭代器pos类似于指针的作用。当要输出multiset的某一点的值时可以在pos前加*，输出该数据。
另外还有一个重要的统计容器中相同数据的方法：
s.count(elem) – 返回元素值为elem的元素的个数。
当然这只是针对multiset，因为set我们在上面说过它是一种集合类型，不允许存放多个相同数据，所以s.count(elem)对set没有意义。
对于查找时的函数可以使用find()函数，find()函数使用二分查找法查找元素，并返回元素的初始地址。

对于map与multimap和set的区别是可以同时定义两种数据类型，形成一对pair：
map <data_type1, data_type2> map_name;
如：map <string, int> m;//默认按string由小到大排序
这里就要提到键值，键值即一对pair中的第一个数据，所有的排序规则，查找准则都依靠键值决定。
另外对于map来说，可以通过键值对其直接赋值存取，例如：
m[key] = value；
查找的时候如果没有键值为key的元素，则安插一个键值为key的新元素，实值为默认(一般0)。
看着类似于数组形式（其中m是map名）。
对于m的元素插入有三种方法：
m.insert(elem) 插入一个元素elem
a)运用value_type插入
map<string, float> m;
m.insert(map<string, float>:: value_type (“Robin”, 22.3));
看上去十分繁琐。
b) 运用pair<>
m.insert(pair<string, float>(“Robin”, 22.3));
c) 运用make_pair()
m.insert(make_pair(“Robin”, 22.3));
以后使用make_pair的情况会相对多一些，因为使用make_pair不用记录map的存储的两种数据类型，直接对map进行插入元素即可。

另外补充一下优先队列的概念，优先队列：
如：priority_queue q;//默认是大顶堆，在其内部通过二叉树的结构进行排列，所以其内部数据并非都是按照从大到小依次进行如此排列，其内部数据的排列顺序是没有纯粹的从大到小的队列规律的。
二叉树的排列规则对于选取首个元素输出的结构相对于从大到小全排列便捷很多，能使数据更加快速的进行筛选，每次新输入的数据都会与之前的数据进行比较，而且只需比较一条路径即可，相对于全排序更有优势。另外当删除栈顶（队头）元素后，最后一个元素到达树顶然后进行比较处理。
当然我们可以通过重载小于号使数据按照自己的规则进行排序，例：

struct T1{
    int key;
    int value1, value2;
    bool operator<(const T1 &b)const{
        return (key < b.key);
    }

该排序规则按照结构体的key值进行从大到小排序。

#define pow2(a) ((a)*(a))
#define dist2(x, y) (pow2(x) + pow2(y))
struct coord{
    int x, y;
    const bool operator<(const coord &b)const{
        return (dist2(x, y) < dist2(b.x, b.y));
    }
};

该排序规则按照结构体内x.y的平方和大小进行从大到小排序。
其中#define pow2(a) ((a)*(a))
#define dist2(x, y) (pow2(x) + pow2(y))
是定义的伪函数，表示平方和。