第一节 关联容器

set/multiset/map/multimap 内部元素有序排列，新元素插入的位置决定于它的值，查找速度快。 除了各容器都有的函数外，还支持以下成员函数： find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等) lower_bound : 查找某个下界 upper_bound : 查找某个上界 equal_range : 同时查找上界和下界 count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等) insert: 用以插入一个元素或一个区间

第二节 set和multiset

预备知识：**pair**模板 template struct pair{ typedef _T1 first_type; typedef _T2 second_type; _T1 first; _T2 second; pair():first(),second(){}//如果first和second是对象的话，就用无参构造函数来初始化 pair(const _T1&__a,const _T2&__b):first(__a),second(__b){} //构造函数有两个静态变量__a和__b，分别用来初始化first和second template pair(const pair<_U1,_U2>&__p):first(__p.first),second(__p.second){} }; 第三个构造函数是一个函数模板，用以下例子来示例一下： pair<int, int> p(pair<double, double>(5.5,4.6)); //p.first = 5, p.second = 4 1.multiset template<class Key, class Pred = less, class A = allocator > class multiset { …… }; 在这里面，Pred类型的变量决定了multiset中的元素“一个比另一个小”是怎么定义的。multiset运行过程中，比较两个元素x，y的大小的做法，就是生成一个Pred类型的变量，假定为op，若表达式op<x,y>返回值为true，则x比y小。Pred**的缺省值类型是**less。 less模板： template struct less : public binary_function<T, T, bool> { bool operator()(const T& x, const T& y) { return x < y ; } const; }; //less模板是靠 < 来比较大小的 表2.1 multiset的成员函数

函数名

作用

iterator find(const T &val)

在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。

iterator insert(const T & val);

将val插入到容器中并返回其迭代器。

void insert( iterator first,iterator last);

将区间[first,last)插入容器。

int count(const T & val);

统计有多少个元素的值和val相等。

iterator lower_bound(const T & val);

查找一个最大的位置it,使得[begin(),it)中所有的元素都比val小。（返回大于等于val的第一个数字的地址）

iterator upper_bound(const T & val);

查找一个最小的位置it,使得[it,end())中所有的元素都比val大。（返回比val大的第一个数字的地址）

pair<iterator,iterator> equal_range(const T & val);

同时求得lower_bound和upper_bound。

iterator erase(iterator it);

删除it指向的元素，返回其后面的元素的迭代器(Visual studio 2010上如此，但是在C++标准和Dev C++中，返回值不是这样)。

（**1）multiset**的用法 #include using namespace std; class A { }; int main() { multiset a; a.insert(A());//error } 主函数中第一句话没有什么问题，但是第二句话存在问题。因为multiset a等价于multiset<A, less> a，这样插入元素的时候，multiset会将插入元素同已有元素进行比较。由于a中的元素都是A类型的，插入的也是一个A类型的，所以需要对A类型的对象进行比较，这要求A的对象能用<比较，即需要对**<**进行重载。 例程： #include #include using namespace std; template void Print(T first, T last) { for(;first!=last;++first) cout<<*first<<” “; cout<< endl; } class A{ private: int n; public: A(int _n){n = _n;} friend bool operator<(const A &a1, const A &a2){return a1.n<a2.n;} friend ostream & operator<<(ostream & o, const A &a2){o<<a2.n;return o;} friend class MyLess; }; struct MyLess{ bool operator ()(const A & a1, const A & a2)//按个位数比较 {return (a1.n%10)<(a2.n%10);} }; typedef multiset MSET1; typedef multiset<A,MyLess> MSET2;//MSET用MyLess::operator()比较大小 int main(){ const int SIZE = 6; A a[SIZE]={4,22,19,8,33,40}; MSET1 m1; m1.insert(a,a+SIZE); m1.insert(22); cout<<”1)”<<m1.count(22)<<endl;//output:1)2 cout<<”2)”<<Print(m1.begin(),m1.end());//output: 2)4 8 19 22 22 33 40 MSET1::iterator pp = m1.find(19); if(pp!=m1.end()) cout<<”found”<<endl; cout<<”3}”;cout<<*m1.lower_bound(22)<<”,”<<*m1.upper_bound(22)<<endl;//output:22 23 pp = m1.erase(m1.lower_bound(22),m1.upper_bound(22));//pp指向被删除元素的下一个元素 cout<<”4)”;Print(m1.begin(),m1.end());//输出4 8 19 33 40 cout<<”5)”;cout<<*p>>endl;//输出33 MSET2 m2; m2.insert(a,a+SIZE); cout<<”6)”;Print(m2.begin(),m2.end());//输出6)40 22 33 4 8 19 return 0; } 以上程序已弄明白，但是要多看看，理解下。 2.set template<class Key, class Pred = less, class A = allocator> class set{} 插入set中已有元素时，忽略插入。例程如下： #include #include using namespace std; int main() { typedef set::iterator IT; int a[5] = { 3,4,6,1,2 }; set st(a, a + 5); pair<IT,bool> result; result = st.insert(5); if (result.second) cout << *result.first << “inserted” << endl; if (st.insert(5).second) cout << *result.first << endl; else cout << *result.first << “already exists” << endl; pair<IT, IT>bounds = st.equal_range(4); cout << *bounds.first << “.” << *bounds.second; system(“pause”); return 0; } 定义的result是一个pair类型的对象，其里面的first是IT类型，second是bool类型（pair类定义见本节的预备知识）。下面得到的result对象里面的IT就是迭代器指向5所在位置，而second的值为true（因为插入成功）。 if (st.insert(5).second)这句话实际上是先执行了st.insert(5)之后，判断其second值是false还是true。由于前面已经插入了5，所以这里肯定插入不成功，所以second肯定是false。

第三节 map和multimap

1.multimap template<class Key, class T, class Pred = less, class A = allocator> class multimap{ typedef pairvalue_type; };//Key代表关键字的类型 multimap中的元素由 <关键字,值>组成，每个元素是一个pair对象，关键字就是first成员变量,其类型是Key。 multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less 定义关键字的“小于”关系。 例程： #include #include