算法与数据结构之集合

C++为我们提供了集合这个内置的数据结构，它是基于二叉搜索树来实现的，并且对树进行了平衡处理，使得元素在树中分布较为均匀。因此，能保证它搜索、插入、删除操作的时间复杂度为O(logn)

set是stl的内置数据结构，它包含以下的成员函数：

函数名	功能	复杂度
size()	返回set中的元素数	O(1)
clear()	清空set	O(1)
begin()	返回指向set开头的迭代器	O(1)
end()	返回指向set末尾的迭代器	O(1)
insert(key)	向set中插入元素key	O(logn)
find(key)	搜索与key一致的元素，并返回指向该元素的迭代器。若没有与key一致的元素，则返回指向set末尾的迭代器	O(logn)
erase(key)	删除值为key的元素	O(logn)

需要注意的是，指向set末尾的迭代器，指向的是最后一个元素的下一位的内存地址。（如果不是这样的话，那在搜索的时候，如果key与集合最后一个元素相同的话，就会得出无法找到元素的结论了）

下面一个例子给出了set的集中用法：

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

void print(set<int>s)
{
    cout<<s.size()<<":";
    for(set<int>::iterator it = s.begin(); it!=s.end();it++)
    {
        cout<<" "<<(*it);
    }
    cout<<endl;
}

int main()
{
    set<int>s;
    s.insert(8);
    s.insert(1);
    s.insert(7);
    s.insert(4);
    s.insert(8);
    s.insert(4);
    print(s);

    s.erase(7);

    print(s);

    s.insert(2);

    print(s);

    if(s.find(4)==s.end()) cout<<"not found"<<endl;
}