2019-08-13

C++

6 分钟读完 (大约 829 个字) ...次访问

C++11 新用法

基于哈希的 map 和 set

简述

基于哈希的 map 和 set ，它们分别叫做 unordered_map, unordered_set 。数据分布越平均，性能相较 map 和 set 来说提升就更大。但由于它们基于哈希，所以并不像 map 和 set 一样能自动排序；它们都是无序的。

我做了一个测试：随机生成 $10^7$ 个 int 范围内的整数（平均分布），然后将其分别插入 map 和 unordered_map，再完整的做一次查询，查看时间和内存上的消耗。

测试结果

结构	总耗时	插入耗时	查询耗时	内存
map	18,041 MS	10,299 MS	7,742 MS	230.7 MB
unordered_map	7,138 MS	5,426 MS	1,712 MS	212.0 MB

当数据分布平均时，从时间上看，两者的性能差距约为 $7138 / 18041 \approx 40\%$

提示

即使在平均意义下 unordered_map 有着比 map 更高的效率，但是由于两者的实现（前者哈希，后者平衡树）， unordered_map 单次插入的最差复杂度是 $O(N)$， map 单次插入的最差复杂度是 $O(log N)$ 。所以在出题人故意造数据卡 unordered_map 使其内部哈希表发生严重冲突时，unordered_map 就会变得很慢。

测试代码

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

vector<pair<int, int>> data;

int main() {
    freopen("map.txt", "r", stdin);
    data.resize(5000000);
    map<int, int> mp;
    double st, ed;
    st = clock();
    for (int i = 0; i < 5000000; ++i) scanf("%d%d", &data[i].first, &data[i].second);
    ed = clock();
    printf("Read: %dms\n", int(1000.0 * (ed - st) / CLOCKS_PER_SEC));
    st = clock();
    for (int i = 0; i < 5000000; ++i) mp[data[i].first] = data[i].second;
    ed = clock();
    printf("Insert: %dms\n", int(1000.0 * (ed - st) / CLOCKS_PER_SEC));
    st = clock();
    for (int i = 0; i < 5000000; ++i) data[i].second = mp[data[i].first];
    ed = clock();
    printf("Query: %dms\n", int(1000.0 * (ed - st) / CLOCKS_PER_SEC));
    data = vector<pair<int, int>>();
}

语法上的变化

auto 关键字的新含义

在 C++11 中，auto 关键字被赋予了新的含义。其功能是自动类型推导。

auto x = 3; // y的类型自动推导为 int
auto y = make_pair(1, 2); // y的类型自动推导为 pair<int, int>
auto z; // 编译错误, z的类型需要一个初始值才能推导

map<int, int> mp;
// iter的类型推导为map<int, int>::iterator
for (auto iter = mp.begin(); iter != mp.end(); ++iter)
    cout << iter->first << ' ' << iter->second << '\n';

与其相关的是一个新的关键字 decltype，取得某一个值的类型。

1 2	int a = 1, b = 2; decltype(a + b) c; // c为int

增强的 for（基于范围的for循环）

map<int, int> mp;

// C++11 之前遍历
for (map<int, int>::iterator it = mp,begin(); it != mp,end(); ++it)
	cout << it->first << ' ' << it->second << '\n';

// C++11 之后
for (auto val : mp)
	cout << val.first << ' ' << val.second << '\n';

模板嵌套时一个小改善

1 2	priority_queue<pair<int, int> > heap; // C++11之前需加一个空格避免歧义 priority_queue<pair<int, int>> heap; // C++11之后不用

初始化列表

更简单的初始化方式。

vector<pair<int, int>> v{ {1, 2}, {2, 3}, {3, 4} };

// 等价于下面代码
vector<pair<int, int> > v;
v.push_back(make_pair(1, 2));
v.push_back(make_pair(2, 3));
v.push_back(make_pair(3, 4));

lambda 表达式

下面用一个例子讲述一下lambda表达式的大致用法。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<pair<int, int>> v{ {1, 2}, {2, 3}, {3, 4} };
    for (auto& val : v) {
        cout << val.first << ' ' << val.second << '\n';
    }
    sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b) { return a.first > b.first; });
    cout << "After sort:\n";
    for (auto& val : v) {
        cout << val.first << ' ' << val.second << '\n';
    }
    return 0;
}

代码里的 sort，在C++11之前比较常见的等价写法是：

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.first > b.first;
}

int main() {
    // ...
    sort(v.begin(), v.end(), cmp);
    // ...
}

# C++11, STL, 数据结构