05英雄C++STL编程（下）

7、set 7.1 基础概念

容器特点：

#include <iostream> #include <set> using namespace std; int main() { set<int> s; multiset<int> ms; return 0; } 7.2 对象创建 #include<iostream> #include<set> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { // 1.默认构造函数 set<int> s1; cout << "s1: "; printSet(s1);//空 // 2. 初始化列表 set<int> s2_1 = { 9,8,7,6,5 }; cout << "s2_1: "; printSet(s2_1);//5 6 7 8 9 set<int> s2_2({ 9,8,7,7,6,5 }); // set不支持重复元素、multiset支持重复元素 cout << "s2_2: "; printSet(s2_2);//5 6 7 8 9 // 3. 迭代器的方式 set<int> s3(s2_1.begin(), s2_1.end()); cout << "s3: "; printSet(s3);//5 6 7 8 9 // 4. 拷贝构造 set<int> s4(s2_2); cout << "s4: "; printSet(s4);//5 6 7 8 9 return 0; } 7.3 赋值操作 #include <iostream> #include <set> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s = { 9,8,5,2,1,1 }; cout << "s: "; printSet(s);// 1 2 5 8 9 // 1. = set 对象 set<int> s1; s1 = s;//运算符重载 cout << "s1: "; printSet(s1);// 1 2 5 8 9 // 2. = 初始化列表 set<int> s2; s1 = (s2 = { 3, 4, 5 }); cout << "s2: "; printSet(s2);//3 4 5 cout << "s1: "; printSet(s1);//3 4 5 return 0; } 7.4 大小操作 #include<iostream> #include<set> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s1; cout << "s1.empty() = " << s1.empty() << endl;//1 cout << "s1.size() = " << s1.size() << endl;//0 set<int> s2 = { 1,1,1,1,6,7,8,9 }; cout << "s2.empty() = " << s2.empty() << endl;//0 cout << "s2.size() = " << s2.size() << endl;//5 return 0; } 7.5 数据插入 #include<iostream> #include<set> #include <vector> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s; // O(logn) s.insert(3); printSet(s);//3 s.insert(2); printSet(s);//2 3 s.insert(5); printSet(s);//2 3 5 s.insert(4); printSet(s);//2 3 4 5 s.insert(1); printSet(s);//1 2 3 4 5 vector<int> v = { 0, 5, 6, 9 ,8 }; s.insert(v.begin(), v.end()); printSet(s);//0 1 2 3 4 5 6 8 9 return 0; } 7.6 数据查找 #include<iostream> #include<set> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s = { 1,2,3,4,5 }; set<int>::iterator it = s.find(3); if (it != s.end()) { cout << "find: " << (*it) << endl; } it = s.find(10); if (it == s.end()) { cout << "can't find: 10" << endl; } return 0; } 7.7 数据删除 #include<iostream> #include<set> using namespace std; void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s = { 1,2,3,4,5 }; s.erase(3); printSet(s);//1 2 4 5 set<int>::iterator rm = s.find(4); if (rm != s.end()) { s.erase(rm); } printSet(s);//1 2 5 // [ ) s = { 1,2,3,4,5 }; set<int>::iterator rml = s.find(2); set<int>::iterator rmr = s.find(4); s.erase(rml, rmr);//[rml,rmr) printSet(s);//1 4 5 // cout << *rml << endl;//报错 return 0; } 7.8 数据统计 #include<iostream> #include<set> using namespace std; /* count */ void printSet(const set<int>& s) { for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } void printMultiSet(const multiset<int>& s) { for (multiset<int>::const_iterator it = s.begin(); it != s.end(); it++) { cout << *it << " "; } cout << endl; } int main() { set<int> s = { 1,2,3,4,5 }; for (int i = 0; i < 8; i += 2) { cout << "元素：" << i << "的出现次数为 " << s.count(i) << endl; // s.has(i) } multiset<int> ms = { 1,1,1,1,1,1,4,4,4,4,4,2,2,2,2,2,2,2,6,6,6,6,6,8,8,8,5,5,5,5,5 }; for (int i = 0; i < 8; i += 2) { cout << "元素：" << i << "的出现次数为 " << ms.count(i) << endl; } printMultiSet(ms);//1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 8 8 8 return 0; } 7.9 排序规则 #include <iostream> #include <set> using namespace std; class CGaGa { public: CGaGa() { _name = ""; _priority = -1; } CGaGa(string name, int pri) : _name(name), _priority(pri) {} //bool operator<(const CGaGa& cgg) const { //外层的const保证 _name和_priority不被修改 // return _priority < cgg._priority; //} void print() const { cout << "(" << _priority << ")" << _name << endl; } private: string _name; int _priority;//优先级 }; int main() { set< CGaGa > s; s.insert(CGaGa("C++算法零基础", 5)); s.insert(CGaGa("C++面向对象", 2)); s.insert(CGaGa("C++零基础语法", 1)); s.insert(CGaGa("C++数据结构", 3)); s.insert(CGaGa("C++STL", 4)); s.insert(CGaGa("C++项目实战(贪食蛇、扫雷、3D赛车)", 6)); for (set< CGaGa >::iterator it = s.begin(); it != s.end(); it++) { (*it).print(); } return 0; }

不加注释掉的代码，会报错：

   二进制“<”:“const _Ty”不定义该运算符或到预定义运算符可接收的类型的转换。

8、map 8.1 基础概念

 

Map 是 C++ 中非常重要的关联容器之一。它以键值对的形式存储数据，其中每个键都是唯一的，这意味着不能有重复的键。如果尝试插入一个已存在的键，将会覆盖该键对应的值。

Map 的内部结构是红黑树，这使得它具有很多优点。首先，数据是有序的，这有助于高效地进行查找、插入和删除操作。查找、插入、删除的平均和最坏时间复杂度都是 O (log n)，其中 n 是 map 中元素的个数。

在 C++ 中，pair类是一种模板类型，定义在<utility>头文件中。它将两个不同类型的值组合成一个单一的对象。对于map容器来说，map中的每个元素都是一个pair类型。map底层的红黑树节点中的数据，使用pair<Key,T>存储键值对数据。

 

#include <iostream> #include <map> #include <set> using namespace std; int main() { pair<int, int> p1; p1.first = 13; p1.second = 14; cout << p1.first << p1.second << endl; pair<int, string> p2(2, "333"); cout << p2.first << p2.second << endl; pair<char, int> p3 = make_pair(52, 0); // '0' -> 48, '1' -> 49 ... '4' -> 52 cout << p3.first << p3.second << endl; map<int, int> m; set<int> s; return 0; } 8.2 对象创建 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { // 1. 默认构造函数 map<int, int> m1; cout << "m1: " << endl; printMap(m1);//空 // 2. 初始化列表 map<int, int> m2_1 = { pair<int, int>(1, 10), pair<int, int>(4, 24), pair<int, int>(3, 43), pair<int, int>(2, 15) }; cout << "m2_1: " << endl;//1 2 3 4 printMap(m2_1); map<int, int> m2_2({ pair<int, int>(1, 18), pair<int, int>(4, 23), pair<int, int>(3, 41), pair<int, int>(2, 11) }); cout << "m2_2: " << endl; printMap(m2_2); // 3. 迭代器 map<int, int> m3(m2_1.begin(), m2_1.end()); cout << "m3: " << endl; printMap(m3); // 4. 拷贝构造 map<int, int> m4(m2_2); cout << "m4: " << endl; printMap(m4); return 0; } 8.3 赋值操作 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m = { pair<int, int>(1, 10), pair<int, int>(4, 24), pair<int, int>(3, 43), pair<int, int>(2, 15), }; cout << "m: " << endl; printMap(m); // 1. = 对象 map<int, int> m1; m1 = m; cout << "m1: " << endl; printMap(m1); // 2. = 初始化列表 map<int, int> m2; m2 = { pair<int, int>(1, 8), pair<int, int>(4, 36), pair<int, int>(3, 18), pair<int, int>(2, 22), }; cout << "m2: " << endl; printMap(m2); return 0; } 8.4 大小操作 #include <iostream> #include <map> using namespace std; int main() { map<int, int> m1; cout << "m1.empty() = " << m1.empty() << endl;//1 cout << "m1.size() = " << m1.size() << endl;//0 map<int, int> m2 = { pair<int, int>(1, 10),pair<int, int>(3, 5),pair<int, int>(4, 8) }; cout << "m2.empty() = " << m2.empty() << endl;//0 cout << "m2.size() = " << m2.size() << endl;//3 return 0; } 8.5 数据插入 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m; // 1 m.insert(pair<int, int>(1, 10)); printMap(m); // 2 m.insert(make_pair(3, 20)); printMap(m); // 3 m.insert(map<int, int>::value_type(2, 78)); printMap(m); // 4 m[4] = 6; printMap(m); // 5 pair< map<int, int>::iterator, bool > ret = m.insert(make_pair(3, 21));//key在，插入失败 cout << "insert(3, 21) = " << ret.second << endl; printMap(m); // 6 m[3] = 22; printMap(m);//改变 20 变成 22 // 7 m[0];//键不存在的情况，会插入 printMap(m);//m[0] 变为 0 0 return 0; } 8.6 数据查找 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m = { pair<int, int>(1, 4), pair<int, int>(3, 20), pair<int, int>(2, 80), pair<int, int>(4, 17), }; for (int i = 4; i <= 5; ++i) { map<int, int>::iterator it = m.find(i); if (it != m.end()) { cout << "找到键值对：（" << it->first << "," << it->second << "）" << endl; } else { cout << "未找到键：" << i << endl; } } return 0; } 8.7 数据删除 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m = { pair<int, int>(1, 4), pair<int, int>(3, 30), pair<int, int>(2, 80), pair<int, int>(4, 90), }; printMap(m); m.erase(1);//删除1 printMap(m); m.erase(m.begin());//删除2 printMap(m); m.erase(m.begin(), m.end()); printMap(m); m = { pair<int, int>(1, 4), pair<int, int>(3, 30), pair<int, int>(2, 80), pair<int, int>(4, 90), }; m.clear(); printMap(m); return 0; } 8.8 数据修改 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m; m.insert(make_pair(1, 20)); m.insert(make_pair(2, 330)); m.insert(make_pair(3, 4440)); m[3] = 888; printMap(m); m[2]++; printMap(m); m[1] -= 21; printMap(m); return 0; } 8.9 数据统计 #include <iostream> #include <map> using namespace std; void printMap(const map<int, int>& m) { for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) { // it->first, it->second cout << "key = " << it->first << " " << " value = " << it->second << endl; } cout << "----------------------------" << endl; } int main() { map<int, int> m; m.insert(make_pair(1, 20)); m.insert(make_pair(2, 330)); m.insert(make_pair(3, 4440)); m[3] = 888; printMap(m); m[2]++; printMap(m); m[1] -= 21; printMap(m);//-1 return 0; }