map类
时间: 2023-06-30 13:11:53 浏览: 43
好的,我明白了。那么我先帮你创建一个有序 int 数组和一个 map<int, int> 实例,并在其中插入数据。
以下是代码示例:
```cpp
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <chrono>
using namespace std;
int main() {
const int N = 20000;
int arr[N];
map<int, int> mp;
unordered_map<int, int> ump;
// 初始化数组和 map
for (int i = 0; i < N; i++) {
arr[i] = i;
mp.insert({i, i});
ump.insert({i, i});
}
// 需要查找的数据
vector<int> targets = {500, 1500, 2500, 3500, 4500, 5500, 6500, 7500, 8500, 9500, 10500,
11500, 12500, 13500, 14500, 15500, 16500, 17500, 18500, 19500};
// 在数组中顺序查找
auto start = chrono::steady_clock::now();
for (auto target : targets) {
for (int i = 0; i < N; i++) {
if (arr[i] == target) {
break;
}
}
}
auto end = chrono::steady_clock::now();
auto diff = end - start;
cout << "在数组中顺序查找的时间为: " << chrono::duration<double, milli>(diff).count() << " ms" << endl;
// 在数组中二分查找
start = chrono::steady_clock::now();
for (auto target : targets) {
int index = lower_bound(arr, arr + N, target) - arr;
}
end = chrono::steady_clock::now();
diff = end - start;
cout << "在数组中二分查找的时间为: " << chrono::duration<double, milli>(diff).count() << " ms" << endl;
// 在 map 中查找
start = chrono::steady_clock::now();
for (auto target : targets) {
auto iter = mp.find(target);
}
end = chrono::steady_clock::now();
diff = end - start;
cout << "在 map 中查找的时间为: " << chrono::duration<double, milli>(diff).count() << " ms" << endl;
// 在 unordered_map 中查找
start = chrono::steady_clock::now();
for (auto target : targets) {
auto iter = ump.find(target);
}
end = chrono::steady_clock::now();
diff = end - start;
cout << "在 unordered_map 中查找的时间为: " << chrono::duration<double, milli>(diff).count() << " ms" << endl;
return 0;
}
```
代码中,我们先定义了一个数组和一个 map,然后在其中插入数据。接着,我们定义了一组需要查找的数据,包括数组中的元素和 map 中的键值。然后,我们分别使用顺序查找、二分查找、map 查找和 unordered_map 查找算法,来测试它们的时间开销。
你可以运行这段代码,观察输出结果并进行比较。