根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
set
- set 是按照一定次序存储元素的容器
- 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
- 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代。
- set在底层是用二叉搜索树(红黑树)实现的。
#include <iostream>
#include <map>
#include <set>
using namespace std;
void test_set1()
{
set<int> s;
s.insert(3);
s.insert(2);
s.insert(4);
s.insert(5);
s.insert(1);
s.insert(5);
s.insert(2);
s.insert(5);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
auto pos = s.find(3);//o(logn)
//auto pos = find(s.begin(), s.end(), 3);o(N) 暴力查找
if (pos != s.end())
{
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_set1();
return 0;
}
set操作函数方法
find查找
find(时间复杂度为log(N)),利用二叉搜索树查找方式。返回值为迭代器
count返回重复数字出现的次数
lower_bound 返回大于等于目标值的iterator
lower_bound
在查找目标值的时候,只针对搜索大于等于该值的目标,并且找到后返回其iterator
位置,如果没有找到,则返回end
位置
upper_bound返回大于目标值的iterator
upper_bound
返回目标值后一个位置的iterator
位置
equal_range 获取相等元素的范围
如果要查找的元素在本set中没有,则会返回跟他最接近且大的值,如果要查找的元素只有一个,则会返回元素本身到最后一个元素区间。
源代码
void test_set1()
{
set<int> s;
s.insert(3);
s.insert(2);
s.insert(4);
s.insert(5);
s.insert(1);
s.insert(5);
s.insert(2);
s.insert(5);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
set<int>::iterator pos = s.find(3);//o(logn)
auto pos = find(s.begin(), s.end(), 3);o(N)
if (pos != s.end())
{
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
multiset 操作方法
- multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。
- 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的),但可以从容器中插入或删除。
- 在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
- multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭代器遍历时会得到一个有序序列。
- multiset底层结构为二叉搜索树(红黑树)。
注意:
- multiset中再底层中存储的是<value, value>的键值对
- mtltiset的插入接口中只需要插入即可
- 与set的区别是,multiset中的元素可以重复,set是中value是唯一的
- 使用迭代器对multiset中的元素进行遍历,可以得到有序的序列
- multiset中的元素不能修改
- 在multiset中找某个元素,时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
- multiset的作用:可以对元素进行排序
count返回重复数字出现的次数
lower_bound和upper_bound
此处只简单演示set与multiset的不同,其他接口接口与set相同
源代码
void test_set2()
{
multiset<int> s;
s.insert(3);
s.insert(5);
s.insert(8);
s.insert(7);
s.insert(7);
s.insert(9);
s.insert(7);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
cout << s.count(7) << endl;
auto ret = s.equal_range(7);
auto itlow = ret.first;
auto itup = ret.second;
cout << *itlow << endl;
cout << *itup << endl;
s.erase(itlow, itup);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
认识pair
模拟实现pair
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)
{}
};
认识make_pair
make_pair就直接帮我们内部调用了pair
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中的元素总是按照键值key进行比较排序的。
- map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
- map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。
insert
insert插入用的pair来插入的
private:
int _a1;
int _a2;
};
void test_map1()
{
map<string, string> dict;
pair<string, string> kv1("insert", "插入");
dict.insert(kv1);
dict.insert(pair<string, string>("sort", "排序"));
//c++98
dict.insert(make_pair("string", "字符串"));
//C++11多参数的构造函数隐式类型转换
dict.insert({ "apple","苹果" });
//例如
string str = "hello";//字符串隐式类型转换
A aa1 = { 1,2 };
}
在我们的日常使用中,map中的key值是不可以修改的,只有value值是可以修改的
void test_map2()
{
map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("sort", "排序"));
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//it->first = "xxx";
it->second = "xxx";
cout << (*it).first << " : " << (*it).second << endl;
cout << it->first << " : " << it->second << endl;
it++;
}
cout << endl;
for (const auto& kv : dict)
{
cout << kv.first << " : " << kv.second << endl;
}
}
opeartor[]
map的【】和我们平时使用的【】是完全不一样的
在元素访问时,有一个与operator[]类似的操作at()(该函数不常用)函数,都是通过key找到与key对应的value然后返回其引用,不同的是:当key不存在时,operator[]用默认value与key构造键值对然后插入,返回该默认value,at()函数直接抛异常。
普通插入
使用operator[] 插入
void test_map3()
{
string arr[] = { "苹果","橘子","梨","苹果","橘子","梨" ,"苹果" };
map<string, int> countMap;
/*for (auto e : arr)
{
auto it = countMap.find(e);
if (it == countMap.end())
{
countMap.insert(make_pair(e, 1));
}
else
{
it->second++;
}
}*/
for (auto e : arr)
{
countMap[e]++;
}
for (const auto& kv : countMap)
{
cout << kv.first << " ; " << kv.second << endl;
}
}
验证【】插入方法
void test_map5()
{
map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("sort", "排序"));
cout << dict["sort"] << endl;//查找和读
dict["map"]; //插入
dict["map"] = "映射地图";//修改
dict["insert"] = "xxx";//修改
dict["set"] = "集合";//插入+修改
for (auto it : dict)
{
cout << it.first << " : " << it.second << endl;
}
}
文章来源:https://www.toymoban.com/news/detail-629219.html
multimap
multimap只跟map差一个operator[]操作方法,其次,multimap还支持多个相同元素的存放文章来源地址https://www.toymoban.com/news/detail-629219.html
到了这里,关于【C++】树形结构的关联式容器(map、set)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!