STL-Set集合

STL-Set集合

• STL-Set集合
  • 导入
  • 构造
  • 插入删除
  • 查找元素
  • 遍历元素
  • 成员方法
  • multiset
  • unordered_set
  • 参考资料

set 集合 unordered_set 无序集合

set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。 set不允许两个元素有相同的键值。

不允许出现相同的两个
set 根据元素的值，系统自动排序

底层原理 hash表

导入

#incude<set>
#incdue<unordered_set>

构造

常见的创建 set 容器的方法，大致有以下 5 种。

std::set<std::string> myset;   //默认构造函数

std::set<std::string> copyset(myset);  //复制构造
//等同于
//std::set<std::string> copyset = myset


set<string> mysets{"python","go","java"};  //构造初始化
std::set<std::string> myset{"python","go","java"};  //构造初始化


std::set<std::string> copyset(++myset.begin(), myset.end());   // 复制初始化


set<string, std::greater<string>> words {"one", "two", "three"};

插入删除

添加元素

//插入数据
set<string>  str_set;
str_set.insert("china");
str_set.insert("us");


set<string, greater<string>> words {"one", "two", "three"};

// 插入单个元素会返回一个 pair<iterator，bool> 对象。
auto pr1 = words.insert("four");
auto pr2 = words.insert ("two") ;

//插入单个元素和一个标识，会返回一个迭代器。
auto iter3 = words.insert(pr.first, "seven");

//插入一段元素或一个初始化列表就不会有返回值。
words.insert ({ "five","six"}) ;

//当 insert() 的参数是初始化列表时，会用列表中的字符串创建 string 对象
string wrds[] {"eight", "nine", "ten"};
words.insert(std::begin(wrds) , std::end(wrds));

删除元素

成员函数 clear() 会删除 set 的所有元素。成员函数 erase() 会删除迭代器指定位置的元素或与对象匹配的元素

//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
    //创建并初始化 set 容器
    std::set<int>myset{1,2,3,4,5};
    cout << "myset size = " << myset.size() << endl;
   
    //1. erase() 方法
    int num = myset.erase(2); //删除元素 2，myset={1,3,4,5}
    cout << "1. myset size = " << myset.size() << endl;
    cout << "num = " << num << endl;
    
    //2. erase() 方法
    set<int>::iterator iter = myset.erase(myset.begin()); //删除元素 1，myset={3,4,5}
    cout << "2. myset size = " << myset.size() << endl;
    cout << "iter->" << *iter << endl;
    
    //3. erase() 方法
    set<int>::iterator iter2 = myset.erase(myset.begin(), --myset.end());//删除元素 3,4，myset={5}
    cout << "3. myset size = " << myset.size() << endl;
    cout << "iter2->" << *iter2 << endl;
    return 0;
}

//myset size = 5
//1. myset size = 4
//num = 1
//2. myset size = 3
//iter->3
//3. myset size = 1
//iter2->5

删除 set 容器中存储的所有元素

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
    //创建并初始化 set 容器
    std::set<int>myset{1,2,3,4,5};
    cout << "1. myset size = " << myset.size() << endl;
    //清空 myset 容器
    myset.clear();
    cout << "2. myset size = " << myset.size() << endl;
    return 0;
   

查找元素

find()函数用于查找具有给定值 val 的元素。如果找到元素，则返回指向该元素的迭代器

否则返回指向集合末尾的迭代器即set :: end()。

#include <iostream>
#include <set>

using namespace std;

int main(void) {
   set<int> m = {100,200,300,400};

   auto it = m.find(300);

   cout << "iter ->  " << *it << endl;

   return 0;
}
//iter ->  300

//打印输出
for(std::set<int>::iterator iter=chars.begin();iter!=chars.end();++iter){
    cout<< *iter<< endl;
    }


set<string> str_set;
str_set.insert("123")
set<string>::iterator  it= str_set.find("123"); 
cout<< *it<< endl;   //如果输出的是 123 则说明找到

//或者     
//返回一个迭代器  iterator  
if(str_set.find("123")!=str_end()){
    cout<<"find 123" <<endl;
}else {
    cout<<"not find 123"<<endl;
}
    
//是否在set中
//str_set.count();	

遍历元素

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main()
{
    std::set<int> numbers{2, 4, 6, 8, 10, 12, 14};


    for (auto  it= numbers.begin(); it != numbers.end(); i++)
        cout << *it << " "; // 注意指针运算符

    numbers.clear();

    return 0;
}

成员方法

multiset

multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

set<T> st;//set默认构造函数： 
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数

#include <iostream>
#include <set>
using namespace std;

void printSetInt(multiset<int> &mset)
{
  
   for (auto  it = mset.begin(); it != mset.end(); it++)
   {
      cout << *it << " ";
   }
   cout << endl;
}
void test()
{
   multiset<int> s;
   s.insert(10);
   s.insert(10);
   s.insert(10);
   printSetInt(s);
}
int main(int argc, char *argv[])
{
   test();
   return 0;
}
10 10 10

unordered_set

unordered_set 和set 区别

底层数据结构： std::set 通常基于树结构（例如红黑树）实现，而 std::unordered_set 则基于哈希表实现。

元素顺序： 由于 std::set 是基于树实现的，所以它的元素是按顺序存储的，这意味着你可以使用迭代器来遍历元素并期望它们以某种顺序出现。相反，std::unordered_set 不保证元素的顺序，也就是说，你无法期望使用迭代器遍历时元素的顺序保持不变。

查找和插入操作的效率：由于 std::set 是基于树结构实现的，所以查找和插入操作的平均时间复杂度为 O(log n)。而 std::unordered_set 使用哈希表，所以查找和插入操作的平均时间复杂度为 O(1)，但是这个 O(1) 性能依赖于哈希函数的工作方式以及哈希表的大小。

空间消耗：由于哈希表的使用，std::unordered_set 在空间上的消耗通常会比 std::set 大一些。

#include <iostream>  
#include <unordered_set>  
  
int main() {  
    std::unordered_set<int> us; // 声明一个整数无序集合  
  
    // 插入元素  
    us.insert(1);  
    us.insert(2);  
    us.insert(3);  
  
    // 查找元素  
    if (us.find(2) != us.end()) {  
        std::cout << "Element 2 is in the set" << std::endl;  
    }  
  
    // 删除元素  
    us.erase(2);  
  
    // 遍历元素  
    for (int x : us) {  
        std::cout << x << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

参考资料

http://c.biancheng.net/view/538.html

http://c.biancheng.net/view/7196.html

http://c.biancheng.net/view/7203.html