Sets, Maps
Sets(集合)
在 library 中有两种集合:
- set:使用一种名为二叉树的结构实现.
- 速度相当快;元素以排序顺序存储
- 值必须有一个 "<" 操作
- hashset:使用一种称为哈希表的特殊数组实现。
- 非常快速；元素以不可预测的顺序存储。
- 值必须有一个 hashCode 函数（大多数标准类型提供）。
这两种的选择取决你是否按照排序顺序存放元素
**#include "set.h"**
**#include "hashset.h"**
| Menber | Set | Hashset | description(描述) |
|---|---|---|---|
| s.add(value) | O(log N) | O(1) | 添加元素到集合中 |
| s.clear() | O(N) | O(N) | 清空集合 |
| s.contains(value) | O(log N) | O(1) | 判断元素是否存在于集合中 |
| s.isEmpty() | O(1) | O(1) | 判断集合是否为空 |
| s.isSubsetOf(set) | O(N log N) | O(N) | 判断集合是否是另一个集合的子集 |
| s.remove(value) | O(log N) | O(1) | 从集合中删除元素 |
| s.size() | O(1) | O(1) | 集合中元素的数量 |
| s.toStirng() | O(N) | O(N) | 集合中元素的字符串表示 |
运算符
- s1 == s2: 判断两个集合是否相等
- s1 != s2: 判断两个集合是否不相等
- s1 + s2: 合并两个集合
- s1 += s2: 合并两个集合并更新第一个集合
- s1 - s2: 集合 s1 中元素不在集合 s2 中的元素
- s1 -= s2: 集合 s1 中元素不在集合 s2 中的元素并更新第一个集合
- s1 * s2: 集合 s1 和集合 s2 的交集
- s1 *= s2: 集合 s1 和集合 s2 的交集并更新第一个集合
注意:无法使用 for 循环遍历集合中的元素，因为集合是无序的。
Lexicon(词典)
这就是以字符串构成的 Sets(集合)的例子。
Maps(映射)
Maps(映射)是键值对的集合。
组成部分:
- key: 映射中的键
- value: 映射中的值
映射是一种存储对集合的数据结构
**#include "map.h"** 使用一种称为二叉搜索树的链接结构实现。
所有操作速度相当快；键以排序顺序存储。
两种映射实现完全相同的操作。
值必须有一个 "<" 操作。
**#include "hashmap.h"** 使用一种称为哈希表的特殊数组实现。
速度非常快；键以不可预测的顺序存储。
值必须有一个 hashCode 函数（大多数标准类型提供）。
运算符
- m.put(key, value): 添加键值对到映射中
c++
m.put("bobo", "114-514"); //or
m["bobo"] = "114-514";- m.get(key): 获取键对应的值
c++
string value = m.get("bobo"); //"114-514" or
string value = m["bobo"];- m.remove(key): 从映射中删除键值对
c++
m.remove("bobo");membership
| 成员 | Map | HashMap | 描述 |
|---|---|---|---|
| m.clear() | O(N) | O(N) | 移除所有键/值对 |
| m.containsKey(key) | O(log N) | O(1) | 如果映射中存在给定键的对，则返回 true |
| m[key] 或 m.get(key) | O(log N) | O(1) | 返回映射到给定键的值；如果未找到，则以默认值添加 |
| m.isEmpty() | O(1) | O(1) | 如果映射不包含任何对，则为 true |
| m.keys() | O(N) | O(N) | 返回映射中所有键的 Vector 复制 |
| m[key] = value; 或 m.put(key, value); | O(log N) | O(1) | 添加键/值对；如果键已存在，替换其值 |
| m.remove(key) | O(log N) | O(1) | 移除给定键的任何对 |
| m.size() | O(1) | O(1) | 返回映射中的对数 |
| m.toString() | O(N) | O(N) | 示例："{a:90, d:60, c:70}" |
| m.values() | O(N) | O(N) | 返回映射中所有值的 Vector 复制 |
| ostr << m | O(N) | O(N) | 将映射打印到流中 |
Lotto ticket example 嵌套集合
集合之间可以相互嵌套
c++
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
int main()
{
// Set of integers
set<int> s1 = {1, 2, 3, 4, 5};
set<int> s2 = {3, 4, 5, 6, 7};
set<int> s3 = {5, 6, 7, 8, 9};
// Map of sets
map<string, set<int>> m;
m["s1"] = s1;
m["s2"] = s2;
m["s3"] = s3;
// Accessing values using keys
cout << m["s1"].size() << endl; // Output: 5
cout << m["s2"].size() << endl; // Output: 5
cout << m["s3"].size() << endl; // Output: 5
// Accessing values using iterators
for(auto it = m.begin(); it != m.end(); it++) {
cout << it->first << " : ";
for(auto jt = it->second.begin(); jt != it->second.end(); jt++) {
cout << *jt << " ";
}
cout << endl;
}
return 0;
}big O notation(大 O 记法)
我们可以从不同方面来衡量一个算法的效率。
- Efficiency(效率):衡量代码使用计算资源的程度。
- 可能相对速度（运行时间）、内存（空间）等。
- 最常指的是运行时间。
- 单个语句的运行时间 = 1。
- 一个函数调用的运行时间 = （函数体内语句运行时间的总和）。
- N 次迭代的循环运行时间 = (N * (循环体的运行时间))。
O(1)<O(log N)<O(N)<O(N log N)<O(N^2)<O(2^N)<O(N!)<O(N^N)<O(infinity)