c++ 无序容器的桶管理

 

无序容器在存储上组织为一个“桶”,每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素,容器首先计算元素的哈希值,它指出应该搜索哪个“桶”。容器将具有一个特定哈希值的所有元素都保存在相同的“桶”中。如果容器允许重复关键字,所有具有相同关键字的元素也都会在一个“桶”中。因此,无序容器的性能依赖于哈希函数的质量和“桶”的容量和大小。

对于相同的参数,哈希函数必须总是生成相同的结果。理想情况下,哈希函数还能将每个特定的值映射到唯一的“桶”。但是,将不同关键字的元素映射到相同的“桶” 也是允许的。当一个“桶”保存多个元素时,需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在“桶”中搜索通常都是很快的操作。但是,如果一个“桶”保存的很多元素,那么查找一个特定的元素就需要大量的比较操作。

无序容器提供了一组管理“桶”的函数,这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

无序容器有:unordered_set, unordered_map,unordered_multimap, unordered_multiset. 分别定义在unordered_set和unordered_map的头文件中

  • 桶接口:

    • c.bucket_count() 正在使用的桶的数目
    • c.max_bucket_count() 容器能容纳的最多的桶的数目
    • c.bucket_size(n) 第n个桶中有多少个元素
    • c.bucket(k)关键字为k的元素在哪个桶中
  • 桶迭代:

    • local_iterator 可以用来访问桶中元素的迭代类型
    • const_local_iterator const版本
      无序容器对关键字类型的要求:默认情况下,无序容器使用关键字类型的==运算符来比较元素,它们还是用hash<key_type>类型的对象来生成每个哈希值。标准库为内置类型(包括指针)提供了hash模板。

我们不能直接定义关键字类型为自定义类类型的无序容器,与容器不同,不能直接使用哈希模板,必须提供我们自己的hash模板版本。

 


用无序容器降低时间复杂度,相当是用空间换时间:leetcode_Two Sum

[cpp]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;//empty vector
unordered_map<int, size_t> m;

    for (size_t i = 0; i != nums.size(); ++i) {
        m.insert({nums[i], i });
    }
    for (size_t j = 0; j != nums.size(); ++j) {
        int com = target - nums[j];
        if (m.find(com) != m.end() &amp;&amp; m[com] != j) {
            ret.push_back(j);
            ret.push_back(m[com]);
            break;
        }
    }

    return ret;

    //Time complexity : O(n)

    //time complexity  O(n^2)
    /*
    bool find = false;
    for (size_t i = 0; i != nums.size() &amp;&amp; !find; ++i) {
        for (size_t j = i + 1; j != nums.size() &amp;&amp; !find; ++j) {
            if (nums[i] + nums[j] == target) {
                ret.push_back(i);
                ret.push_back(j);
                find = true;
            }
        }
    }*/
}

};
[/cpp]

注:摘自<<c++ primer>> 第五版

您的支持将鼓励我继续分享~