【C++】unordered 系列关联式容器-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】unordered 系列关联式容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【C++】unordered 系列关联式容器,C++,哈希算法,c++,数据结构,算法

1. unordered 系列关联式容器

在 C++ 98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 $log_2 N$ ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是：进行很少的比较次数就能将元素找到，因此在 C++ 11 中，STL 又提供了 4 个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对 unordered_map 和 unordered_set 进行介绍。

2. unordered_map

2.1 unordered_map 的文档介绍

unordered_map

unordered_map 是存储 <key, value> 键值对的关联式容器，其允许通过 keys 快速的索引到与其对应的 value。
在 unordered_map 中，键值通常用于唯一的标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部，unordered_map 没有对 <key, value> 按照任何特定的顺序排序，为了能在常数范围内找到 key 所对应的 value，unordered_map 将相同哈希值的键值对放在相同的桶中。
unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_map 实现了直接访问操作符（operator[]），它允许使用 key 作为参数直接访问 value。
它的迭代器至少是前向迭代器。

2.2 unordered_map 的接口说明

unordered_map 的构造

函数声明功能介绍

unordered_map 构造不同格式的 unordered_map 对象
unordered_map 的容量

函数声明功能介绍

bool empty() const 检测 unordered_map 是否为空

size_t size() const 获取 unordered_map 的有效元素个数

函数声明	功能介绍
unordered_map	构造不同格式的 unordered_map 对象

函数声明	功能介绍
bool empty() const	检测 unordered_map 是否为空
size_t size() const	获取 unordered_map 的有效元素个数

unordered_map 的迭代器

函数声明	功能介绍
begin	返回 unordered_map 第一个元素的迭代器
end	返回 unordered_map 最后一个元素下一个位置的迭代器
cbegin	返回 unordered_map 第一个元素的 const 迭代器
cend	返回 unordered_map 最后一个元素下一个位置的 const 迭代器

unordered_map 的元素访问

函数声明功能介绍

operator[] 返回 key 对应的 value，没有返回一个默认值

注意：该函数中实际调用哈希桶的插入操作，用参数 key 与 V() 构造一个默认值往底层哈希桶中插入，如果 key 不再哈希桶中，插入成功，返回 V()；插入失败，说明 key 已经在哈希桶中，将 key 对应的 value 返回。
unorder_map 的查询

函数声明功能介绍

iterator find(const K& key) 返回 key 在哈希桶中的位置

size_t count(const K& key) 返回哈希桶中关键码为 key 的键值对的个数

注意：unordered_map 中 key 是不能重复的，因为 count 函数的返回值最大为 1。

函数声明	功能介绍
operator[]	返回 key 对应的 value，没有返回一个默认值

函数声明	功能介绍
iterator find(const K& key)	返回 key 在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为 key 的键值对的个数

unordered_map 的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map 的桶操作

函数声明	功能介绍
size_t bucket_count() const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n) const	返回 n 号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素 key 所在的桶号

3. unordered_set

参见 unordered_set 在线文档说明。

4. 在线 OJ

在长度 2N 的数组中找出重复 N 次的元素

class Solution
{
public:
    int repeatedNTimes(vector<int>& nums)
    {
        int n = nums.size() / 2;
        
        // 用 unordered_map 统计每个元素出现的次数
        unordered_map<int, int> hash;
        for (auto& e : nums)
        {
            ++hash[e];
        }

		// 找出出现次数为 n 的元素个数
        for (auto& e : hash)
        {
            if (e.second == n)
            {
                return e.first;
            }
        }

        return 0;
    }
};

两个数组的交集

class Solution
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
    	// 使用 unordered_set 去重
        unordered_set<int> us1;
        for (auto& e : nums1)
        {
            us1.insert(e);
        }

        unordered_set<int> us2;
        for (auto& e : nums2)
        {
            us2.insert(e);
        }

		// 遍历 us1，在 us2 中寻找 us1 的每个元素，如果找到，即为交集
        vector<int> ret;
        for (auto& e : us1)
        {
            if (us2.find(e) != us2.end())
            {
                ret.push_back(e);
            }
        }

        return ret;
    }
};

两个数组的交集 Ⅱ

class Solution
{
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
    	// 使用 unordered_map 统计次数
        unordered_map<int, int> um1;
        for (auto& e : nums1)
        {
            ++um1[e];
        }

        unordered_map<int, int> um2;
        for (auto& e : nums2)
        {
            ++um2[e];
        }

		// 遍历 um1，在 um2 中查找 um1 的各个元素，并找到该元素出现次数的较小值
        vector<int> ret;
        for (auto& e : um1)
        {
            auto it = um2.find(e.first);
            if (it != um2.end())
            {
                // 找较小值
                int less = e.second;
                if (e.second > (*it).second)
                {
                    less = (*it).second;
                }

                // 插入
                for (int i = 0; i < less; i++)
                {
                    ret.push_back(e.first);
                }
            }
        }

        return ret;
    }
};

存在重复元素

class Solution
{
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int, int> um;
        // 我们把 nums 各元素插入到 unordered_map 中
        for (auto& e : nums)
        {
        	// 如果在插入之前发现该元素已经存在于 unordered_map 中，说明该元素是重复的
            if (um.find(e) != um.end())
            {
                return true;
            }

            ++um[e];
        }

        return false;
    }
};

两句话中的不常见单词文章来源地址https://www.toymoban.com/news/detail-847866.html

class Solution
{
public:
    vector<string> uncommonFromSentences(string s1, string s2)
    {
    	// 分析题意，发现要找的单词就是在两个句子中只出现一次的单词
        string str = s1 + " " + s2 + " ";
        unordered_map<string, int> um;

        // 分割字符串入哈希表
        int begin = 0, end = 0;
        while (begin < str.size())
        {
            // size_t find (const string& str, size_t pos = 0) const;
            end = str.find(" ", begin);

            // string (const string& str, size_t pos, size_t len = npos);
            int npos = end - begin;
            string key(str, begin, npos);
            
            ++um[key];
            begin = end + 1;
        }

        // 找到出现次数为 1 的单词
        vector<string> ret;
        for (auto& e : um)
        {
            if (e.second == 1)
            {
                ret.push_back(e.first);
            }
        }

        return ret;
    }
};