C++ STL中的multiset find()函数

STL中提供了multiset容器，是一个有序容器，可以保存多个相同的元素。它可以自动将元素按照排序规则来进行排序，multiset中的元素插入、删除都是基于红黑树实现的，其中的find()函数也是使用二分查找的方式，效率极高。在本文中，我们将详细介绍multiset中的find()函数。

multiset简介

multiset容器是一个关联式容器，被定义在头文件中，是一个有序容器，也就是说插入元素的时候会按照排序规则自动进行排序。multiset容器可以保存多个相同的元素，不像set容器会进行去重操作，所以multise容器中的size()函数返回的大小可能会大于容器中元素的个数。multiset容器中的元素都是只读的，也就是说不能通过迭代器修改容器中的元素，但可以使用迭代器删除元素。

下面是multiset定义示例：

#include<set>
#include<iostream> 
using namespace std;
int main()
{
    multiset<int> s; 
    s.insert(1);
    s.insert(5);
    s.insert(3);
    for(auto i:s)
    {
        cout<<i<<" ";
    }    
    return 0;
}

输出：

1 3 5

find()函数介绍

multiset中的find()函数用于在容器中查找指定元素，并返回其迭代器，如果未找到，返回的迭代器等于end()函数返回的迭代器。find()函数的原型如下：

iterator find (const key_type& k);

参数k表示要查找的元素。下面是一个示例：

auto it=s.find(3);
if(it!=s.end())
{
    cout<<"Find:"<<*it<<endl;
}
else
{
    cout<<"Not Found"<<endl;
}

输出：

Find:3

如果要查找不存在的元素，可以使用如下代码：

auto it=s.find(4);
if(it!=s.end())
{
    cout<<"Find:"<<*it<<endl;
}
else
{
    cout<<"Not Found"<<endl;
}

输出：

Not Found

使用multiset容器中的find()函数进行查找时，时间复杂度为O(logN)。

总结

multiset容器是一个方便进行排序操作的关联式容器，通过使用find()函数，可以方便快捷地在multiset容器中查找指定的元素。multiset容器中的find()函数底层使用的是基于二分查找方式进行查找，效率非常高。