/*
 *
 ********************************************
 *   multiset多重集合容器的基础说明：
 ********************************************
 *
 * multiset多重集合容器使用RB-Tree的平衡二叉检索树的数据结构。
 * 允许将重复键值的元素插入到multiset中
 * 插入过程中要进行平衡处理，但检索过程效率高
 *
 * 提供了元素插入、删除、检索的功能
 * Sorted Associative Container  Simple Associative Container   Multiple Associative Container
 *
 * 使用multisetr必须使用宏语句#include <set>   //与set相同
 *
 **************************************************************************************
 *
 * 创建multisetr对象:
 * template < class Key, class Compare=less<Key>, class Alloc=alloc >
 *
 * 1.multisetr<int> a;
 * 2.multisetr(const key_compare& comp)    //指定一个比较函数对象comp来创建set对象，详细使用见main()中示例
 *  3.multisetr(const multisetr&);      //multisetr<int> b(a);
 * 4.multisetr(first,last);       //multisetr<char> c(a.begin(),a.end())
 * 5.multisetr(first,last,const key_compare& comp); //依据comp函数进行插入排序
 **************************************************************************************
 *
 * 元素的插入
 * iterator insert(const value_type& v);    //不再是返回pair，而是插入的迭代器位置
 * iterator insert(iterator pos,const value_type& v);
 * void insert(first,last);
 *
 **************************************************************************************
 *
 * 元素的删除
 * void erase(iterator pos);
 * size_type erase(const key_type& k);     //删除等于键值k的元素
 * void erase(first,last);        //删除[first,last)区间的元素
 * void clear();
 *
 **************************************************************************************
 *
 * 访问与搜索
 *
 * iterator begin();iterator end();     //企图通过迭代器改变元素是不被允许的
 * reverse_iterator rbegin();reverse_iterator rend();
 *
 * iterator find(const key_type& k) const;
 * pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
 *                //first为lower_bound(k);大于等于k的第一个元素位置
 *                //second为upper_bound();大于k的第一个元素位置
 *
 * 其它常用函数
 * bool empty() const;
 * size_type size() const;
 * size_type count(const key_type& k) const;   //返回键值等于k的元素个数
 * void swap();
 *
 * //main中包含了一下函数的简单例子
 * iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
 *
 *
 *
 ********************************************
 **   cumirror ** tongjinooo@163.com **    **
 ********************************************
 *
 */

#include <set>
#include <iostream>

// 自定义数据的插入
struct student{
 char name[20];
 int age;
 char city[20];
 char phone[20];
};

// 这里采用函数对象的方式设置,与set中有不同,key设置为city,注意应设置为public
class stuCmp{
public:
 bool operator()(const student& a,const student& b) const{
  return strcmp(a.city,b.city)<0;
 }
};

// 对于一些基本数据类型，如int，string等可参照set
int main(){
 using namespace std;
 student stu1={"童进",23,"长沙","XXX"};
 student stu2={"老大",28,"武汉","XXX"};    //老大，你成熟了5岁，哈哈
 student stu3={"饺子",23,"福州","XXX"};
// multiset<student,stuCmp> b;       
 multiset<student,stuCmp> b(stuCmp());
 b.insert(stu1);
 b.insert(stu2);
 b.insert(stu3);
// 武汉同学最多,只是现在大家又都天各一方
 student stu4={"小芳",23,"武汉","XXX"};
 student stu5={"黄庆",23,"武汉","XXX"};
 student stu6={"英俊",23,"武汉","XXX"};
 b.insert(stu4);
 b.insert(stu5);
 b.insert(stu6);

 for(multiset<student,stuCmp>::iterator i=b.begin();i!=b.end();i++){
  cout<<i->name<<endl;
 }

 student key={"",99,"武汉","XXX"};
 cout<<"武汉朋友数目："<<b.count(key)<<endl;
 cout<<"武汉的第一个朋友："<<b.lower_bound(key)->name<<endl;
 cout<<"武汉最后一个朋友："<<(--b.upper_bound(key))->name<<endl; // 这里武汉是最后的,再大于这个键值,就会返回end()指向头节点,所以--
 for(multiset<student,stuCmp>::reverse_iterator j=b.rbegin();j!=b.rend();j++){
  cout<<j->name<<endl;
 }

// 验证set中的猜测,此时键值为city
 student test={"路人甲",99,"武汉","XXX"};    
 multiset<student,stuCmp>::iterator v=b.find(test); //返回第一个与键值相等的迭代器  
 cout<<"寻找武汉的路人甲："<<v->name<<endl;

// 元素搜索
 cout<<"搜索武汉的朋友们："<<endl;
 pair<multiset<student,stuCmp>::iterator,multiset<student,stuCmp>::iterator> p=b.equal_range(test);
 for(multiset<student,stuCmp>::iterator k=p.first;k!=p.second;k++){
  cout<<k->name<<endl;
 }
 return 0;
}