欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[STL]Set和Multisets

程序员文章站 2022-05-19 10:04:51
...

本篇图片代码取自:The C++ Standard Libarary 第六章第五节,p175页,读者若有不清楚可以自行翻阅

Set和Multiset

set和multiset会根据特定的排序准则,自动将元素排序,而这两者的区别就是multiset允许元素重复而set不允许。
[STL]Set和Multisets
在使用set或者multiset之前我们必须先包含入头文件 #include<set>
在这个头文件中,上述两个型别都被定义为命名空间std内的class templates;


template<class _Kty,
    class _Pr = less<_Kty>,
    class _Alloc = allocator<_Kty> >
class set

template<class _Kty,
    class _Pr = less<_Kty>,
    class _Alloc = allocator<_Kty> >
class multiset

其中可有可无的第二个templates参数用来定义排序准则,如果没有传入准则,就采用默认的缺省准则less,这是一个仿函数,以operator<对元素进行比较,以便完成排序。
关于排序准则:
1.必须使反对称的。
对operator<而言,如果x

Sets和Multisets的能力

和所有标准关联上容器类似,set和multisets通常以平衡二叉树来实现,实际上通常用红黑树来实现,因为红黑树在改变元素和元素搜寻方面都很出色。
优缺点:自动排序的优点是使得搜寻元素时具有良好的性能,具有对数时间复杂度。
缺点就是:不能直接改变元素值,因为这样会打乱原有的顺序,改变元素值的方法是:先删除旧元素,再插入新元素。
存取元素只能通过迭代器,从迭代器的角度看,元素值是常数。

Sets和Multisets的操作函数

生成、复制、销毁
构造函数和析构函数:
[STL]Set和Multisets
其中set可为下列形式:
[STL]Set和Multisets

有两种方式可以定义排序准则:
1、以template参数定义:

std::set<int,std::greater<int> > coll;

注意两个>>之间要加一个空格否则编译器会视为亦为操作符
2、以构造函数参数定义:
这种情况下,同一个型别可以运用不同的排序准则,而排序准则的初始值或状态也可以不同。如果执行期才获得排序准则,而且需要用到不同的排序准则,此一方式可以派上用场。

#include <iostream>
#include "print.hpp"
#include <set>
using namespace std;

template <class T>
class RuntimeCmp{
public:
    enum cmp_mode{normal,reverse};
private:
    cmp_mode mode;
public:
    RuntimeCmp(cmp_mode m = normal):mode(m){}

    bool operator()(const T &t1,const T &t2)
    {
        return mode == normal ? t1 < t2 : t2 < t1;
    }

    bool operator==(const RuntimeCmp &rc)
    {
        return mode == rc.mode;
    }
};

typedef set<int,RuntimeCmp<int> > IntSet;

void fill(IntSet& set);

int main()
{
    IntSet set1;
    fill(set1);
    PRINT_ELEMENTS(set1,"set1:");

    RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);

    IntSet set2(reverse_order);
    fill(set2);
    PRINT_ELEMENTS(set2,"set2:");

    set1 = set2;//assignment:OK
    set1.insert(3);
    PRINT_ELEMENTS(set1,"set1:");

    if(set1.value_comp() == set2.value_comp())//value_comp Returns the comparison object associated with the container
        cout << "set1 and set2 have the same sorting criterion" << endl;
    else
        cout << "set1 and set2 have the different sorting criterion" << endl;
}

void fill(IntSet &set)
{
    set.insert(4);
    set.insert(7);
    set.insert(5);
    set.insert(1);
    set.insert(6);
    set.insert(2);
    set.insert(5);
}

程序输出如下:
coll1: 1 2 4 5 6 7
coll2 :7 6 5 4 2 1
coll1: 7 6 5 4 3 2 1
coll1 and coll2 have same sorting criterion

Sets和Multisets的非变动性操作:
[STL]Set和Multisets
Sets和Multisets的搜寻操作函数:
[STL]Set和Multisets

赋值

sets和multisets只提供所有容器都提供的基本赋值操作,见下表:
[STL]Set和Multisets
Sets和Multisets的迭代器相关操作函数
[STL]Set和Multisets
Sets和Multisets的元素安插和移除
[STL]Set和Multisets

sets提供如下接口:

pair<iterator,bool> insert(const value_type& elem); 
iterator  insert(iterator pos_hint, const value_type& elem);

关于队组(pair)我有博客作了介绍,有需要的小伙伴请自行取阅:Pair是什么?
multsets提供如下接口:

iterator  insert(const value_type& elem); 
iterator  insert(iterator pos_hint, const value_type& elem);

返回值型别不同的原因是set不允许元素重复,而multiset允许。当插入的元素在set中已经包含有同样值的元素时,插入就会失败。所以set的返回值型别是由pair组织起来的两个值。
第一个元素返回新元素的位置,或返回现存的同值元素的位置。第二个元素表示插入是否成功。set的第二个insert函数,如果插入失败,就只返回重复元素的位置!
但是,所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数,在各种容器中有共通接口。

Sets应用实例

#include <iostream>
#include <set>

int main()
{
    // type of the collection
    typedef std::set<int> IntSet;

    IntSet coll;        // set container for int values

    /* insert elements from 1 to 6 in arbitrary order
     * - value 1 gets inserted twice
     */
    coll.insert(3);
    coll.insert(1);
    coll.insert(5);
    coll.insert(4);
    coll.insert(1);
    coll.insert(6);
    coll.insert(2);

    /* print all elements
     * - iterate over all elements
     */
    IntSet::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

对于multisets,微微改变

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

int main()
{
    /* type of the collection:
     * - duplicates allowed
     * - elements are integral values
     * - descending order
     */
    typedef multiset<int,greater<int> > IntSet;

    IntSet coll1;        // empty multiset container

    // insert elements in random order
    coll1.insert(4);
    coll1.insert(3);
    coll1.insert(5);
    coll1.insert(1);
    coll1.insert(6);
    coll1.insert(2);
    coll1.insert(5);

    // iterate over all elements and print them
    IntSet::iterator pos;
    for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
        cout << *pos << ' ';
    }
    cout << endl;

    // insert 4 again and process return value
    IntSet::iterator ipos = coll1.insert(4);
    cout << "4 inserted as element "
         << distance(coll1.begin(),ipos) + 1 << endl;

    // assign elements to another multiset with ascending order
    multiset<int> coll2(coll1.begin(),
                        coll1.end());

    // print all elements of the copy
    copy (coll2.begin(), coll2.end(),
          ostream_iterator<int>(cout," "));
    cout << endl;

    // remove all elements up to element with value 3
    coll2.erase (coll2.begin(), coll2.find(3));

    // remove all elements with value 5
    int num;
    num = coll2.erase (5);
    cout << num << " element(s) removed" << endl;

    // print all elements
    copy (coll2.begin(), coll2.end(),
          ostream_iterator<int>(cout," "));
    cout << endl;
}

结果如下:
6 5 5 4 3 2 1
4 inserted as element 5
1 2 3 4 4 5 5 6
2 element(s) removed
3 4 4 6