1. 关联式容器
在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、
forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面
存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的
键值对，在数据检索时比序列式容器效率更高。
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，value表示与key对应的信息
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} };
树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使
用平衡搜索树(即红黑树)作为其底层结果.
3.set的介绍
1.set在底层是用二叉搜索树(红黑树)实现的。
2.与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
3.set中插入元素时，只需要插入value即可，不需要构造键值对。
4.set中的元素不可以重复(因此可以使用set进行去重)。
5使用set的迭代器遍历set中的元素，可以得到有序序列
6.set中查找某个元素，时间复杂度为：l o g 2 n log_2 nlog2n
4.set的常用函数使用
1.insert函数以及迭代器的使用
#include<iostream> #include<set> #include<vector> #include<map> using namespace std; void test_set1() { set<int>st; st.insert(11); st.insert(3); st.insert(7); st.insert(5); st.insert(2); st.insert(7); st.insert(4); set<int>::iterator it = st.begin(); while (it != st.end()) { cout << *it << " "; it++; } cout << endl; } ```c int main() { test_set1(); }
set可以做到排序+去重
2.set的常见构造函数以及范围for
void test_set2() { vector<int>v = { 8,7,4,3,9,11 }; set<int>s2(v.begin(), v.end()); for (auto e : s2) { cout << e << " "; } cout << endl; set<int>s3 = { 8,6,9,3,2,7,5,1,1}; set<int>::iterator it = s3.begin(); while (it != s3.end()) { cout << *it << " "; it++; } cout << endl; } int main() { test_set2(); }
支持迭代器区间构造以及集合直接构造
3.erase函数以及find函数
void test_set3() { set<int>s3 = { 8,6,9,3,2,7,5,1,1 }; set<int>::iterator it = s3.begin(); while (it != s3.end()) { cout << *it << " "; it++; } cout << endl; s3.erase(8); for (auto e : s3) { cout << e << " "; } cout << endl; auto pos = s3.find(20); if (pos != s3.end()) { cout << *pos << endl; s3.erase(pos); } else { cout << "找不到"<<endl; } for (auto e : s3) { cout << e << " "; } cout << endl; } int main() { test_set3(); }
4.lower_bound函数和upper_bound函数
lower_bound函数返回set中>=传参值的第一个位置的迭代器
upper_bound函数返回set中<=传参值的第一个位置迭代器
这样我们可以使用erase删除一段区间
void test_set4() { set<int>st; for (int i = 0; i < 10; i++) {st.insert(i * 10); } for (auto e : st) { cout << e << " "; } cout << endl; auto itlow = st.lower_bound(25); auto itup = st.upper_bound(65); st.erase(itlow, itup); for (auto e : st) { cout << e << " "; } cout << endl; } int main() { test_set4(); }
5.不去重的multiset
void test_set5() { multiset<int>st; st.insert(1); st.insert(8); st.insert(4); st.insert(2); st.insert(1); st.insert(1); for (auto e : st) { cout << e << " "; } cout << endl; } int main() { test_set5(); }
实现排序不去重
5.map的介绍
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair
typedef pair<const key, T> value_type;- map中的的元素是键值对
- map中的key是唯一的，并且不能修改
- 默认按照小于的方式对key进行比较
- map中的元素如果用迭代器去遍历，可以得到一个有序的序列
- map的底层为平衡搜索树(红黑树)，查找效率比较高O ( l o g 2 N ) O(log_2 N)O(log2N)
- 支持[]操作符，operator[]中实际进行插入查找。
6.map的常用函数使用
1.insert函数
void test_map1() { map<string, string>dic; pair<string, string>kv("sort", "排序"); dic.insert(kv); dic.insert(pair<string, string>("left", "左边"));//插入匿名对象 dic.insert(make_pair("right", "右边")); dic.insert(make_pair("right", "左边")); dic.insert({ "string","字符串" });//隐式类型转换 }
遍历
迭代器遍历：
void test_map1() { map<string, string>dic; pair<string, string>kv("sort", "排序"); dic.insert(kv); dic.insert(pair<string, string>("left", "左边")); dic.insert(make_pair("right", "右边")); dic.insert(make_pair("right", "左边")); dic.insert({ "string","字符串" });//隐式类型转换 map<string, string>::iterator it = dic.begin();//这里类型太长我们可以用auto auto it = dic.begin(); //auto it = dic.begin(); while (it != dic.end()) { cout << (*it).first << ":" << (*it).second << endl; it++; } cout << endl; }
it是迭代器，**it是迭代器指向的pair，pair第一个位置是他的键值。pair第二个位置是他的值value。
借鉴list迭代器那里
同样我们可以这样写
void test_map1() { map<string, string>dic; pair<string, string>kv("sort", "排序"); dic.insert(kv); dic.insert(pair<string, string>("left", "左边")); dic.insert(make_pair("right", "右边")); dic.insert(make_pair("right", "左边")); dic.insert({ "string","字符串" });//隐式类型转换 map<string, string>::iterator it = dic.begin(); while (it != dic.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; it++; } cout << endl; }
it.operator->()取到的是指向数对的地址，it.operator->()->first就是对应pair上的键值
it.operator->()->second 就是对应的value
范围for
void test_map1() { map<string, string>dic; pair<string, string>kv("sort", "排序"); dic.insert(kv); dic.insert(pair<string, string>("left", "左边")); dic.insert(make_pair("right", "右边")); dic.insert(make_pair("right", "左边")); dic.insert({ "string","字符串" });//隐式类型转换 map<string, string>::iterator it = dic.begin(); for (auto& kv : dic)//深拷贝 { cout << kv.first << ":" << kv.second << endl; } cout << endl;
这里用引用是因为string拷贝会去调string的拷贝构造，深拷贝，开辟空间太麻烦，直接传引用，kv是dic中一段pair的别名
auto[a,b] (c++17支持)
void test_map1() { map<string, string>dic; pair<string, string>kv("sort", "排序"); dic.insert(kv); dic.insert(pair<string, string>("left", "左边")); dic.insert(make_pair("right", "右边")); dic.insert(make_pair("right", "左边")); dic.insert({ "string","字符串" });//隐式类型转换 map<string, string>::iterator it = dic.begin(); for (auto&[x,y] : dic)//深拷贝 { cout << x << ":" << y << endl; } cout << endl;
2. V&operator[const K&key]
5.使用map统计次数
void test_map4() { string arr[] = { "苹果","西瓜","苹果" ,"西瓜", "西瓜", "西瓜", "西瓜", "香蕉","香蕉" }; map<string, int>countmap; for (auto& e : arr) { auto it = countmap.find(e); if (it != countmap.end()) { it->second++; } else { countmap.insert({e,1}); } } for (auto& kv : countmap) { cout << kv.first << ":" << kv.second << endl; } } int main() { test_map5(); }
统计水果出现次数，水果名称为键值，水果出现次数为value,遍历arr,如果countmap对应键值没有出现该水果，就插入，是第一次，所以value=1;
如果出现过对应键值，就value++,水果数目++；
这里的排序是按找key比的，因为key是string，按照ascll比较，小的在前，应该底层调用的是strcmp(),如果要按照出现次数排序，我们让键值为出现次数，value为水果名称，但是这里键值为出现次数的话，key就会出现重复，我们之前说了key不能重复，这样会导致相同次数的有些水果不能被插入，这里我们引入multimap，他的key可以重复，但是multimap就没有V&operator[const K&key]，因为key是多个，找不到对应的value了
3.multimap
void test_multimap() { string arr[] = { "苹果","西瓜","苹果" ,"西瓜", "西瓜", "西瓜", "西瓜", "香蕉","香蕉" }; map<string, int>countmap; for (auto& e : arr) { countmap[e]++; } multimap<int, string>sortmap; for (auto& e : countmap) { sortmap.insert({ e.second,e.first }); } for (auto& kv : sortmap) { cout << kv.first << ":" << kv.second << endl; } } int main() { test_multimap(); }
将countmap里面的键值和value位置交换一下，让水果出现次数为key,multimap支持key重复，所以都可以插入
