首页 / C++ / C++ map set
C++ map set
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++ map set,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2746字,纯文字阅读大概需要4分钟。
内容图文
C++ map set
map 和 set 的内部数据结构是红黑树
PS:二叉树的存储方式
二叉树既可以用链式存储,也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树,其他类型的二叉树用数组存储会比较浪费存储空间。堆其实就是一种完全二叉树,最常用的存储方式就是数组。
PSS: 散列表 vs 二叉查找(排序)树
散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序。而对于二叉查找树来说,我们只需要中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列。
散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn)。
散列表的构造比二叉查找树要复杂,需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定。
尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高。
红黑树
我们学习数据结构和算法,要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树,也不例外。你如果能搞懂这几个问题,其实就已经足够了。
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中,复杂度退化的问题而产生的。红黑树的高度近似 log2n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。
map 和 set 使用
- map
// ref: https://blog.csdn.net/bingtang_blog/article/details/52730530
#include<iostream>
#include<map>
using namespace std;
int main(){
//map声明,加入有文件map
map<int, int> m;
//插入元素要用makr_pair的方式
m.insert(make_pair(1, 5));
//通过iterator来查找map里面的元素
map<int, int>::iterator ite;
ite = m.find(1);
//如果找到了,那么我们就删除掉原有的元素,加入新元素
//因为后来加入的元素如果键重复,不能覆盖,会被忽略
if(ite != m.end()){
m.erase(1);
m.insert(make_pair(1, 6));
}else{
//没找到直接加入
m.insert(make_pair(1, 6));
}
//用这种方式,来输出键值对的值
cout << ite->second << endl;
//历遍map元素,并输出键值对
for(ite = m.begin(); ite != m.end(); ite++){
cout << ite->first << "\t" << ite->second << endl;
}
}
- set
// ref: https://blog.csdn.net/bingtang_blog/article/details/52730530
#include<iostream>
#include<map>
#include<set>
using namespace std;
int main(){
//声明集合,加入头文件<set>
set<int> s;
//向集合中插入元素
s.insert(1);
s.insert(2);
s.insert(3);
//在集合中查找元素
set<int>::iterator ite;
ite = s.find(1);
if(ite == s.end()){
cout << "Not found" << endl;
}else{
cout << "Found" << endl;
}
//集合删除元素
s.erase(2);
//在集合中查找元素的第二种方式
if(s.count(3) != 0){
cout << "Found" << endl;
}else{
cout << "Not found" << endl;
}
//历遍集合元素
for(ite = s.begin(); ite != s.end(); ite++){
cout << *ite << endl;
}
}
内容总结
以上是互联网集市为您收集整理的C++ map set全部内容,希望文章能够帮你解决C++ map set所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。