|
|
本帖最后由 yuanbao 于 2023-3-28 22:01 编辑
map 和 unordered_map 都是 C++ STL 中的关联容器，用于存储键值对。二者的底层实现不同，导致它们的特性也有所不同。
map 是基于红黑树的实现，因此它的元素是按照键值的大小有序排列的。map 的查找、删除、插入操作都是 $\log n$ 的时间复杂度，其中 $n$ 是元素数量。由于 map 的元素是有序的，因此我们可以使用 lower_bound、upper_bound 等 STL 算法。
unordered_map 是基于哈希表的实现，它的元素是无序的。哈希表的查询、删除、插入操作的时间复杂度都是常数级别的，因此 unordered_map 在元素数量较多时更加高效。但是，由于哈希表需要进行哈希函数的计算，因此 unordered_map 的空间使用上会比 map 大一些。
使用时，如果需要对元素进行排序，或者需要使用 lower_bound、upper_bound 等 STL 算法，就可以使用 map。如果需要快速定位元素并且不需要排序，就可以使用 unordered_map。
需要注意的是，由于哈希表的原理，它的元素在内存中是离散的，因此在访问内存时可能会出现较多的缓存不命中，从而影响程序的性能。另外，由于哈希表的元素数量通常会超过预期，因此需要根据实际情况调整哈希表的初始大小和负载因子，以避免过多的哈希冲突和重新哈希操作。
下面是使用 unordered_map 计算每个树种出现次数的代码：- #include <iostream>
- #include <unordered_map>
- #include <string>
- using namespace std;
- int main() {
- unordered_map<string, int> mp;
- string st;
- while (getline(cin, st)) {
- mp[st]++;
- }
- for (auto it = mp.begin(); it != mp.end(); it++) {
- cout << it -> first << " " << it -> second << endl;
- }
- return 0;
- }
终于理解了map容器对key进行排序的了。- #include <iostream>
- #include <map>
- #include <iomanip>
- #include <string>
- using namespace std;
- map<string, int> mp;
- string st;
- int cnt;
- double ans;
- int main(){
- while (getline(cin, st)){
- mp[st]++;
- cnt++;
- }
- for (auto it = mp.begin(); it != mp.end(); it++){
- ans = (it -> second) * 1.0 / cnt * 100;
- cout << it -> first << ' ' << fixed << setprecision(4) << ans << '\n';
- }
- return 0;
- }
|
|
发表于 2023-3-28 09:50:20
置顶卡
发表于 2023-3-28 18:55:55