一、set
1.1 set 容器介绍
set 属于关联容器 ( Associative Container )，其按照某种排序方式排序且存储的元素是唯一的
默认情况下 set 按照 key 进行升序排序，可以借由仿函数来变更其排序的方式
set 的底层实现是二叉搜索树，因此 set 不提供更改数据的接口，避免更新破坏二叉搜索树的特性
// Example int main() { set<int> s; // 空set set<int> s2 = {6, 4, 2, 8, 3, 1}; // 以一至多个数据进行初始化 for (auto &e : s2) { cout << e << " "; } cout << endl; return 0; }
1.2 set 接口介绍
1.2.1 插入
插入的接口有：
insert()和emplace()
insert : 插入已经构造好的对象 ( 可以简单理解为不会在插入的时候原地构造对象 )
( 对隐式类型来说，是先建构出一份对象的临时拷贝再插入)
emplace : 直接在容器内部原地构建对象
int main() { set<pair<char, int>> ms; ms.emplace('a', 24); // emplace 直接调用 pair 的构造函数然后插入 set // ms.insert('b', 25); // 报错，因为 insert 只能接收一个参数 ms.insert(make_pair('b', 25)); // 先构建出对象，再插入 set for (auto it = ms.begin(); it != ms.end(); ++it) cout << " " << (*it).first << " " << (*it).second << endl; // Output : a 24 b 25 return 0; }
1.2.2 访问
set 的访问可以由迭代器来实现
int main() { set<int> s1 = {3, 5, 4, 2, 7}; auto it = s1.begin(); while (it != s1.end()) { cout << *it << " "; it++; } return 0; }
1.2.3 查找
int main() { set<int> s = {1, 4, 2, 3, 5}; auto it = s.find(3); // 查找 3 /* 如果找到，则返回指向该元素的迭代器。如果未找到，则返回std::set::end() */ auto it2 = s.count(4); // count 和 find 的差别在于， count 返回的是要查找的数据数据的个数 if (it != s.end()) cout << *it; else cout << "Element not Found!"; return 0; }
1.2.4 删除
int main() { set<int> s = {1, 4, 2, 3, 5}; s.erase(5); s.erase(s.begin()); // 用迭代器删除 /* 返回从 set 容器中删除的元素数量。对于 set ，该值始终为 1 或 0 */ for (auto x: s) cout << x << " "; return 0; }
1.2.5 其他接口
- lower_bound() : 找到 set 中等于或大于给定值的第一个元素
- upper_bound() : 找到 set 中第一个大于给定值的元素
int main() { set<int> s = {5, 4, 3, 8, 6, 0, 7, 1}; auto lower = s.lower_bound(3); auto upper = s.upper_bound(7); s.erase(lower, upper); // s.erase(3,8); 左闭右开 所以是删除 3~7 for (auto &e : s) { cout << e << " "; // 0 1 8 } cout << endl; return 0; }
1.2.6 时间复杂度
操作 时间复杂度 插入 O(log n) 删除 O(log n) 查找最大的数据 O(1) 查找最小的数据 O(1) 查找某个数据 O(log n) 遍历 set O(n)
二、map
2.1 map 容器介绍
map 也属于关联容器，其与 set 的区别在于 map 是以
<key,value>的形式存储默认排序是根据
key进行升序且key的值不允许重复map 的底层是使用红黑树实现，所以有修改的接口
2.2 map 接口介绍
2.2.1 插入
map 的插入方式有三种
insert : 只插入一次，如果后面重复插入相同的 key 不同的 value 也不会改变 value 的数据
operator []
插入又分为 key 是否以存在于 map 中，若存在则改变 value ( 假如值与原本的不一样 )；
反之则插入
<key,value>到 map 中emplace：主要还是和 insert 形成对比，直接调用构造函数构造对象，而不是先构造才能插入
// insert int main() { map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}}; m.insert({"f", 6}); for (auto &e : m) { cout << e.first << " " << e.second << endl; } cout << endl; m.insert({"a", 10}); // 插入重复的数据 for (auto &e : m) { cout << e.first << " " << e.second << endl; } cout << endl; return 0; } /* output: a 1 b 2 c 3 d 4 e 5 f 6 a 1 b 2 c 3 d 4 e 5 f 6 */// operator [] int main() { map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}}; m["f"] = 6; for (auto &e : m) { cout << e.first << " " << e.second << endl; } cout << endl; m["a"] = 10; for (auto &e : m) { cout << e.first << " " << e.second << endl; } cout << endl; return 0; } /* a 1 b 2 c 3 d 4 e 5 f 6 a 10 b 2 c 3 d 4 e 5 f 6 */
2.2.2 访问
// 访问可以利用迭代器、[]、或at int main() { map<int, string> m = {{1, "Geeks"}, {2, "For"}, {3, "Geeks"}}; cout << m[1] << endl; cout << m.at(2); return 0; } /* output: Geeks For */
2.2.3 修改
// 修改可以使用[] 或 at int main() { map<int, string> m = {{1, "Geeks"}, {2, "For"}, {3, "Geeks"}}; // 修改数据 m[0] = "Tweaks"; m.at(1) = "By"; cout << m[0] << endl; cout << m.at(1); return 0; } /* output: Tweaks By */
2.2.4 查找
int main() { map<int, string> m = {{1, "Geeks"}, {2, "For"}, {3, "Geeks"}}; // 查找key为2的数据 auto it = m.find(2); /* find : 如果有找到返回这个数据的迭代器；反之返回 end() */ if (it != m.end()) cout << it->first << " " << it->second; else cout << "Key not Found!"; return 0; }
2.2.5 删除
int main() { map<int, string> m = {{1, "Geeks"}, {2, "For"}, {3, "Geeks"}}; // 删除 m.erase(2); m.erase(m.begin()); // 返回从 map 容器中删除的元素数量。对于 map ，该值始终为 1 或 0 for(auto i : m) // 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据 cout << i.first << " " << i.second // 3 Geeks << endl; return 0; }
2.3.6 时间复杂度
操作 时间复杂度 插入元素 O（log n） 按 key 删除元素 O（log n） 按 key 访问元素 O（log n） 按 key 查找元素 O（log n） 按 key 更新元素 O（log n） 遍历 O (n)
后续会在补充 关于红黑树的知识点