set/multiset类模板 - C语言学习教程_C语言程序_ c语言编程

set与multiset的区别在于是否允许有重复元素，其他用法都很相似，因此将这两种容器放在一起进行讲解，接下来我们就分别讲解集合对象的创建及其常用的操作方法。

1、创建对象

set与multiset中都重载了不同的构造函数，因此可以以不同的方式定义集合，set集合的定义方式如下所示：

set<T> s;          //创建一个空的set集合，默认升序排列
set<T, op> s;        //创建一个空的set集合，按op规则排序
set<T> s(begin, end);   //创建一个集合，用[begin, end)区间为其初始化
set<T,op> s(begin, end); //创建一个集合，用[begin, end)区间为其初始化，并按op规则排序
set<T> s(s1);        //创建一个空的set集合，用另一个集合s1初始化

set集合提供了五种重载构造函数，接下来我们分别用这五种方式定义不同的集合，代码如下所示：

set<char> s1;
set<int,greater<int>()> s2; 
set<float> s3(begin, end);
set<string, greater<string>()> s4(begin, end);
set<int> s5(s2);

上述代码分别用不同的方式定义了char、int等类型的集合，其中集合s2与s4中的greater<T>则是排序规则，意指从大到小的顺序排列，如果没有排序规则，则默认规则是less<T>，意为从小到大排序，这是STL中定义的函数对象（functor），包含在头文件functional中。

与set集合一样，multiset也重载了这五种构造函数，接下来用这五种方式分别定义不同的multiset集合对象，代码如下所示：

multiset<char> ms1;
multiset <int, greater<int>()> ms2; 
multiset <float> ms3(begin, end);
multiset <string, greater<string>()> ms4(begin, end);
multiset <int> ms5(s2);

上述代码分别用五种不同的方式定义了五个multiset集合对象，其定义中的参数与set集合一样，这里就不再赘述。

多学一招：函数对象

在定义集合时，我们使用到了greater<>()这么一个“函数”，其实它是一个函数对象，所谓函数对象，是行为类似函数的对象。一个类对象表现出函数的特征，就是通过重载()运算符实现的，如果没有上下文，完全可以把它当作一个函数来用。例如，定义下面一个类：

class Sum
{
public:
  int operator()(int a, int b){return a+b;}
}
Sum sum;

这样sum就是一个函数，但在程序中完全可以用sum(1,2)这样的方式调用，它实际上是利用了()运算符的重载。既然函数对象是一个类对象，那么它当然可以在函数参数列表中调用。如果说函数指针是C语言的标志，那么函数对象就可以说是C++中的“函数指针”。

如果运用泛型的思维来思考，可以定义一个函数模板类，实现一般数据类型的相加，代码如下所示：

class Sum
{
public:
  template<typename T>
  T operator()(T t1, T t2){return t1+t2;}
}

STL中就广泛运用了这种技术，定义了一组用于算术、关系、逻辑运算的函数对象，例如上一节所讲解的greater<>与less<>就是STL定义的函数对象。

正确的使用函数对象会使程序性能提高很多，但随之而来的便是一些复杂的问题和陷阱，如何去蔽扬利还需要我们不断学习和探索。

2、集合的大小、元素的查找和统计

集合容器和其他容器一样，提供了获取容器大小的函数size()，判断容器是否为空的函数empty()，以及返回容器可容纳最大元素数量的成员函数max_size()，其函数调用如下所示：

s.size(); //返回容器中元素的数目
s.max_size(); //返回容器中可容纳的最大元素数量
s.empty(); //判断容器是否为空

上述函数调用中的s指集合容器，如无特殊说明，则s既可以是set容器也可以是multiset容器，即两个容器都提供了这样的函数。

集合容器还提供了查找函数find()和统计元素个数的函数count()，函数调用形式如下所示：

s.find(elem);
s.count(elem);

find()函数的功能是返回key元素的位置，返回值是迭代器类型。count()函数的功能是返回元素elem的个数，对于set集合来说，要么是0要么是1，而对于multiset来说，值可能大于1。

3、获取头尾部元素

set与multiset容器提供了begin()与end()函数分别用于获取头尾部元素，函数的调用形式如下所示：

s.begin();  //返回容器中首元素的迭代器
s.end();   //返回容器中最后一个元素之后的迭代器

这两个函数的调用形式和其他容器使用方式相同，这里就不再赘述。

4、插入和删除元素

set与multiset提供了insert()与erase()函数用于向容器中插入和删除元素，insert()有三种实现形式，其调用如下所示：

s.insert(elem);    //在容器中插入元素elem
s.insert(pos, elem); //在pos位置插入元素elem
s.insert(begin, end); //在容器中插入[begin, end)区间的值

对于set容器来说，第一种形式的insert()调用的返回值是pair<iterator, bool>对象，其第一个参数iterator是迭代器，指示元素插入的位置；第二个参数bool类型的值代表元素是否插入成功。

这是因为set容器中不允许存在重复的元素，如果要插入一个容器中已存在的元素，则插入操作会失败，而pair中的bool值就是标识插入是否成功，而multiset不存在这样的情况，因此multiset返回的是一个iterator。

set与multiset提供的erase()函数也有几种实现形式，其函数调用形式如下所示：

s.erase(pos);     //删除pos位置上的元素
s.erase(begin, end); //删除[begin, end)区间上的元素
s.erase(elem);     //删除元素elem

调用erase()函数可以删除某一个位置上的元素，可以删除指定的元素，也可以删除指定范围的元素。

学习了set与multiset容器的几个常用的函数，接下来我们通过一个案例来演示这几个函数的使用，具体如例1所示。

例1

 1    #include <iostream>
 2    #include <set>
 3    #include <functional>
 4    using namespace std;
 5    int main()
 6    {
 7        set<int, greater<int>> s;  //创建一个set容器，元素按降序排列
 8        multiset<char> ms;  //创建一个multiset容器
 9        cout <<"s能容纳的最大元素数量"<< s.max_size() << endl;
 10        cout << "ms能容纳的最大元素数量" << ms.max_size() << endl;
 11        //向s中插入元素
 12        pair<set<int>::iterator, bool> ps;
 13        ps = s.insert(12);
 14        if (ps.second == true)
 15            cout << "insert success" << endl;
 16        s.insert(39);
 17        s.insert(32);
 18        s.insert(26);
 19        //向ms中插入元素
 20        ms.insert('a');
 21        ms.insert('z');
 22        ms.insert('T');
 23        ms.insert('u');
 24        ms.insert('u');
 25        //输出两个容器中的元素
 26        set<int>::iterator its; //创建s容器的迭代器，用于获取元素
 27        cout << "s容器中元素：";
 28        for (its = s.begin(); its != s.end(); its++)
 29            cout << *its << " ";
 30        cout << endl;
 31        multiset<char>::iterator itms;  //创建ms容器的迭代器
 32        cout << "ms容器中元素：";
 33        for (itms = ms.begin(); itms != ms.end(); itms++)
 34            cout << *itms << " ";
 35        cout << endl;
 36    
 37        //查找两个容器中头尾元素
 38        cout << "s头元素： " << *s.begin() << endl;
 39        cout << "ms尾元素： " << *(--ms.end()) << endl;
 40        //查找ms容器中u元素出现的次数
 41        cout <<"ms容器中u元素出现的次数："<< ms.count('u') << endl;
 42        system("pause");
 43        return 0;
 44    }

运行结果如图1所示。

图1 例1运行结果

例1中创建了一个set容器s和一个multiset容器ms，其中容器s中的元素是按降序排列，代码9-10行调用max_size()函数分别算出两个容器的最大容量，代码12-24行分别调用insert()函数向两个容器中插入元素，其中ms容器中插入了重复的元素u，代码26-35行分别创建相应的迭代器输出容器中的元素，由图1可知，s中的元素按降序排列，ms中的元素按升序排列。代码37-38分别调用begin()与end()函数输出s的头元素和ms的尾元素，由图1可知，两个元素输出成功。代码41行调用count()函数输出ms容器中u元素的个数，由图1可知，ms容器中u元素有2个。

多学一招：pair类模板

在头文件utility中，定义了一个类模板pair，其源代码如下所示：

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}

    #ifdef __STL_MEMBER_TEMPLATES
    // 允许使用兼容的pair进行复制构造  
    template <class U1, class U2>
    pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
    #endif
};

其主要作用是将两个数据组成一个数据，用来表示一个二元组或一个元素对，两个数据可以是同一个类型也可以是不同的类型。

当需要将两个元素组合在一起时，可以选择构造pair对象，当一个函数需要返回两个数据的时候也可以选择pair，如上一节讲解集合set的insert()返回值时，其insert()函数返回值就是一个pair对象。接下来我们就来学习一下如何创建pair对象以及如何使用pair对象。

1、创建pari对象

创建pair对象可以调用pair的构造函数，还可以调用STL提供的make_pair()函数，其原型如下所示：

template pair make_pair(T1 a, T2 b){return pair(a,b);}

make_pair()函数内调用的仍然是pair构造函数，下面的代码是分别使用这两种方式来创建pair对象：

pair<int, float> p1; //调用构造函数来创建pair对象
make_pair(1,1.2);   //调用make_pair()函数来创建pair对象

一般make_pair()函数都使用在pair对象作参数的地方，直接调用make_pair()生成的pair对象很方便，代码也很清晰。

2、pair对象的使用

pair类有两个成员first与second，这两个成员可以直接使用，用点操作符就可以访问。first成员对应第一个元素，second成员对应第二个元素，例如下面的代码：

pair<int, float> p1(1, 1.2);
cout << p1.first << endl;
cout << p1.second << endl;

创建了一个pair对象p1，p1.first获取的是第一个元素：int类型的1，p1.second获取的是第二个元素:float类型的1.2。

pair类模板比较简单，读者只要理解会使用即可，在STL中的关联容器中使用较为广泛，其本身也可以嵌套使用。