精华内容
下载资源
问答
  • c++ unordered_set的用法
    千次阅读
    2022-02-23 12:01:14

    本文都是为了方便刷力扣的算法题

    1.背景

            C++ 11 为 STL 标准库增添了 4 种无序(哈希)容器, 本节讲解 unordered_set 容器           unordered_set 容器,可直译为“无序 set 容器”,即 unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。

    2.特性

    1. 不再以键值对的形式存储数据,而是直接存储数据的值。
    2. 容器内部存储的各个元素的值都互不相等,且不能被修改。
    3. 不会对内部存储的数据进行排序(这和该容器底层采用哈希表结构存储数据有关)。

    3.使用容器的条件

    另外,实现 unordered_set 容器的模板类定义在<unordered_set>头文件,并位于 std 命名空间中。这意味着,如果程序中需要使用该类型容器,则首先应该包含如下代码:

    #include <unordered_set>
    using namespace std;

    注意,第二行代码不是必需的,但如果不用,则程序中只要用到该容器时,必须手动注明 std 命名空间(强烈建议初学者使用)。

    4.类模板

    unordered_set 容器的类模板定义如下:

    template < class Key,            //容器中存储元素的类型
               class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
               class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
               class Alloc = allocator<Key>   //指定分配器对象的类型
               > class unordered_set;

    可以看到,以上 4 个参数中,只有第一个参数没有默认值,这意味着如果我们想创建一个 unordered_set 容器,至少需要手动传递 1 个参数。事实上,在 99% 的实际场景中最多只需要使用前 3 个参数(各自含义如表 1 所示),最后一个参数保持默认值即可。

    表 1 unordered_set模板类定义

    参数含义
    Key确定容器存储元素的类型,如果读者将 unordered_set 看做是存储键和值相同的键值对的容器,则此参数则用于确定各个键值对的键和值的类型,因为它们是完全相同的,因此一定是同一数据类型的数据。
    Hash = hash<Key>指定 unordered_set 容器底层存储各个元素时,所使用的哈希函数。需要注意的是,默认哈希函数 hash<Key> 只适用于基本数据类型(包括 string 类型),而不适用于自定义的结构体或者类。
    Pred = equal_to<Key>unordered_set 容器内部不能存储相等的元素,而衡量 2 个元素是否相等的标准,取决于该参数指定的函数。 默认情况下,使用 STL 标准库中提供的 equal_to<key> 规则,该规则仅支持可直接用 == 运算符做比较的数据类型。

    注意,如果 unordered_set 容器中存储的元素为自定义的数据类型,则默认的哈希函数 hash<key> 以及比较函数 equal_to<key> 将不再适用,只能自己设计适用该类型的哈希函数和比较函数,并显式传递给 Hash 参数和 Pred 参数。

    5.创建unordered_set容器

    1) 通过调用 unordered_set 模板类的默认构造函数,可以创建空的 unordered_set 容器。比如:

    std::unordered_set<std::string> uset;

    如果程序已经引入了 std 命名空间,这里可以省略所有的 std::。

    由此,就创建好了一个可存储 string 类型值的 unordered_set 容器,该容器底层采用默认的哈希函数 hash<Key> 和比较函数 equal_to<Key>。

    2) 当然,在创建 unordered_set 容器的同时,可以完成初始化操作。比如:

    std::unordered_set<std::string> uset{ "http://c.biancheng.net/c/",
     "http://c.biancheng.net/java/",
     "http://c.biancheng.net/linux/" };

    通过此方法创建的 uset 容器中,就包含有 3 个 string 类型元素。


    3) 还可以调用 unordered_set 模板中提供的复制(拷贝)构造函数,将现有 unordered_set 容器中存储的元素全部用于为新建 unordered_set 容器初始化。

    例如,在第二种方式创建好 uset 容器的基础上,再创建并初始化一个 uset2 容器:

    std::unordered_set<std::string> uset2(uset);

    由此,umap2 容器中就包含有 umap 容器中所有的元素。


    除此之外,C++ 11 标准中还向 unordered_set 模板类增加了移动构造函数,即以右值引用的方式,利用临时 unordered_set 容器中存储的所有元素,给新建容器初始化。例如:

    //返回临时 unordered_set 容器的函数
    std::unordered_set <std::string> retuset() {
    std::unordered_set<std::string> tempuset{ "http://c.biancheng.net/c/",
    "http://c.biancheng.net/java/",
    "http://c.biancheng.net/linux/" };
    return tempuset;
    }
    //调用移动构造函数,创建 uset 容器
    std::unordered_set<std::string> uset(retuset());

    注意,无论是调用复制构造函数还是拷贝构造函数,必须保证 2 个容器的类型完全相同。


    4) 当然,如果不想全部拷贝,可以使用 unordered_set 类模板提供的迭代器,在现有 unordered_set 容器中选择部分区域内的元素,为新建 unordered_set 容器初始化。例如:

    //传入 2 个迭代器,
    std::unordered_set<std::string> uset2(++uset.begin(),uset.end());

    通过此方式创建的 uset2 容器,其内部就包含 uset 容器中除第 1 个元素外的所有其它元素。

    6.成员方法

    unordered_set 类模板中,提供了如表 2 所示的成员方法。

    表 2 unordered_set 类模板成员方法
    成员方法功能
    begin()返回指向容器中第一个元素的正向迭代器。
    end();返回指向容器中最后一个元素之后位置的正向迭代器。
    cbegin()和 begin() 功能相同,只不过其返回的是 const 类型的正向迭代器。
    cend()和 end() 功能相同,只不过其返回的是 const 类型的正向迭代器。
    empty()若容器为空,则返回 true;否则 false。
    size()返回当前容器中存有元素的个数。
    max_size()返回容器所能容纳元素的最大个数,不同的操作系统,其返回值亦不相同。
    find(key)查找以值为 key 的元素,如果找到,则返回一个指向该元素的正向迭代器;反之,则返回一个指向容器中最后一个元素之后位置的迭代器(如果 end() 方法返回的迭代器)。
    count(key)在容器中查找值为 key 的元素的个数。
    equal_range(key)返回一个 pair 对象,其包含 2 个迭代器,用于表明当前容器中值为 key 的元素所在的范围。
    emplace()向容器中添加新元素,效率比 insert() 方法高。
    emplace_hint()向容器中添加新元素,效率比 insert() 方法高。
    insert()向容器中添加新元素。
    erase()删除指定元素。
    clear()清空容器,即删除容器中存储的所有元素。
    swap()交换 2 个 unordered_map 容器存储的元素,前提是必须保证这 2 个容器的类型完全相等。
    bucket_count()返回当前容器底层存储元素时,使用桶(一个线性链表代表一个桶)的数量。
    max_bucket_count()返回当前系统中,unordered_map 容器底层最多可以使用多少桶。
    bucket_size(n)返回第 n 个桶中存储元素的数量。
    bucket(key)返回值为 key 的元素所在桶的编号。
    load_factor()返回 unordered_map 容器中当前的负载因子。负载因子,指的是的当前容器中存储元素的数量(size())和使用桶数(bucket_count())的比值,即 load_factor() = size() / bucket_count()。
    max_load_factor()返回或者设置当前 unordered_map 容器的负载因子。
    rehash(n)将当前容器底层使用桶的数量设置为 n。
    reserve()将存储桶的数量(也就是 bucket_count() 方法的返回值)设置为至少容纳count个元(不超过最大负载因子)所需的数量,并重新整理容器。
    hash_function()返回当前容器使用的哈希函数对象。


    注意,此容器模板类中没有重载 [ ] 运算符,也没有提供 at() 成员方法。不仅如此,由于 unordered_set 容器内部存储的元素值不能被修改,因此无论使用那个迭代器方法获得的迭代器,都不能用于修改容器中元素的值。

    另外,对于实现互换 2 个相同类型 unordered_set 容器的所有元素,除了调用表 2 中的 swap() 成员方法外,还可以使用 STL 标准库提供的 swap() 非成员函数,它们具有相同的名称,用法也相同(都只需要传入 2 个参数即可),仅是调用方式上有差别。

    下面的样例演示了表 2 中部分成员方法的用法:

    #include <iostream>
    #include <string>
    #include <unordered_set>
    using namespace std;
    
    int main()
    {
    //创建一个空的unordered_set容器
    std::unordered_set<std::string> uset;
    //给 uset 容器添加数据
    uset.emplace("http://c.biancheng.net/java/");
    uset.emplace("http://c.biancheng.net/c/");
    uset.emplace("http://c.biancheng.net/python/");
    //查看当前 uset 容器存储元素的个数
    cout << "uset size = " << uset.size() << endl;
    //遍历输出 uset 容器存储的所有元素
    for (auto iter = uset.begin(); iter != uset.end(); ++iter) {
    cout << *iter << endl;
    }
    return 0;
    }

    程序执行结果为:

    uset size = 3
    http://c.biancheng.net/java/
    http://c.biancheng.net/c/
    http://c.biancheng.net/python/

    更多相关内容
  • unordered_map unordered_set

    unordered_map 和 unordered_set


    unordered_map 是将由键值(key value)和映射值(mapped value)的组合形成的元素的关联容器,并且允许基于其键快速检索单个元素。
    在unorded_map中,键值通常用于唯一标识元素,而映射值是具有与该键值相关联的内容的对象。键和映射值的数据类型可以不同。
    在内部,unorded_map中的元素不以任何特定顺序对其键或映射值排序,而是根据其哈希值组织成桶,以允许通过其键值直接访问各个元素(具有常量平均时间复杂度,即O(1)的时间复杂度)。
    unorded_map容器比map容器更快,以便通过它们的key访问各个元素,尽管它们通常会通过其元素的子集进行范围迭代。
    无序映射实现直接访问运算符(operator[]),允许使用其键值作为参数直接访问映射值。
    容器中的迭代器至少是前向迭代器


    unordered_set 是以无特定顺序存储唯一元素的容器,并且允许根据它们的值快速检索单个元素。
    在unordered_set中,元素的值同时是它的key,它唯一地标识它。键是不可变的,因此, unordered_set中的元素不能在容器中修改一次 - 但是可以插入和删除它们。
    在内部,unordered_set中的元素不是按任何特定顺序排序的,而是根据它们的哈希值组织成桶,以允许直接通过它们的值快速访问单个元素(平均具有恒定的平均时间复杂度)。
    unordered_set容器比set容器更快地通过它们的key访问单个元素,尽管它们通常对于通过其元素的子集进行范围迭代的效率较低。
    容器中的迭代器至少是前向迭代器。


    模板

    std::unordered_map template (C++ 11)

    template < class Key,                                    // unordered_map::key_type
               class T,                                      // unordered_map::mapped_type
               class Hash = hash<Key>,                       // unordered_map::hasher
               class Pred = equal_to<Key>,                   // unordered_map::key_equal
               class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
               > class unordered_map;
    

    std::unordered_set template (C++ 11)

    template < class Key,                        // unordered_set::key_type/value_type
               class Hash = hash<Key>,           // unordered_set::hasher
               class Pred = equal_to<Key>,       // unordered_set::key_equal
               class Alloc = allocator<Key>      // unordered_set::allocator_type
               > class unordered_set;
    

    基础特性

    unordered_map和unordered_set一致。

    • 联想
      关联容器中的元素是通过它们的键而不是它们在容器中的绝对位置来引用的。
    • 无序
      无序容器使用允许通过键快速访问元素的哈希表来组织它们的元素。
    • 映射
      每个元素将一个键关联到一个映射值:键用于标识其主要内容是映射值的元素。
    • 唯一键
      容器中的键是惟一的。
    • 分配器感知
      容器使用分配器对象来动态处理其存储需求。

    成员函数

    unordered_map 和 unordered_set 的成员函数使用方法都一样。

    empty()

    判断容器是否为空。

    • parameters: 无
    • return: 为空返回true,否则false
    // unordered_map::empty
    #include <iostream>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<int,int> first;
      std::unordered_map<int,int> second = {{1,10},{2,20},{3,30}};
      std::cout << "first " << (first.empty() ? "is empty" : "is not empty" ) << std::endl;
      std::cout << "second " << (second.empty() ? "is empty" : "is not empty" ) << std::endl;
      return 0;
    }
    
    Output:
    first is empty
    second is not empty
    
    

    size()

    返回unordered_map中的元素数量。

    • parameters: 无
    • return: 容器中元素数量
    // unordered_map::size
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<std::string,double> mymap = {
           {"milk",2.30},
           {"potatoes",1.90},
           {"eggs",0.40}
      };
    
      std::cout << "mymap.size() is " << mymap.size() << std::endl;
    
      return 0;
    }
    
    Output:
    mymap.size() is 3
    
    

    max_size()

    容器可以容纳的最大元素数量。

    • parameters: 无
    • return: 容器最大元素数量
    // unordered_map limits
    #include <iostream>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<int,int> mymap;
    
      std::cout << "max_size = " << mymap.max_size() << std::endl;
      std::cout << "max_bucket_count = " << mymap.max_bucket_count() << std::endl;
      std::cout << "max_load_factor = " << mymap.max_load_factor() << std::endl;
    
      return 0;
    }
    
    //Possible output:
    //max_size = 357913941
    //max_bucket_count = 357913941
    //max_load_factor = 1
    

    find()

    获取元素的迭代器
    在容器中搜索以k为键的元素,如果找到则返回一个迭代器,否则返回一个迭代器到unordered_map::end(容器末尾的元素)。
    另一个成员函数unordered_map::count可用于检查特定键是否存在。
    映射的值也可以通过使用成员函数at或operator[]直接访问。

    • parameters: key
      要查找的键。
    • return: 如果找到指定的键值,则为元素的迭代器;如果在容器中未找到指定的键,则为unordered_map::end。
    // unordered_map::find
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<std::string,double> mymap = {
         {"mom",5.4},
         {"dad",6.1},
         {"bro",5.9} };
    
      std::string input;
      std::cout << "who? ";
      getline (std::cin,input);
    
      std::unordered_map<std::string,double>::const_iterator got = mymap.find (input);
    
      if ( got == mymap.end() )
        std::cout << "not found";
      else
        std::cout << got->first << " is " << got->second;
    
      std::cout << std::endl;
    
      return 0;
    }
    
    Possible output:
    who? dad
    dad is 6.1
    
    

    count()

    查找具有特定键的元素的数量
    在容器中搜索键为k的元素并返回找到的元素数。因为unordered_map容器不允许重复键,这意味着如果容器中存在具有该键的元素,则该函数实际上返回1 ,否则返回 0。

    • parameters: key
      要查找的键。
    • return: 如果找到具有等效于k的键的元素,则为1,否则为零。
    // unordered_map::count
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<std::string,double> mymap = {
         {"Burger",2.99},
         {"Fries",1.99},
         {"Soda",1.50} };
    
      for (auto& x: {"Burger","Pizza","Salad","Soda"}) {
        if (mymap.count(x)>0)
          std::cout << "mymap has " << x << std::endl;
        else
          std::cout << "mymap has no " << x << std::endl;
      }
    
      return 0;
    }
    
    Output:
    mymap has Burger
    mymap has no Pizza
    mymap has no Salad
    mymap has Soda
    

    insert()

    在unordered_map中插入新元素。
    只有当每个元素的键不等于容器中已经存在的任何其他元素的键时,才会插入每个元素(unordered_map中的键是唯一的)。这通过插入的元素数量有效地增加了容器大小。
    unordered_map 模板类中,提供了多种语法格式的 insert() 方法,根据功能的不同,可划分为以下几种用法。

    1. insert() 方法可以将 pair 类型的键值对元素添加到 unordered_map 容器中,其语法格式有 2 种:
    //以普通方式传递参数
    pair<iterator,bool> insert ( const value_type& val );
    //以右值引用的方式传递参数
    template <class P>
        pair<iterator,bool> insert ( P&& val );
    

    以上 2 种格式中,参数 val 表示要添加到容器中的目标键值对元素;该方法的返回值为 pair类型值,内部包含一个 iterator 迭代器和 bool 变量:

    • 当 insert() 将 val 成功添加到容器中时,返回的迭代器指向新添加的键值对,bool 值为 True;
    • 当 insert() 添加键值对失败时,意味着当前容器中本就存储有和要添加键值对的键相等的键值对,这种情况下,返回的迭代器将指向这个导致插入操作失败的迭代器,bool 值为 False。
    1. 除此之外,insert() 方法还可以指定新键值对要添加到容器中的位置,其语法格式如下:
    //以普通方式传递 val 参数
    iterator insert ( const_iterator hint, const value_type& val );
    //以右值引用方法传递 val 参数
    template <class P>
        iterator insert ( const_iterator hint, P&& val );
    

    以上 2 种语法格式中,hint 参数为迭代器,用于指定新键值对要添加到容器中的位置;val 参数指的是要添加容器中的键值对;方法的返回值为迭代器:

    • 如果 insert() 方法成功添加键值对,该迭代器指向新添加的键值对;
    • 如果 insert() 方法添加键值对失败,则表示容器中本就包含有相同键的键值对,该方法返回的迭代器就指向容器中键相同的键值对;

    注意,以上 2 种语法格式中,虽然通过 hint 参数指定了新键值对添加到容器中的位置,但该键值对真正存储的位置,并不是 hint 参数说了算,最终的存储位置仍取决于该键值对的键的值。

    1. insert() 方法还支持将某一个 unordered_map 容器中指定区域内的所有键值对,复制到另一个 unordered_map 容器中,其语法格式如下:
    template <class InputIterator>
        void insert ( InputIterator first, InputIterator last );
    

    其中 first 和 last 都为迭代器,[first, last)表示复制其它 unordered_map 容器中键值对的区域。

    1. 除了以上 3 种方式,insert() 方法还支持一次向 unordered_map 容器添加多个键值对,其语法格式如下:
    void insert ( initializer_list<value_type> il );
    

    其中,il 参数指的是可以用初始化列表的形式指定多个键值对元素。

    更多样例可以查看http://m.biancheng.net/view/7240.html


    erase()

    从unordered_map容器中删除单个元素或一系列元素([first,last))。
    这有效地通过删除元素的数量来减小容器大小,调用每个元素的析构函数。
    使用方法有如下三种:

    • 通过位置索引:
      指向要从unordered_map中删除的单个元素的迭代器。成员类型const_iterator是前向迭代器类型。
    • 查找指定的键值:
      要擦除的元素的键。成员类型key_type是容器中元素的键的类型,在unordered_map中定义为其第一个模板参数 ( Key ) 的别名。
    • 指定范围:
      指定要删除的unordered_map容器内的范围的迭代器: [first,last)。即,范围包括first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
      请注意,unordered_map容器不遵循任何特定顺序来组织其元素,因此范围删除的影响可能不容易预测。成员类型const_iterator是前向迭代器类型。
    by position (1)	iterator erase ( const_iterator position );
    by key (2)	size_type erase ( const key_type& k );
    range (3)	iterator erase ( const_iterator first, const_iterator last );
    

    return: (1) 和 (3) 返回一个迭代器,该迭代器指向紧跟最后一个被擦除元素的位置。 (2) 返回已擦除元素的数量,在unordered_map容器(具有唯一键)中,如果存在键值为k的元素(因此随后被擦除),则为1 ,否则为零。 成员类型迭代器是前向迭代器类型。 成员类型size_type是无符号整数类型。


    clear()

    清除unordered_map容器中的所有元素。


    Reference

    [1] http://www.cplusplus.com/reference/unordered_map/unordered_map/
    [2] http://www.cplusplus.com/reference/unordered_set/unordered_set/
    [3] http://m.biancheng.net/view/7240.html

    展开全文
  • unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。 unordered_set 容器具有以下几个特性: 不再以键值对的形式存储数据,而是直接存储数据的...

    参考链接

    unordered_set

    unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。

    unordered_set 容器具有以下几个特性:

    • 不再以键值对的形式存储数据,而是直接存储数据的值;
    • 容器内部存储的各个元素的值都互不相等,且不能被修改。
    • 不会对内部存储的数据进行排序(这和该容器底层采用哈希表结构存储数据有关)

    实现 unordered_set 容器的模板类定义在<unordered_set>头文件,并位于 std 命名空间中。

    参数含义
    Key确定容器存储元素的类型,如果读者将 unordered_set 看做是存储键和值相同的键值对的容器,则此参数则用于确定各个键值对的键和值的类型,因为它们是完全相同的,因此一定是同一数据类型的数据。
    Hash = hash指定 unordered_set 容器底层存储各个元素时,所使用的哈希函数。需要注意的是,默认哈希函数 hash 只适用于基本数据类型(包括 string 类型),而不适用于自定义的结构体或者类。
    Pred = equal_tounordered_set 容器内部不能存储相等的元素,而衡量 2 个元素是否相等的标准,取决于该参数指定的函数。 默认情况下,使用 STL 标准库中提供的 equal_to 规则,该规则仅支持可直接用 == 运算符做比较的数据类型。

    创建unordered_set容器

    • 调用 unordered_set 模板类的默认构造函数,可以创建空的 unordered_set 容器

      std::unordered_set<std::string> uset;
      
    • 在创建 unordered_set 容器的同时,可以完成初始化操作。

      std::unordered_set<std::string> uset{ "http://c.biancheng.net/c/",
                                            "http://c.biancheng.net/java/",
                                            "http://c.biancheng.net/linux/" };
      
    • 调用 unordered_set 模板中提供的复制(拷贝)构造函数,将现有 unordered_set 容器中存储的元素全部用于为新建 unordered_set 容器初始化。

      std::unordered_set<std::string> uset2(uset);
      
    • 以右值引用的方式,利用临时 unordered_set 容器中存储的所有元素,给新建容器初始化。

      //返回临时 unordered_set 容器的函数
      std::unordered_set <std::string> retuset() {
          std::unordered_set<std::string> tempuset{ "http://c.biancheng.net/c/",
                                                    "http://c.biancheng.net/java/",
                                                    "http://c.biancheng.net/linux/" };
          return tempuset;
      }
      //调用移动构造函数,创建 uset 容器
      std::unordered_set<std::string> uset(retuset());
      
    • 使用 unordered_set 类模板提供的迭代器,在现有 unordered_set 容器中选择部分区域内的元素,为新建 unordered_set 容器初始化。

      //传入 2 个迭代器,
      std::unordered_set<std::string> uset2(++uset.begin(),uset.end());
      

    unordered_set容器的成员方法

    成员方法功能
    begin()返回指向容器中第一个元素的正向迭代器。
    end();返回指向容器中最后一个元素之后位置的正向迭代器。
    cbegin()和 begin() 功能相同,只不过其返回的是 const 类型的正向迭代器。
    cend()和 end() 功能相同,只不过其返回的是 const 类型的正向迭代器。
    empty()若容器为空,则返回 true;否则 false。
    size()返回当前容器中存有元素的个数。
    max_size()返回容器所能容纳元素的最大个数,不同的操作系统,其返回值亦不相同。
    find(key)查找以值为 key 的元素,如果找到,则返回一个指向该元素的正向迭代器;反之,则返回一个指向容器中最后一个元素之后位置的迭代器(如果 end() 方法返回的迭代器)。
    count(key)在容器中查找值为 key 的元素的个数。
    equal_range(key)返回一个 pair 对象,其包含 2 个迭代器,用于表明当前容器中值为 key 的元素所在的范围。
    emplace()向容器中添加新元素,效率比 insert() 方法高。
    emplace_hint()向容器中添加新元素,效率比 insert() 方法高。
    insert()向容器中添加新元素。
    erase()删除指定元素。
    clear()清空容器,即删除容器中存储的所有元素。
    swap()交换 2 个 unordered_map 容器存储的元素,前提是必须保证这 2 个容器的类型完全相等。
    bucket_count()返回当前容器底层存储元素时,使用桶(一个线性链表代表一个桶)的数量。
    max_bucket_count()返回当前系统中,unordered_map 容器底层最多可以使用多少桶。
    bucket_size(n)返回第 n 个桶中存储元素的数量。
    bucket(key)返回值为 key 的元素所在桶的编号。
    load_factor()返回 unordered_map 容器中当前的负载因子。负载因子,指的是的当前容器中存储元素的数量(size())
    max_load_factor()返回或者设置当前 unordered_map 容器的负载因子。
    rehash(n)将当前容器底层使用桶的数量设置为 n。
    reserve()将存储桶的数量(也就是 bucket_count() 方法的返回值)设置为至少容纳count个元(不超过最大负载因子)所需的数量,并重新整理容器。
    hash_function()返回当前容器使用的哈希函数对象。

    此容器模板类中没有重载 [ ] 运算符,也没有提供 at() 成员方法。不仅如此,由于 unordered_set 容器内部存储的元素值不能被修改,因此无论使用那个迭代器方法获得的迭代器,都不能用于修改容器中元素的值

    #include <iostream>
    #include <string>
    #include <unordered_set>
    using namespace std;
    int main()
    {
        //创建一个空的unordered_set容器
        std::unordered_set<std::string> uset;
        //给 uset 容器添加数据
        uset.emplace("http://c.biancheng.net/java/");
        uset.emplace("http://c.biancheng.net/c/");
        uset.emplace("http://c.biancheng.net/python/");
        //查看当前 uset 容器存储元素的个数
        cout << "uset size = " << uset.size() << endl;
        //遍历输出 uset 容器存储的所有元素
        for (auto iter = uset.begin(); iter != uset.end(); ++iter) {
            cout << *iter << endl;
        }
        return 0;
    }
    

    unordered_multiset容器

    unordered_multiset 容器大部分的特性都和 unordered_set 容器相同,包括:

    • unordered_multiset 不以键值对的形式存储数据,而是直接存储数据的值;
    • 该类型容器底层采用的也是哈希表存储结构,它不会对内部存储的数据进行排序;
    • unordered_multiset 容器内部存储的元素,其值不能被修改。

    unordered_multiset 容器可以同时存储多个值相同的元素,且这些元素会存储到哈希表中同一个桶(本质就是链表)上

    unordered_multiset 除了能存储相同值的元素外,它和 unordered_set 容器完全相同。

    unordered_multiset 容器和 unordered_set 容器共用同一个<unordered_set>头文件,并且也位于 std 命名空间。

    创建 unordered_multiset容器的方法和unordered_set类似,此处略过。

    unordered_multimap容器的成员方法和 unordered_set 类模板一样,此处略过。

    #include <iostream>
    #include <string>
    #include <unordered_set>
    using namespace std;
    int main()
    {
        //创建一个空的unordered_multiset容器
        std::unordered_multiset<std::string> umset;
        //给 uset 容器添加数据
        umset.emplace("http://c.biancheng.net/java/");
        umset.emplace("http://c.biancheng.net/c/");
        umset.emplace("http://c.biancheng.net/python/");
        umset.emplace("http://c.biancheng.net/c/");
        //查看当前 umset 容器存储元素的个数
        cout << "umset size = " << umset.size() << endl;
        //遍历输出 umset 容器存储的所有元素
        for (auto iter = umset.begin(); iter != umset.end(); ++iter) {
            cout << *iter << endl;
        }
        return 0;
    }
    
    展开全文
  • 返回值:此函数返回unordered_set容器中存在的存储桶的当前计数。 #include #include using namespace std; int main() { unordered_set sampleSet; // Inserting elements sampleSet.insert(5); sampleSet.insert...

    目录

    哈希表

    定义

    处理哈希冲突

    1、 开放寻址法

    2、 拉链法

    哈希表的扩容

    哈希表如何读取数据

    散列表的构造方法

    1、 直接定址法

    2、 除留取余法

    3、数字分析法

    4、折叠法

    5、平方取中法

    C++ STL 之 unordered_set 使用

    定义

    模板原型

    基本函数

    1. unordered_set构造

    2. 添加新的元素(无法插入相同的元素)

    3. 查找元素

    4.查找桶接口

    5. 观察器

    6. 清除元素

    7. 其他函数

    基本操作

    1. 迭代器操作

    2. 基本操作

    3. 篮子操作

    4. 内存操作

    5. hash func

    unordered_map的使用

    1、 介绍

    2、 特性:

    3、 迭代器

    4、 操作

    5、 举例代码

    6、 迭代器和bucket操作

    6.1 begin

    6.2 end

    6.3 bucket

    6.4 bucket_count

    6.5 bucket_size

    7、与map的区别


    哈希表

    定义

     哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

    记录的存储位置 = f(关键字)

    这里的对应关系 称为散列函数,又称为哈希(Hash函数),采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。

    哈希表hashtable(key,value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

    (或者:把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。)

    而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    哈希表-CSDN

    https://blog.csdn.net/duan19920101/article/details/51579136

    举例-CSDN

    举例:

    散列函数:由 w -> 王   F()

    在哈希表中是通过哈希函数将一个值映射到另外一个值的,所以在哈希表中,a映射到b,a就叫做键值,而b呢?就叫做a的哈希值,也就是hash值。

    处理哈希冲突

    1、 开放寻址法

    1.1 线性探查法

    1.2 平方探测法

    2、 拉链法

    这里采用的是链表,什么意思呢?就像图中所示,现在张三和李四都要放在1找个位置上,但是张三先来的,已经占了这个位置,待在了这个位置上了,那李四呢?解决办法就是链表,这时候这个1的位置存放的不单单是之前的那个Entry了,此时的Entry还额外的保存了一个next指针,这个指针指向数组外的另外一个位置,将李四安排在这里,然后张三那个Entry中的next指针就指向李四的这个位置,也就是保存的这个位置的内存地址,如果还有冲突,那就把又冲突的那个Entry放在一个新位置上,然后李四的Entry中的next指向它,这样就形成了一个链表。

    哈希表的扩容

    哈希表如何读取数据

    散列表的构造方法

    哈希表原理-CSDN

    1、 直接定址法

    2、 除留取余法

    3、数字分析法

    4、折叠法

    5、平方取中法

    unordered_map、unordered_set使用

    区别-CSDN

    C++ STL 之 unordered_set 使用

    定义

     C++ 11中对unordered_set描述大体如下:无序集合容器(unordered_set)是一个存储唯一(unique,即无重复)的关联容器(Associative container),容器中的元素无特别的秩序关系,该容器允许基于值的快速元素检索,同时也支持正向迭代。
           在一个unordered_set内部,元素不会按任何顺序排序,而是通过元素值的hash值将元素分组放置到各个槽(Bucker,也可以译为“桶”),这样就能通过元素值快速访问各个对应的元素(均摊耗时为O(1))。
           原型中的Key代表要存储的类型,而hash<Key>也就是你的hash函数,equal_to<Key>用来判断两个元素是否相等,allocator<Key>是内存的分配策略。一般情况下,我们只关心hash<Key>和equal_to<Key>参数。

    unordered_set本质是使用hash散列的方式存储数据,是一种使用hash值作为key的容器,所以当有频繁的搜索、插入和移除拥有常数时间。unordered_set存储原理是声明一个有n个桶的数据结构,计算加入到unordered_set的新的值hash,然后计算hash%n后的值x,将新的值加入到桶x中。当桶x中已经有了元素,就直接链接在后边。当数据结构中的元素满足一定数量时我们要扩充桶的数量,并重新构建桶结构。

    unordered_set是一种无序集合,既然跟底层实现基于hashtable那么它一定拥有快速的查找和删除,添加的优点.基于hashtable当然就失去了基于rb_tree的自动排序功能。

    unordered_set无序,所以在迭代器的使用上,set的效率会高于unordered_set。

    模板原型

    template < class Key,  
        class Hash = hash<Key>,  
        class Pred = equal_to<Key>,  
        class Alloc = allocator<Key>  
    > class unordered_set;  


    基本函数

    1. unordered_set构造

    std::unordered_set<std::string> c;  //初始化容器  unordered_set<string>  c;
    std::unordered_set<std::string> c{"aaa","bbb","ccc"};  // 初始化容器,并将“aaa”、“bbb”、“ccc”加入到容器中
    std::unordered_set<std::string> c{16};  //初始化容器,并设置16个桶

    2. 添加新的元素(无法插入相同的元素)

    c.insert("dddd");  //向容器添加元素”dddd"
    a.insert({ "aaa","bbbb","cccc" });  //向容器添加元素"aaa","bbbb","cccc"
    a.insert(b.begin(), b.end());  //b是一个存储着和a相同类型元素的向量,可将b中所有元素添加到a中

    3. 查找元素

    a.find("eeee"):查找元素"eeee",返回结果为a.end()则表明没有找到,否则返回所对应元素
    a.count("eeee"):查找元素"eeee"在a中有几个(由于unordered_set中没有相同的元素,所以结果通常为0或1)  ??
    

    4.查找桶接口

    a.bucket_count():返回数据结构中桶的数量
    a.bucket_size(i):返回桶i中的大小
    a.bucket(“eeee"):返回元素"eeee"在哪个桶里

    存储桶是unordered_set内部哈希表中的一个存储元素的插槽。

    注意:unordered_set中的存储桶从0到n-1编号,其中n是存储桶的总数。

    参数:此函数不接受任何参数。

    返回值:此函数返回unordered_set容器中存在的存储桶的当前计数。

    #include <iostream> 
    #include <unordered_set> 
      
    using namespace std; 
      
    int main() 
    { 
      
        unordered_set<int> sampleSet; 
      
        // Inserting elements 
        sampleSet.insert(5); 
        sampleSet.insert(10); 
        sampleSet.insert(15); 
        sampleSet.insert(20); 
        sampleSet.insert(25); 
      
        cout << "The sampleSet container has " << sampleSet.bucket_count() 
             << " number of buckets\n\n"; 
      
        for (auto itr = sampleSet.begin(); itr != sampleSet.end(); itr++) { 
            cout << "The Element " << (*itr) << " is present in the bucket: "
                 << sampleSet.bucket(*itr); 
            cout << endl; 
        } 
      
        return 0; 
    }

    输出:

    The sampleSet container has 11 number of buckets
    
    The Element 25 is present in the bucket: 3
    The Element 5 is present in the bucket: 5
    The Element 10 is present in the bucket: 10
    The Element 15 is present in the bucket: 4
    The Element 20 is present in the bucket: 9

    5. 观察器

    a.hash_function()("aaa"):返回"aaa"所对应的hash值
    a.key_eq()("aaa","aaaa") :当元素相同时返回true,否则返回false

    6. 清除元素

    a.clear():清除a中所有元素
    a.erase("aaa"):清除元素"aaa"

    7. 其他函数

    a.size():返回a中总的元素个数
    a.max_size():返回a中最大容纳元素
    a.empty():判断a中是否为空

    基本操作

    1. 迭代器操作

        //返回头迭代器 begin()
        unordered_set<int>::iterator ite_begin = c1.begin();
        
        //返回尾迭代器 end()
        unordered_set<int>::iterator ite_end = c1.end();
        
        //返回const头迭代器 cbegin()
        unordered_set<int>::const_iterator const_ite_begin = c1.cbegin();
        
        //返回const尾迭代器 cend()
        unordered_set<int>::const_iterator const_ite_end = c1.cend();
        
        //槽迭代器
        unordered_set<int>::local_iterator local_iter_begin = c1.begin(1);
        unordered_set<int>::local_iterator local_iter_end = c1.end(1);

    2. 基本操作

        //查找函数 find() 通过给定主键查找元素
        unordered_set<int>::iterator find_iter = c1.find(1);
        
        //value出现的次数 count() 返回匹配给定主键的元素的个数
        c1.count(1);
        
        //返回元素在哪个区域equal_range() 返回值匹配给定搜索值的元素组成的范围
        pair<unordered_set<int>::iterator, unordered_set<int>::iterator> pair_equal_range = c1.equal_range(1);
        
        //插入函数 emplace()
        c1.emplace(1);
        
        //插入函数 emplace_hint() 使用迭代器
        c1.emplace_hint(ite_begin, 1);
        
        //插入函数 insert()
        c1.insert(1);
        
        //删除 erase()
        c1.erase(1);//1.迭代器 value 区域
        
        //清空 clear()
        c1.clear();
        
        //交换 swap()
        c1.swap(c2);

    3. 篮子操作

        //篮子操作 篮子个数 bucket_count() 返回槽(Bucket)数
        c1.bucket_count();
        
        //篮子最大数量 max_bucket_count() 返回最大槽数
        c1.max_bucket_count();
        
        //篮子个数 bucket_size() 返回槽大小
        c1.bucket_size(3);
        
        //返回篮子 bucket() 返回元素所在槽的序号
        c1.bucket(1);
        
        //    load_factor    返回载入因子,即一个元素槽(Bucket)的最大元素数
        c1.load_factor();
        
        //    max_load_factor    返回或设置最大载入因子
        c1.max_load_factor();

    4. 内存操作

        //    rehash    设置槽数
        c1.rehash(1);
        
        //    reserve    请求改变容器容量
        c1.reserve(1000);

    5. hash func

        //hash_function() 返回与hash_func相同功能的函数指针
        auto hash_func_test = c1.hash_function();
        
        //key_eq() 返回比较key值得函数指针
        auto key_eq_test = c1.key_eq();

    unordered_map的使用

    关联容器-CSDN

    1、 介绍

    关联容器,内部采用的是hash表结构,拥有快速检索的功能。

    2、 特性:

    • 关联性:通过key去检索value,而不是通过绝对地址(和顺序容器不同)
    • 无序性:使用hash表存储,内部无序
    • Map : 每个值对应一个键值
    • 键唯一性:不存在两个元素的键一样
    • 动态内存管理:使用内存管理模型来动态管理所需要的内存空间

    在这里插入图片描述

    3、 迭代器

    unordered_map的迭代器是一个指针,指向这个元素,通过迭代器来取得它的值。

    unordered_map<Key,T>::iterator it;
    (*it).first;             // the key value (of type Key)
    (*it).second;            // the mapped value (of type T)
    (*it);                   // the "element value" (of type pair<const Key,T>) 
    

    它的键值分别是迭代器的first和second属性。

    it->first;               // same as (*it).first   (the key value)
    it->second;              // same as (*it).second  (the mapped value) 
    

    4、 操作

    • size()     // 返回unordered_map的大小
    • bool empty() const noexcept;      // 为空返回true
    • iterator find ( const key_type& k );      //查找key所在的元素。
                                                               - 找到:返回元素的迭代器。通过迭代器的second属性获取值
                                                               - 没找到:返回unordered_map::end
    • insert //插入
    • mapped_type& at ( const key_type& k );  // 

      查找key所对应的值
      - 如果存在:返回key对应的值,可以直接修改,和[]操作一样。
      - 如果不存在:抛出 out_of_range 异常.

      mymap.at(“Mars”) = 3396; //mymap[“Mars”] = 3396

    • erase()   //  通过位置(迭代器)iterator erase ( const_iterator position );

                           - 通过key   size_type erase ( const key_type& k );

                           - 通过范围(两个迭代器) iterator erase ( const_iterator first, const_iterator last );

    • clear()   //清空unordered_map

    • swap ()  //交换两个unordered_map(注意,不是交换特定元素,是整个交换两个map中的所有元素)

    5、 举例代码

    插入--查找--修改--删除--交换--清空

    // unordered_map::insert
    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    void display(unordered_map<string,double> myrecipe,string str)
    {
        cout << str << endl;
        for (auto& x: myrecipe)
            cout << x.first << ": " << x.second << endl;
        cout << endl;
    }
    
    int main ()
    {
        unordered_map<string,double>
        myrecipe,
        mypantry = {{"milk",2.0},{"flour",1.5}};
    
        /****************插入*****************/
        pair<string,double> myshopping ("baking powder",0.3);
        myrecipe.insert (myshopping);                        // 复制插入
        myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入
        myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入
        myrecipe.insert ({{"sugar",0.8},{"salt",0.1}});    // 初始化数组插入(可以用二维一次插入多个元素,也可以用一维插入一个元素)
        myrecipe["coffee"] = 10.0;  //数组形式插入
    
        display(myrecipe,"myrecipe contains:");
    
        /****************查找*****************/
        unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");
    
        if ( got == myrecipe.end() )
            cout << "not found";
        else
            cout << "found "<<got->first << " is " << got->second<<"\n\n";
        /****************修改*****************/
        myrecipe.at("coffee") = 9.0;
        myrecipe["milk"] = 3.0;
        display(myrecipe,"After modify myrecipe contains:");
    
    
        /****************擦除*****************/
        myrecipe.erase(myrecipe.begin());  //通过位置
        myrecipe.erase("milk");    //通过key
        display(myrecipe,"After erase myrecipe contains:");
    
        /****************交换*****************/
        myrecipe.swap(mypantry);
        display(myrecipe,"After swap with mypantry, myrecipe contains:");
    
        /****************清空*****************/
        myrecipe.clear();
        display(myrecipe,"After clear, myrecipe contains:");
        return 0;
    }

     输出结果:
     

    myrecipe contains:
    salt: 0.1
    milk: 2
    flour: 1.5
    coffee: 10
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    found coffee is 10
    
    After modify myrecipe contains:
    salt: 0.1
    milk: 3
    flour: 1.5
    coffee: 9
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    After erase myrecipe contains:
    flour: 1.5
    coffee: 9
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    After swap with mypantry, myrecipe contains:
    flour: 1.5
    milk: 2
    
    After clear, myrecipe contains:
    

    6、 迭代器和bucket操作

    6.1 begin

      iterator begin() noexcept;
      local_iterator begin ( size_type n );
    
    • begin() : 返回开始的迭代器(和你的输入顺序没关系,因为它的无序的)
    • begin(int n) : 返回n号bucket的第一个迭代器

    6.2 end

      iterator end() noexcept;
      local_iterator end( size_type n );
    
    • end(): 返回结束位置的迭代器
    • end(int n) : 返回n号bucket的最后一个迭代器

    6.3 bucket

    size_type bucket ( const key_type& k ) const;
    

    返回通过哈希计算key所在的bucket(注意:这里仅仅做哈希计算确定bucket,并不保证key一定存在bucket中!)

    6.4 bucket_count

    返回bucket的总数

    6.5 bucket_size

    size_type bucket_size ( size_type n ) const;

    返回第i个bucket的大小(这个位置的桶子里有几个元素,注意:函数不会判断n是否在count范围内)

    // unordered_map::bucket_count
    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    int main ()
    {
        unordered_map<string,string> mymap =
        {
            {"house","maison"},
            {"apple","pomme"},
            {"tree","arbre"},
            {"book","livre"},
            {"door","porte"},
            {"grapefruit","pamplemousse"}
        };
        /************begin和end迭代器***************/
        cout << "mymap contains:";
        for ( auto it = mymap.begin(); it != mymap.end(); ++it )
            cout << " " << it->first << ":" << it->second;
        cout << endl;
        /************bucket操作***************/
         unsigned n = mymap.bucket_count();
    
        cout << "mymap has " << n << " buckets.\n";
    
        for (unsigned i=0; i<n; ++i)
        {
            cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";
            for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
                cout << "[" << it->first << ":" << it->second << "] ";
            cout << "\n";
        }
    
        cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;
        cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;
    
        return 0;
    }
    

    7、与map的区别

    map: map内部实现了一个红黑树,该结构具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素,因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行这样的操作,故红黑树的效率决定了map的效率。
    unordered_map: unordered_map内部实现了一个哈希表,因此其元素的排列顺序是杂乱的,无序的

    展开全文
  • ——unordered_set 参考链接 leetcode题目推荐 用于存放hash散列,其搜索插入移除通常为常数时间,其原理是声明一个有n个桶的数据结构 特点: unordered_set为一种容器,以不特定的顺序存储唯一元素,可根据值检索 ...
  • unordered_map 底层实现完全由hash表代替,所以没有自动排序,适合用于只查找元素...unordered_set> int main() { unordered_map<int, int> unmap; for (int i = 0; i < 30; i++) { unmap.insert
  • unordered_set需要头文件#include <unordered_set> 二者都是基于哈希实现的,无序,因此增删改查的时间复杂度是 O(1),比map和set快,它们是基于平衡二叉树(红黑树)实现的,动态维护有序序列,时间复杂度 O...
  • 参考链接:https://blog.csdn.net/YangLei253/article/details/97621684 介绍 unordered_set 是一个封装哈希表的无序容器,其中每个元素仅可出现一次。 unordered_multi
  • 结论:如果需要内部元素自动排序,使用map,不需要排序使用unordered_map 二、集合 set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能...
  • C++ STL unordered_set使用

    2021-06-02 19:02:27
    C++ STL unordered_set使用
  • set的性质和一些操作 set的底层是红黑树,所以是不支持随机访问的类型,那么迭代器就只能++,–。红黑树就是一个要求不那么严格的平衡二叉树,对于红黑树的内容等后期自己学习一下也会写一篇文章,现在只需知道set和...
  • 哈希表又叫做散列表,它可以用来封装unordered_map和unordered_set。 我们还是按照老规矩来,先介绍其用法,再介绍其原理,并引到哈希上来。 目录 unordered_map/unordered_set的用法 unordered_map/unordered_...
  • unordered_map定义如下: template<class Key, class Ty, class Hash = std::hash<Key>, class Pred = std::equal_to<Key>, class Alloc = std::allocator<std::pair<const Key, Ty> &...
  • unordered_map、unordered_set底层哈希表的实现机理哈希表哈希函数哈希冲突 哈希表 数组的特点是:寻址(查询)容易,插入和删除困难; 链表的特点是:寻址(查询)困难,插入和删除容易。 那么我们能不能综合...
  • unordered_map 头文件#include<unordered_map> unordered_map用于存放键值对,其中元素以pair形式存放。 赋值: 方法一,直接赋值 //赋值方法一:直接赋值; unordered_map<string, int> mp = {...
  • C++的unordered_setunordered_map

    千次阅读 2019-08-16 15:43:34
    set/map的用法和unordered_set/unordered_map的用法完全一样。所以之前我们的3个程序,把unordered_去掉,其他地方不用改,一样可以运行。 set/map不一样的地方是它们内部是用平衡树实现的。所以insert/find/...
  • 3.unordered_set 4.unordered_multiset 关联式容器 关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是'<'key, value'>'结构的键值对,在数据检索时比序列式容器效率更高。 STL中的...
  • 4、multiset容器查找 三、unordered_set 1、setunordered_set区别 2、setunordered_set使用情景 3、unordered_set常用操作 四、unordered_multiset 1、初始化 2、常用操作 3、不常用操作 一、set set是STL中一种...
  • 引言 在STL中,有两种很常见的关联...set/multiset/unordered_set容器 简介 set里面每个元素只存有一个key,保证查询的高效性,且所有元素都会在插入时被自动排序 本质 set的底层是由红黑树实现的(一种平衡二叉搜索
  • STL:unordered_set

    2022-02-22 15:50:49
    在C++11中stl新增了四种哈希相关的容器,其中就有unordered_set。 它和set的区别在于:set:存储的时候自动有序,而unordered_set:是无序状态的 所以unordered_set用几个关键字来叙述就是:无序,去重,key+value...
  • 文章目录 哈希表源代码 哈希表模板参数的控制 string类型无法取模问题 哈希表默认成员函数实现 哈希表正向迭代器的实现 unordered_set的模拟实现 unordered_map的模拟实现 封装完成后的代码 哈希表的代码 正向迭代器...
  • unordered_set的使用

    2022-01-21 15:17:50
    unordered_set 举例: 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 示例 1: 输入:nums = [1,2,3,1] 输出:true 示例 2: 输入:nums = [1...
  • C++常用语法——unordered_set

    千次阅读 2021-10-22 09:30:50
    unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。 unordered_set的几个特性: 不再以键值对的形式存储数据,而是直接存储数据的值 ; ...
  • unordered_set使用介绍

    万次阅读 2019-09-17 13:37:10
    unordered_set C++ 11,新的关联容器:unordered_set 基本介绍 set和map内部实现是基于RB-Tree,而unordered_setunordered_map内部实现是基于哈希表。 unordered_set 容器类型的模板定义在 <unordered_set&...
  • C++_STL——unordered_map、unordered_multimap、unordered_setunordered_multiset 参考:cplusplus 这几种都是拉链法所写的,所以放在一起他们有很多相似之处,以下只记录之前没遇到过的成员函数 遇到不清楚...
  • 由于unorder_set 中不允许重复的元素,因此返回值只要1(k元素存在)或0(k元素不存在)。 五、Modifiers 1.emplace template <class... Args> pair <iterator,bool> emplace ( Args&&
  • (JohnZero)C++:unordered_set

    2020-07-08 15:45:36
    unordered_set是标准的 unordered_set 搜索、插入和移除 拥有平均常数时间复杂度 在内部, 元素并不以任何特别顺序排序, 而是组织进桶中。 元素被放进哪个桶完全依赖其值的哈希。 这允许对单独元素的快速访问, ...
  • C++ STL unordered_set容器完全攻略

    千次阅读 2020-05-02 10:11:06
    我们知道,C++ 11 为 STL 标准库增添了 4 种无序(哈希)容器,前面已经对 unordered_map 和 unordered_multimap 容器做了详细的介绍,本节再讲解一种无序容器,即 unordered_set 容器。 unordered_set 容器,可直译...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,035
精华内容 2,014
关键字:

unordered_set返回值