提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

算法与数据结构之集合

算法集合数据结构
2023-06-13 09:14:14 时间

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

相关文章