关于STL中set容器的一些总结

2022-05-15 0 339
关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序

1.关于set

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。

 关于set有下面几个问题:

(1)为何map和set的插入删除效率比用其他序列容器高?

大部分人说,很简单,因为对于关联容器来说,不需要做内存拷贝和内存移动。说对了,确实如此。set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。结构图可能如下:

  A
/ \
B C
/ \ / \
D E F G

因此插入的时候只需要稍做变换,把节点的指针指向新的节点就可以了。删除的时候类似,稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去,和内存移动没有关系。

(2)为何每次insert之后,以前保存的iterator不会失效?

iterator这里就相当于指向节点的指针,内存没有变,指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说,每一次删除和插入,指针都有可能失效,调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放,iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候,容器内部空间可能不够,需要一块新的更大的内存,只有把以前的内存释放,申请新的更大的内存,复制已有的数据元素到新的内存,最后把需要插入的元素放到最后,那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候,牢记这个原则:不要使用过期的iterator。

(3)当数据元素增多时,set的插入和搜索速度变化如何?

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找,也就是说,如果有16个元素,最多需要比较4次就能找到结果,有32个元素,最多比较5次。那么有10000个呢?最多比较的次数为log10000,最多为14次,如果是20000个元素呢?最多不过15次。看见了吧,当数据量增大一倍的时候,搜索次数只不过多了1次,多了1/14的搜索时间而已。你明白这个道理后,就可以安心往里面放入元素了。

2.set中常用的方法

——————————————————————————–

begin()        ,返回set容器的第一个元素

end()      ,返回set容器的最后一个元素

clear()          ,删除set容器中的所有的元素

empty()    ,判断set容器是否为空

max_size()   ,返回set容器可能包含的元素最大个数

size()      ,返回当前set容器中的元素个数

rbegin     ,返回的值和end()相同

rend()     ,返回的值和rbegin()相同

写一个程序练一练这几个简单操作吧:

代码如下:
#include
#include

using namespace std;

int main()
{
    set s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout<<"set 的 size 值为 :"<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 :"<<s.max_size()<<endl;
    cout<<"set 中的第一个元素是 :"<<*s.begin()<<endl;
    cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;
    s.clear();
    if(s.empty())
    {
        cout<<"set 为空 !!!"<<endl;
    }
    cout<<"set 的 size 值为 :"<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 :"<<s.max_size()<<endl;
    return 0;
}
</s.max_size()<<endl;
</s.size()<<endl;
</endl;
</endl;
</endl;
</s.max_size()<<endl;
</s.size()<<endl;

运行结果:关于STL中set容器的一些总结

小结:插入3之后虽然插入了一个1,但是我们发现set中最后一个值仍然是3哈,这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的,使用前最好使用empty()检验一下set是否为空.

——————————————————————————–

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。

示例代码:


#include
#include

using namespace std;

int main()
{
    set s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout<<"set 中 1 出现的次数是 :"<<s.count(1)<<endl;
    cout<<"set 中 4 出现的次数是 :"<<s.count(4)<<endl;
    return 0;
}
</s.count(4)<<endl;
</s.count(1)<<endl;

运行结果:关于STL中set容器的一些总结

equal_range() ,返回一对定位器,分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素,这个返回值是一个pair类型,如果这一对定位器中哪个返回失败,就会等于end()的值。具体这个有什么用途我还没遇到过~~~

示例代码:

#include
#include

using namespace std;

int main()
{
    set s;
    set::iterator iter;
    for(int i = 1 ; i <= 5; ++i)
    {
        s.insert(i);
    }
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    pair<set::const_iterator,set::const_iterator> pr;
    pr = s.equal_range(3);
    cout<<"第一个大于等于 3 的数是 :"<<*pr.first<<endl;
    cout<<"第一个大于 3的数是 : "<<*pr.second<<endl;
    return 0;
}
</endl;
</endl;
</set</endl;

运行结果:关于STL中set容器的一些总结

erase(iterator)  ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之间的值

erase(key_value),删除键值key_value的值

看看程序吧:

#include
#include

using namespace std;

int main()
{
    set s;
    set::const_iterator iter;
    set::iterator first;
    set::iterator second;
    for(int i = 1 ; i <= 10 ; ++i)
    {
        s.insert(i);
    }
    //第一种删除
    s.erase(s.begin());
    //第二种删除
    first = s.begin();
    secOnd= s.begin();
    second++;
    second++;
    s.erase(first,second);
    //第三种删除
    s.erase(8);
    cout<<"删除后 set 中元素是 :";
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    return 0;
}
</endl;

运行结果:关于STL中set容器的一些总结

小结:set中的删除操作是不进行任何的错误检查的,比如定位器的是否合法等等,所以用的时候自己一定要注意。

——————————————————————————–

find()  ,返回给定值值得定位器,如果没找到则返回end()。

示例代码:

#include
#include

using namespace std;

int main()
{
    int a[] = {1,2,3};
    set s(a,a+3);
    set::iterator iter;
    if((iter = s.find(2)) != s.end())
    {
        cout<<*iter<<endl;
    }
    return 0;
}
</endl;

insert(key_value); 将key_value插入到set中 ,返回值是pair<set::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。</setinset(first,second);将定位器first到second之间的元素插入到set中,返回值是void.

示例代码:


#include
#include

using namespace std;

int main()
{
    int a[] = {1,2,3};
    set s;
    set::iterator iter;
    s.insert(a,a+3);
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    pair<set::iterator,bool> pr;
    pr = s.insert(5);
    if(pr.second)
    {
        cout<<*pr.first<<endl;
    }
    return 0;
}
</endl;
</set</endl;

运行结果:关于STL中set容器的一些总结

lower_bound(key_value) ,返回第一个大于等于key_value的定位器

upper_bound(key_value),返回最后一个大于等于key_value的定位器

示例代码:

#include
#include

using namespace std;

int main()
{
    set s;
    s.insert(1);
    s.insert(3);
    s.insert(4);
    cout<<*s.lower_bound(2)<<endl;
    cout<<*s.lower_bound(3)<<endl;
    cout<<*s.upper_bound(3)<<endl;
    return 0;
}
</endl;
</endl;
</endl;

运行结果:关于STL中set容器的一些总结

收藏 (0) 打赏

感谢您的支持,我们会继续努力的!

打开支付宝/微信/QQ扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

1. 本站所有教学内容和资源均来源于本站原创和网络收集以及用户自主上传,如有侵权请带证联系本站客服进行处理!邮箱:team@lcwl.fun
2. 对于非本站原创的资源不保证所提供下载资源的准确性、安全性和完整性,资源仅供下载学习之用!如有链接无法下载、失效或广告,请联系本站客服处理,有奖励!
3. 除本站原创教学或资源外其余资源您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!
4. 本站原创资源如需商用还请申请商业授权,否则本站有权追究其法律责任!
5. 如果您也有好的资源或教程,您可以投稿发布,成功分享后有学币奖励额外收入!

凌晨资源网 后端开发 关于STL中set容器的一些总结 https://www.lingchenw.cn/1612.html

一个在为了梦想而努力的无名小白

常见问题
  • 本站所有付费教程均可单独付费或者开会员学习,自己购买或者开了会员就可以学习,来凌晨学院报名学习送会员,并且有讲师一对一辅导培训教学,师生互动化,定期布置作业等
查看详情
  • 本站所有资源版权均属于原作者所有,资源中标注可商用的可以商用的代表是本团队自主研发公布可商用的产品,未标注可商用所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
查看详情

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务

学习手机编程软件开发
手机编程软件开发

你知道吗?用手机也能开发制作软件,满足自己的编程心,做属于自己的软件

报名学习
自媒体短视频
副业做自媒体短视频

想做自媒体短视频剪辑给自己多一份副业,只需一部手机你也可以

报名学习
搭建网站必备云互联主机
链未云互联

搭建网站,后台云服务等必备云服务器互联主机,IDC云主机

现在使用
Fa快捷助手
用手点一点就能开发做软件

不用记编程语法,不用一行一行手敲代码,用手点一点就能开发制作软件

点击下载