该系列文章是本人在学习C++map和set 的过程中总结下来的,里面涉及到相关源码,请结合我的源码注释 源码分析资料进行阅读
根据应用场景的不同,STL总共实现了两种不同结构的关联式式容器:树型结构与哈希结构
关联式容器 |
容器结构 |
底层实现 |
set、map、multiset、multimap |
树型结构 |
平衡搜索树(红黑树) |
unordered_set、unordered_map、unordered_multiset、unordered_multimap |
哈希结构 |
哈希表,哈希桶 |
概念:
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量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)
{}
};
set是按照一定次序存储元素的容器,这种次序使用set的迭代器遍历set中的元素,可以得到有序序列
注:与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对
在set中,元素的value也标识它(value就是key,类型为T),set中插入元素时,只需要插入value即可,不需要构造键值对,并且每个value必须是唯一的(可以使用set进行去重)
注:set中的元素不能在容器中修改(元素总是const,修改无法保证数据的次序),但是可以从容器中插入或删除它们
在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序注:默认按照小于来比较,中序遍历后为升序序列
set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代
set在底层是用二叉搜索树(红黑树)实现的
注:接近完全二叉树,查找的时间复杂度为logN
解释:
T: set中存放元素的类型,实际在底层存储<value, value>的键值对
Compare:比较方法,set中元素默认按照小于来比较(中序遍历为升序)
Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理
注意:在使用set时,需要包含头文件set
void testset1()
{
set<int> set1;//空构造
int num[] = { 4,5,1,8,2,4,6,3 };
set<int> set2(num, num+sizeof(num)/sizeof(num[0]));//对于数组使用原生指针构造
set<int> set3(set2);//拷贝构造
// 范围for打印,从打印结果中可以看出:set可去重
for (auto& e : set3)
cout << e << " ";
cout << endl;
}
void testset2()
{
int num[] = { 4,5,1,8,2,4,6,3 };
set<int> set1(num, num + sizeof(num) / sizeof(num[0]));//对于数组使用原生指针构造
// 范围for打印,从打印结果中可以看出:set可去重
for (auto& e : set1)
cout << e << " ";
cout << endl;
//迭代器正向遍历
auto it1 = set1.begin();
while (it1 != set1.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
//迭代器反向遍历
auto it2 = set1.rbegin();
while (it2 != set1.rend())
{
cout << *it2 << " ";
it2++;
}
}
void testset3()
{
int num[] = { 1,8,4,5,3,9,2,6,7,4,5 };
set<int> set;
for (int e : num)//插入
{
auto ret=set.insert(e);
if (ret.second == false)
cout << e << "插入失败" << endl;
}
for (auto& e : set)//遍历
cout << e << " ";
cout << endl;
cout << "count 5:" << set.count(5) << endl;
set.erase(set.find(8));//删除
for (auto& e : set)
cout << e << " ";
cout << endl;
}
四、C++中的multiset
multiset的介绍:
multiset容器与set容器实现和接口基本一致,唯一区别就是,multiset允许键值冗余,即multiset容器当中存储的元素是可以重复的
注意:对于find来说multiset返回底层搜索树中序的第一个键值为key的元素的迭代器
void TestMSet()
{
int array[] = { 2, 1, 2, 1, 6, 0, 1, 6, 4, 7 };
// 允许键值冗余
multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
for (auto& e : s)
cout << e << " ";
cout << endl;
}
注:set和map基本差不多,但是set是k模型,而map是kv模型,这导致在部分地方又有些不一样
注意:在使用map时,需要包含头文件map
map的构造:
void testmap1()
{
map<int, int> map1;//空构造
int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 };
for (auto e : num)
{
map1.insert(make_pair(e,e));
}
map<int, int> map2(map1.begin(),map1.end());//迭代区间构造
map<int, int> map3(map2);//拷贝构造
for (auto& e : map3)
{
cout << e.first << ":" << e.second << endl;
}
}
void testmap2()
{
map<int, int> map1;//空构造
int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 };
for (auto e : num)
{
//map1.insert(pair<int,int>(e, e));
map1.insert(make_pair(e, e));//等同于
}
//迭代器正向遍历
auto it1 = map1.begin();
while (it1 != map1.end())
{
//cout << (*it1).first << ":"<<(*it1).second<<endl;
cout << it1->first << ":"<<it1->second<<endl;//等同于
it1++;
}
//迭代器反向遍历
auto it2 = map1.rbegin();
while (it2 != map1.rend())
{
cout << it2->first << ":" << it2->second << endl;//等同于
it2++;
}
}
void testmap3()
{
int arr[] = { 1,4,8,5,9,6,4,2,9,6,4,1,8,5 };
map<int, int, greater<int>> countmap;
for (auto e : arr)
{
countmap[e]++;
//当不存在对应key则插入键值pair(e,int()),这里的int()即是0 返回0再++
//当存在对应key则返回对应的value,再++
}
auto it1 = countmap.begin();
while (it1 != countmap.end())
{
//cout << (*it1).first << ":"<<(*it1).second<<endl;
cout << it1->first << ":" << it1->second << endl;//等同于
it1++;
}
}
void testmap4()
{
int num[] = { 1,8,4,5,3,9,2,6,7,4,5 };
map<int,int> map;
for (int e : num)//插入
{
auto ret = map.insert(make_pair(e,e));
if (ret.second == false)
cout << e << "插入失败" << endl;
}
for (auto& e : map)//遍历
cout << e.first << ":" << e.second << endl;
cout << "count 5:" << map.count(5) << endl;
map.erase(map.find(8));//删除
for (auto& e : map)//遍历
cout << e.first << ":" << e.second << endl;
}
void testMmap()
{
multimap<int, string> mm;
//允许键值冗余
mm.insert(make_pair(2, "two"));
mm.insert(make_pair(2, "double"));
mm.insert(make_pair(2, "2"));
mm.insert(make_pair(2, "second"));
mm.insert(make_pair(1, "one"));
mm.insert(make_pair(3, "three"));
for (auto e : mm)
{
cout << e.first << ":" << e.second << endl;
}
cout << endl;
//从第一个2找起,遍历到最后一个
auto pos = mm.find(2);
while (pos != mm.end() && pos->first == 2)
{
cout << pos->first << ":" << pos->second << endl;
pos++;
}
}
本文到这里就结束了,如果你觉得这篇文章对你有帮助 点赞关注