首页 > 代码库 > C++ set学习笔记

C++ set学习笔记

2024-09-19 22:01:03   207人阅读

Stl~(multi)set

 

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等

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

常用操作：

begin() 返回指向第一个元素的迭代器

clear() 清除所有元素

count() 返回某个值元素的个数，多用于存在性判断，值只能是0或1

empty() 如果集合为空，返回true

end() 返回指向最后一个元素的迭代器

equal_range() 返回集合中与给定值相等的上下限的两个迭代器

erase() 删除集合中的元素

find() 返回一个指向被查找到元素的迭代器

get_allocator() 返回集合的分配器

insert() 在集合中插入元素

lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器

key_comp() 返回一个用于元素间值比较的函数

max_size() 返回集合能容纳的元素的最大限值

rbegin() 返回指向集合中最后一个元素的反向迭代器

rend() 返回指向集合中第一个元素的反向迭代器

size() 集合中元素的数目

swap() 交换两个集合变量

upper_bound() 返回大于某个值元素的迭代器

value_comp() 返回一个用于比较元素间的值的函数


1.元素插入：insert()

insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。

if(pr.second)
   {
      cout<<*pr.first<<endl;
   }

inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.
2.中序遍历：类似vector遍历（用迭代器）
3.反向遍历：利用反向迭代器reverse_iterator。
    例：
    set<int> s;
    ......
    set<int>::reverse_iterator rit;
    for(rit=s.rbegin();rit!=s.rend();rit++)
4.元素删除：与插入一样，可以高效的删除，并自动调整使红黑树平衡。
            set<int> s;
            s.erase(2);        //删除键值为2的元素
            s.clear();

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

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

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


5.元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。
            set<int> s;
            set<int>::iterator it;
            it=s.find(5);    //查找键值为5的元素
            if(it!=s.end())    //找到
                cout<<*it<<endl;
            else            //未找到
                cout<<"未找到";

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

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


6.自定义比较函数
    (1)元素不是结构体：
        例：
        //自定义比较函数myComp,重载“（）”操作符
        struct myComp
        {
            bool operator()(const your_type &a,const your_type &b)
            [
                return a.data-b.data>0;
            }
        }
        set<int,myComp>s;
        ......
        set<int,myComp>::iterator it;
    (2)如果元素是结构体，可以直接将比较函数写在结构体内。
        例：
        struct Info
        {
            string name;
            float score;
            //重载“<”操作符，自定义排序规则
            bool operator < (const Info &a) const
            {
                //按score从大到小排列
                return a.score<score;
            }
        }
        set<Info> s;
        ......
        set<Info>::iterator it;

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

set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。

不能直接改变元素值。因为这样会打乱原有的顺序。

改变元素值的方法是：先删除旧元素，再插入新元素。

存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。

  1. #include <iostream>  
  2. #include <set>  
  3. using namespace std;  
  4. 程序运行会报错。但是如果把s1的排序准则也指定为greater<int>便运行成功  
  5. int main()  
  6. {  
  7.     set<int> s1;  
  8.     set<int,greater<int> > s2;  
  9.   
  10.     for (int i = 1;i < 6;++i)  
  11.     {  
  12.         s1.insert(i);  
  13.         s2.insert(i);  
  14.     }  
  15.     if(s1 == s2)  
  16.         cout << "c1 equals c2 !" << endl;  
  17.     else  
  18.         cout << "c1 not equals c2 !" << endl;  
  19. }  
  20. //此处分割线--------------------------------------------------------------------------------------
  21. set 的几种操作
  22.         set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));
  23.         cout << "A u B = {";
  24.         print(c);
  25.         c.clear();
  26.         set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));
  27.         cout << "A n B = {";
  28.         print(c);
  29.         c.clear();
  30.         set_difference(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));
  31.         cout << "A - B = {";
  32.         print(c);
  33.         c.clear();
  34.         set_difference(b.begin(),b.end(),a.begin(),a.end(),inserter(c,c.begin()));
  35.         cout << "SA = {";
  36.         print(c);
  37.         c.clear();
  38.         set_difference(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()));
  39.         cout << "SB = {";
  40.         print(c)
  41.  

C++ set学习笔记


联系
我们