c++ 常用STL 之set_std::set内存结构

在文章c++ 常用STL 之vector_kangshuangzhu的博客-CSDN博客

中介绍了序列容器，并且系统介绍了vector的用法。不难发现，无论是哪种序列式容器，其存储的都是 C++ 基本数据类型（诸如 int、double、float、string 等）或使用结构体自定义类型的元素。例如，如下是一个存储 int 类型元素的 vector 容器：

std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
关联式容器则大不一样，此类容器在存储元素值的同时，还会为各元素额外再配备一个值（又称为“键”，其本质也是一个 C++ 基础数据类型或自定义类型的元素），它的功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。

常用的关联式容器包括set map

下面会着重介绍一下set

set  定义在 <set> 头文件中，使用该容器存储的数据，各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。该容器会自动根据各个元素的键（其实也就是元素值）的大小进行升序排序（调用 std::less<T>）。

set的存储方式是平衡二叉树，所以可以快速实现有序的插入元素

 这里仍然从初始化，增，删，改，查5个方面入手，

初始化：

set的初始化和vector比较像，可以空初始化；赋值初始化；拷贝其他set，但是拷贝初始化的时候拷贝的一定要是另一个set，如果是其他的容器则会报错。

    std::vector<int> my_vec = {1,2,3,3,4,3,6};
    std::set<int> s1;  // 初始化一个空set
    std::set<int> s2 = {4,5,3,6,2,7};  // 赋值初始化一个set
    std::set<int> s3(s2);  //  拷贝s2的元素
    std::set<int> s3(my_vec);  //  报错
    std::set<int> s4(s2.begin(),++s2.begin());  // 取某一段内存的数据初始化
    std::set<int> s4(s2.begin(),s2.begin()+3); //报错，set迭代器不支持这种运算
    std::set<int> s5(my_vec.begin(), my_vec.end()); // 取某一段内存的数据初始化
    std::set<int> s6 = {my_vec.begin(), my_vec.end()}; // 取某一段内存的数据初始化

应用最灵活的还是用迭代器初始化，同样的，用迭代器初始化，不要求迭代器是set的迭代器，任何迭代器都可以。

应该格外注意的是set的迭代器不支持s.begin()+3 这种运算，但是却支持s.begin()++ 和 ++ s.begin() 。后面如果找到原因会在这里补上。

查：

因为元素是有序的插入到set中的，所以，set是无序的，不能用下表或者at函数来取某一个值。

find 查询set是否包含某一个元素，如果存在则返回迭代器，如果没有则返回end

    std::set<int> s2 = {4,5,3,6,2,7};  // 赋值初始化一个set
    auto k = s2.find(3);
    std::cout << "(k == s2.end()) " << (k == s2.end()) << std::endl;
    auto s = s2.find(30);
    std::cout << "(s == s2.end()) " << (s == s2.end()) << std::endl;
 
输出 
(k == s2.end()) 0
(s == s2.end()) 1

size()  获取set的大小

empty（）set是否为空

    std::set<int> s2 = {4,5,3,6,2,7};  // 赋值初始化一个set
    std::cout << "set size " << s2.size() << std::endl;
 
输出
set size 6

遍历set

set的遍历方式有两种。因为set时无需集合，所以不能通过下标的方式遍历。

    std::set<int> s2 = {4,5,3,6,2,7};  // 赋值初始化一个set    
    for (auto i: s2){
        std::cout << i << " ";
    }
    for(auto i = s2.begin(); i != s2.end(); i++){
        std::cout << *i << " ";
    }
    for(auto i = s2.begin(); i < s2.end(); i++){  //报错
        std::cout << *i << " ";
    }

set的第二种遍历有一个地方需要注意，终止循环的条件不能写成 

i < s2.end()

而要写成

i != s2.end()

增

set提供一个insert函数用于新增元素，因为set会对元素自动排序，新增元素的时候无所谓插入位置。虽然insert 可以指定插入位置，但插入后会自动排序，所以指定的插入位置没有用

    std::set<int> s2 = {4,5,3,6,2,7};
    s2.insert(10);
    for (auto i: s2){
        std::cout << i << " ";
    }
    s2.insert(s2.begin(), 20);
    for(auto i = s2.begin(); i != s2.end(); i++){
        std::cout << *i << " ";
    }
 
输出
2 3 4 5 6 7 10
2 3 4 5 6 7 10 20

这种指定插入位置的用法可能会逐渐废弃，所以不推荐使用

当然insert还是支持插入一个迭代器的，在插入迭代器的时候，不能指定插入位置。例如

    std::set<int> s2 = {4,5,3,6,2,7}; 
    std::set<int> s3({-1,-2,-3,-4}); 
    s2.insert({10,20,30});
    for (auto i: s2){
        std::cout << i << " ";
    }
    s2.insert(s3.begin(), s3.end());
    for(auto i = s2.begin(); i != s2.end(); i++){
        std::cout << *i << " ";
    }
 
输出
2 3 4 5 6 7 10 20 30
-4 -3 -2 -1 2 3 4 5 6 7 10 20 30

删：

clear()，删除set 所有值

set的删除函数时erase，因为set的元素有唯一性，所以对于基本数据结构可以直接输入一个值进行删除

    std::set<int> s2 = {4,5,3,6,2,7};
    s2.erase(6);
    for (auto i: s2){
        std::cout << i << " ";
    }
 
输出
2 3 4 5 7

当然也可以通过迭代器删除，但是因为set迭代器不支持 begin()+2 以及 < , > , <=,  >= 这些操作。所以想删除某一段数据会比较繁琐。

    std::set<int> s2 = {4,5,3,6,2,7}; 
    auto it = s2.find(5);
    s2.erase(it,s2.end());
    for (auto i: s2){
        std::cout << i << " ";
    }
 
输出
2 3 4 

改

swap 与 vector相同，可以看文章c++ 常用STL 之vector_kangshuangzhu的博客-CSDN博客