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;
}