重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
C++容器篇，unordered-创新互联
C++容器——unordered_set和unordered_map容器
1. unordered系列关联式容器
2.2.3 unordered_map的容量
2.2.4 unordered_map的元素访问
2.2.5 unordered_map的修改和查询
2.2.6 unordered_map的桶操作
3. unordered_set
本文标题：C++容器篇，unordered-创新互联
网站网址：http://cqcxhl.cn/article/csigji.html
在C++98中，STL提供了以红黑树为底层结构的关联容器，在查找时的效率可以达到O(log_2(n))，当树的结点非常多的时候，查找的效率也不离校。因此在C++11，STL有提供了四个unordered系列的关联式容器，这些容器的底层是哈希桶，查找的效率可以达到常数级别。
unordered_map的参考文档
- unordered_map是存储
- 在内部，unordered_map没有进行任何特定的顺序排序，这是因为底层的数据结构所导致的。
- unordered_map通过key访问单个元素要比map快，它通常在遍历元素子集的范围迭代方面效率较低。
- 它也是重载了
(operator [])运算符，通过将key作为下标访问对应的value值。 - 它的迭代器至少是前向迭代器。
unordered_map必须包含头文件#include，并且属于std命名空间里面。
#include#include#includeusing namespace std;
int main()
{unordered_mapm;
m[0] = "hello";
m[1] = "world";
m[2] = ".";
auto it = m.begin();
while (it != m.end())
{cout<< it->first<< " : "<< it->second<< " "; // 0 : hello 1 : world 2 : .
++it;
}
cout<< endl;
} 其实unordered_map与map的区别并不大，主要是底层使用的数据结构的不同，导致效率和顺序性有所差异。
2.2.1 unordered_map的定义| 构造函数 | 接口说明 |
|---|---|
| unordered_map(); | 无参构造 |
2.2.2 unordered_map的迭代器
- 第一个是无参构造，构造一个空的unordered_map，传入的模板参数有key，value的类型，比较器的类型（默认是less）。
unordered_map不存在反向迭代器，因为存入到容器中的数据顺序是乱序的，因此没有办法从最后一个位置向前遍历。
| 迭代器的使用 | 使用说明 |
|---|---|
| begin() | 返回指向开始位置的迭代器 |
| end() | 返回指向末尾元素的下一个位置的迭代器 |
| cbegin() | 返回指向开始并且为常量的迭代器 |
| cend() | 返回指向末尾元素的下一个位置的并且为常量的迭代器 |
| 容量说明 | 接口说明 |
|---|---|
| size | 获取容器中实际的个数 |
| empty | 判断是否为空 |
| 函数 | 接口说明 |
|---|---|
| mapped_type& operator[](const key_type& k) | 获取key对应的value值，如果key存在，则无需插入到unordered_map中，直接返回key对应的value值，如果key不存在，会将对应的key和value值插入到unordered_map中。 |
| 增删改查 | 接口说明 |
|---|---|
| pair insert(const value_type& x) | 在unordered_map中插入键值对新插入位置的迭代器,true，否则返回，key对应位置的迭代器,false。 |
| erase(iterator pos) | 删除unordered_map中pos位置的元素。 |
| erase(const value_type& x) | 删除unordered_map中键值对为x的元素 |
| swap(unordered_map& m) | 交换unordered_map中的元素 |
| find(const key_type& x) | 在unordered_map中查找key为x的元素，找到返回该元素位置的迭代器，找不到返回end() |
| count(const key_type& x) | 返回unordered_map中key值为x的元素的个数 |
| clear | 清除unordered_map的元素 |
| 函数声明 | 功能介绍 |
|---|---|
| size_t bucket_count() const | 返回哈希桶中桶的总个数 |
| size_t bucket_size(size_t n) const | 返回n号桶中有效元素的总个数 |
| size_t bucket(const K& key) | 返回元素key所在的桶号 |
参考：
unordered_set的参考文档
4. 在线OJ重复n次的元素
class Solution
{public:
int repeatedNTimes(vector& A)
{size_t N = A.size()/2;
// 用unordered_map统计每个元素出现的次数
unordered_mapm;
for(auto e : A)
m[e]++;
// 找出出现次数为N的元素
for(auto& e : m)
{if(e.second == N)
return e.first;
}
}
}; 两个数组的交集I
class Solution
{public:
vectorintersection(vector& nums1, vector& nums2)
{// 用unordered_set对nums1中的元素去重
unordered_sets1;
for (auto e : nums1)
s1.insert(e);
// 用unordered_set对nums2中的元素去重
unordered_sets2;
for (auto e : nums2)
s2.insert(e);
// 遍历s1，如果s1中某个元素在s2中出现过，即为交集
vectorvRet;
for (auto e : s1)
{ if (s2.find(e) != s2.end())
vRet.push_back(e);
}
return vRet;
}
}; 两个数组的交集II
class Solution {public:
vectorintersect(vector& nums1, vector& nums2) {unordered_mapcount{};
vectorresult;
for(auto num1 : nums1)
{count[num1]++;
}
for(auto num2 : nums2)
{if(count[num2] >0)
{result.push_back(num2);
count[num2]--;
}
}
return result;
}
}; 存在重复元素
class Solution {public:
bool containsDuplicate(vector& nums) {unordered_mapcount;
for(auto num : nums)
{++count[num];
if(count[num] >= 2)
return true;
}
return false;
}
}; 两句话中不常见的单词
class Solution {public:
vectoruncommonFromSentences(string s1, string s2) {unordered_mapcount;
vectorret;
auto insert = [&](const string& s)
{stringstream ss(s);
string word;
while(ss >>word)
{++count[move(word)];
}
};
insert(s1);
insert(s2);
for(const auto& [word,occ] : count)
{if(occ == 1)
ret.push_back(word);
}
return ret;
}
}; 因为这两个容器底层用到了哈希桶的数据结构，参考数据结构之哈希（C++实现）。
5.1 哈希表的改造模板参数列表的改造
// K:关键码类型 // T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是 // unordered_set,T 为 K // KeyOfValue: 因为T的类型不同，通过value取key的方式就不同，详细见 // unordered_map/set的实现 // Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模 templateclass HashTable; 增加迭代器操作
// 前置声明 templateclass HashTable; template struct __HashIterator {typedef HashNode Node; typedef HashTable 增加通过key获取value的操作
templateclass HashTable {typedef HashNode Node; // 迭代器 template friend struct __HashIterator; public: typedef __HashIterator
namespace ming
{template>class unordered_map
{struct MapKeyOfT
{ const K& operator()(const std::pair& kv)
{ return kv.first;
}
};
public:
typedef typename HashBucket::HashTable, Hash, MapKeyOfT>::iterator iterator;
iterator begin()
{ return _ht.begin();
}
iterator end()
{ return _ht.end();
}
pairInsert(const pair& kv)
{ return _ht.Insert(kv);
}
V& operator[](const K& key)
{ pairret = _ht.Insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
HashBucket::HashTable, Hash, MapKeyOfT>_ht;
};
} #pragma once
#include "HashTable.h"
namespace ming
{template>class unordered_set
{struct SetKeyOfT
{const K& operator()(const K& key)
{return key;
}
};
public:
typedef typename HashBucket::HashTable::iterator iterator;
iterator begin()
{return _ht.begin();
}
iterator end()
{return _ht.end();
}
pairinsert(const K& key)
{return _ht.Insert(key);
}
private:
HashBucket::HashTable_ht;
};
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：C++容器篇，unordered-创新互联
网站网址：http://cqcxhl.cn/article/csigji.html