C++语法（17）---- 二叉搜索树_哈里沃克的博客-CSDN博客https://blog.csdn.net/m0_63488627/article/details/130174864 目录

1.set的介绍

1.set使用

1.基本结构

2.insert

3.erase

4.find

5.count

2.multiset

1.count

2.find

2.map的介绍

1.map

1.相关函数

2.operator[]的原理

​编辑

2.multimap

1.set的介绍

序列式容器：STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。其中的数据是相互关联的。

1.set使用

1.基本结构

其底层实现其实是平衡搜索二叉树

2.insert

第一个就是插入指定值

第二个是指定迭代器位置插入，不过该函数不要轻易使用，因为一旦插入的逻辑违背搜索二叉树的原则，那么变成了一个错误的结构

第三个是按迭代器位置拷贝

int main()
{set<int> s;s.insert(7);s.insert(4);s.insert(5);s.insert(3);s.insert(6);s.insert(1);s.insert(1);for (auto& e : s){cout << e << " ";}cout << endl;return 0;
}

从结果上看，set的作用就是查重加排序。insert检查到已经与重复的数据就不插入了

3.erase

第一个是删除迭代器

第二个是删除传入的数据

4.find

 如果有，则返回指向的迭代器；如果没有返回的迭代器是end()

当然算法库的find()调用迭代器找数据的函数也可以实现同样的效果，但是两个的底层不同，算法库的find是一种暴力求解，全部遍历，O(N)；但是set的find的函数是基于平衡搜索二叉树的结构，那么就接近于二分查找，O(logN)

5.count

 其实是确定set中对应数据的个数；但是在这里很冗余啊，因为set就是去重的，就算有也只有一个。不过不要担心，count的实现是服务与multiset的

2.multiset

multiset是一个可以接受同样一个数据插入的结构

插入删除等函数跟set基本一致

1.count

count专门服务于它，因为它能重复

2.find

find找到的数是中序遍历的第一个重复的数

2.map的介绍

1.map

1.相关函数

key: 键值对中key的类型
T：键值对中value的类型

int main()
{map<string, string> m;m.insert(pair<string, string>("排序", "sort"));m.insert(make_pair("整数", "int"));for (auto& e : m){cout << e.first << " " << e.second << endl;}return 0;
}

2.operator[]的原理

1.普通计数

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> m;for (auto& e : arr){if (m.find(e) == m.end())m.insert(make_pair(e, 1));elsem.find(e)->second++;}for (auto& e : m){cout << e.first << " " << e.second << endl;}
}

2. []原理和使用计数

1.[]中，pair构造用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
2.如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
3.如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器，那么此时该迭代器的T位置调用默认构造
4.operator[]函数最后将insert返回值键值对中的value返回，那么我们对value进行操作就能起到计数的功能了

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> m;for (auto& e : arr){m[e]++;}for (auto& e : m){cout << e.first << " " << e.second << endl;}
}

其原理就是[]返回了插入位置的second值：如果没有默认int构造的是0；加一就为1了刚好起到计数赋值作用；插入了，返回的是find到的迭代器的second，加一刚好等于计数

除了插入的功能外，其实也可以是修改的功能，将second修改成自己想要的数据

当然[]当查找需谨慎，因为找不到这个值，它就会插入了

2.multimap

multimap不提供方括号，因为它可以有多个一样的，所以查找插入无意义

find依然找到的是中序的第一个数据

 当然它也可以用来统计数目，不过想要判断在对象中是否有相同的值