unordered_map 1e7元素空间大小
时间: 2023-08-28 19:20:36 浏览: 45
unordered_map是一种基于哈希实现的容器,可以存储键值对。它的大小是指容器中存储的元素个数。在使用unordered_map之前可以通过调用size()函数来获取当前容器中的元素个数。而对于unordered_map的空间大小,它并不是固定的,而是根据实际存储的元素个数动态分配的。因此,对于1e7个元素的情况,可以通过调用size()函数来获取元素个数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [unordered_map、unordered_set代替手写哈希](https://blog.csdn.net/HangHug_L/article/details/114135343)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
相关问题
上面代码不使用#include <queue> #include <unordered_map>,来实现
那么可以使用手动实现队列和哈希表来代替STL中的queue和unordered_map。
队列可以使用数组或链表来实现,这里以数组为例:
```cpp
const int MAXN = 1e5; // 队列最大容量
int q[MAXN], front = 0, rear = -1;
bool empty() {
return front > rear;
}
void push(int x) {
q[++rear] = x;
}
void pop() {
++front;
}
int front() {
return q[front];
}
```
哈希表可以使用数组或链表来实现,这里以数组为例:
```cpp
const int MAXN = 1e6; // 哈希表最大容量
int h[MAXN], idx = 0;
void insert(int x) {
int pos = (x % MAXN + MAXN) % MAXN; // 计算哈希值
for (int i = h[pos]; i != -1; i = e[i].next) { // 遍历链表
if (e[i].key == x) return; // 已经存在
}
e[idx].key = x; // 插入新节点
e[idx].next = h[pos];
h[pos] = idx++;
}
bool find(int x) {
int pos = (x % MAXN + MAXN) % MAXN; // 计算哈希值
for (int i = h[pos]; i != -1; i = e[i].next) { // 遍历链表
if (e[i].key == x) return true; // 找到了
}
return false; // 没有找到
}
```
这里需要注意的是,要实现一个完整的哈希表,还需要定义一个节点结构体`struct Node { int key, next; } e[MAXN]`来存储节点信息,其中`key`表示键值,`next`表示指向下一个节点的指针。同时,初始化哈希表时需要将所有的`h[i]`初始化为-1,表示链表为空。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9 + 7; int main(){ int n,x; LL ans = 1; unordered_map<int,int> hash; cin >> n; while(n--){ cin >> x; for(int i = 2;i <= x/i; ++i){ while(x % i == 0){ x /= i; hash[i] ++; } } if(x > 1) hash[x] ++; } for(auto i : hash) ans = ans*(i.second + 1) % mod; cout << ans; return 0; } 这一串代码每一步都是什么意思?
这段代码是一个计算给定一组整数的因子个数之积的程序。下面是每一步的解释:
1. `#include <bits/stdc++.h>`:这是一个预处理指令,它包含了所有常用的 C++ 标准库,以便在代码中使用。
2. `using namespace std;`:这是一个命名空间声明,它允许在代码中直接使用标准库中的函数和对象,而无需使用前缀 `std::`。
3. `typedef long long LL;`:这是一个类型定义,将 `long long` 类型重命名为 `LL`,用于表示长整型。
4. `const int mod = 1e9 + 7;`:这是一个常量定义,将 `1e9 + 7` 赋值给变量 `mod`,用于取模运算。
5. `int main()`:这是程序的主函数,程序从这里开始执行。
6. `int n, x;`:定义了两个整型变量 `n` 和 `x`,用于存储输入的值。
7. `LL ans = 1;`:定义一个长整型变量 `ans`,并初始化为 1,用于存储最终的计算结果。
8. `unordered_map<int, int> hash;`:定义了一个无序哈希表 `hash`,用于记录每个数的因子及其出现次数。
9. `cin >> n;`:从标准输入读取一个整数,存储到变量 `n` 中。
10. `while (n--)`:当 `n` 不为 0 时,执行循环体。循环的目的是读取 n 个整数并计算其因子。
11. `cin >> x;`:从标准输入读取一个整数,存储到变量 `x` 中。
12. `for (int i = 2; i <= x / i; ++i)`:循环遍历从 2 到 x 的平方根之间的所有整数 i。循环的目的是找出 x 的所有因子。
13. `while (x % i == 0)`:当 x 能被 i 整除时,执行循环体。循环的目的是将 x 分解为质因数,并记录每个质因数的出现次数。
14. `x /= i;`:将 x 除以 i,更新 x 的值。
15. `hash[i]++;`:将质因数 i 的出现次数加一。
16. `if (x > 1) hash[x]++;`:如果 x 大于 1,则说明 x 是一个大于平方根的质因数,将其出现次数加一。
17. `for (auto i : hash) ans = ans * (i.second + 1) % mod;`:遍历哈希表 hash 中的所有元素,计算每个质因数的因子个数之积,并对 mod 取模。
18. `cout << ans;`:将计算结果输出到标准输出。
19. `return 0;`:返回 0,表示程序正常结束。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)