C++ STL容器之set容器快速入门

发布于 2020-02-08  210 次阅读


set是内部自动有序且不含重复元素的容器。

使用vector需于代码头部添加#include<set>,并且随后加上一句:using namespace std;即可。

set的定义

set<type> name;
其中type可为任何基本类型(如int等)、结构体和STL标准容器。

注意:(1)若type也是STL容器(STL容器嵌套),则需要在>>后加上空格(C++11之前标准的编译会将其视为移位操作)。即set<set<int>> name;。此时可把vector理解成两个维度都可变的二维数组理解。

set数组的定义

set<int> st[100];
这样st[0]到st[100]中每一个set都是一个set容器。
set<set<int>> name;不同的是:这种数组是一维长度为100,另一维长度可变的二维数组。

set容器内元素的访问

和vector容器不同的是,set容器仅能通过迭代器(类似指针)访问

定义:set<typename>::iterator it;

代码:

#include<stdio.h>
#include<set>
using namespace std;
int main(){
    set<int> st;
    //插入元素
    st.insert(3);//insert(x)将x插入set中,并自动去重,时间复杂度O(logN)
    st.insert(5);
    st.insert(2);
    st.insert(3);
    st.insert(4);
    //st.begin()为取st的首元素地址,而it指向此首元素地址
    //遍历元素
    for(set<int>::iterator it1 = st.begin(); it != st.end(); it++){
        //set的迭代器不支持it < vi.end(),因此使用it != vi.end()
        //迭代器it还支持自加和自减各两种操作
        //end()取尾元素地址的下一个地址,即左闭右开
        //end()作为迭代器末尾标志,不存储任何元素
        printf("%d ",*it);
    }
    //查找元素
    set<int>::iterator it2 = st.find(2);
    printf("%d ",*it);//输出2,find(value)返回对应值为value的迭代器,时间复杂度为O(logN)
    printf("%d\n",st.size());  //计算st的长度,输出4,时间复杂度为O(1)
    vi.pop_back();  //删除vi的尾元素5,时间复杂度为O(1)
    //删除单个元素
    //st.erase(vi.begin()+3); 是错误的
    st.erase(st.find(5)); //输出2、3、4,时间复杂度为O(logN)
    //删除一个区间内的所有元素
    set<int>::iterator it3 = st.find(2);
    st.erase(it3, st.end());//删除st[1]、st[2],也就是3和4,即删除[it3,st.end()),时间复杂度为O(st.end()-it3)
    //erase(first, last)删除[first,last),时间复杂度为O(last-first)
    vi.clear();//清空vector中的所有元素,,时间复杂度为O(N)
}

常见用途

自动去重并按升序排序

碰到需要去重却不方便开数组的情况,可以尝试用set解决。

延伸

因为set中元素是唯一的

因此需要处理不唯一元素的情况,可使用multiset

C++11标准中还有unordered_set,以散列替代set内部的红黑树,使其可以用来处理只去重不排序的需求,速度比set快得多。

本文标题:《C++ STL容器之set容器快速入门》

本文链接:https://wnag.com.cn/279.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。