一、关联式容器
vector/list/deque…
这些容器统称为序列式容器
因为其底层为线性序列的数据结构
里面存储的是元素本身
map/set…
这些容器统称为关联式容器
关联式容器也是用来存储数据的
与序列式容器不同的是
其里面存储的是<key, value>结构的键值对
在数据检索时比序列式容器效率更高
二、键值对
“键值对”用来表示具有一一对应关系的一种结构
该结构中一般只包含两个成员变量key和value
key代表键值,value表示与key对应的信息
比如:
现在要建立一个英汉互译的字典
那该字典中必然有英文单词与其对应的中文含义
而且,英文单词与其中文含义是一一对应的关系
即通过该应该单词,在词典中就可以找到与其对应的中文含义
SGI-STL中关于键值对的定义:
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
3.1 树形结构的关联式容器
根据应用场景的不同
C++STL总共实现了
两种不同结构的管理式容器:树型结构与哈希结构
树型结构的关联式容器主要有四种:map、set、multimap、multiset
底层都是使用平衡搜索树(红黑树)来实现
容器中的元素是一个有序的序列
3.2 set的介绍
-
set是按照一定次序存储元素的容器
与map/multimap不同的是
map/multimap中存储的是真正的键值对<key, value>
set中只放value,但在底层实际存放的是由<value, value>构成的键值对 -
在set中,元素是唯一的
元素的value就是key,类型为Tset元素可以插入或删除,但不能修改
map不能修改key,但可以修改value值
set中插入元素时,只需要插入value即可,不需要构造键值对 -
set中的元素总是按内部比较对象(类型比较)
默认按照小于来比较
所指示的特定“严格弱排序”准则进行排序使用set的迭代器遍历set中的元素,可以得到有序序列
-
set容器通过key访问单个元素的速度通常比
unordered_set容器慢,但它们允许根据顺序对
子集进行直接迭代 -
set中查找某个元素,时间复杂度为: l o g 2 n log_2 n log2n
set中的元素之所以不允许修改是怕破坏搜索规则
3.3 set的定义及使用
set的定义
set<int> s1; // 构造int类型的空容器
set<int> s2(s1); // 拷贝构造
string str("abcd");
set<char> s3(str.begin(), str.end()); // 迭代器构造某段区间
set<int, greater<int>> s4; // 比较方式改为大于
set的各个接口跟之前学的vector、list差不多
就不多介绍
set的使用
void test_set()
{
set<int> s;
// 插入元素并去重
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(3);
// 搜索树不允许修改key,可能会破坏搜索的规则
// 1. 迭代器遍历容器
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
// 2. 范围for遍历容器
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 删除元素
s.erase(1);
// 查找删除
set<int>::iterator pos = s.find(2);
if (pos != s.end())
s.erase(pos);
// 计算容器中值为3的元素
cout << s.count(3) << endl;
// 清空容器
s.clear();
// 交换两个容器的数据
set<int> tmp{ 5, 7, 9 };
s.swap(tmp);
}
// 输入一个值,查找在不在
void test_set2()
{
set<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(3);
s.insert(3);
int x;
while (cin >> x)
{
/*
set<int>::iterator it = s.find(x);
if (it != s.end())
{
cout << "在" << endl;
}
else
{
cout << "不在" << endl;
}
*/
if (s.count(x))
{
cout << "在" << endl;
}
else
{
cout << "不在" << endl;
}
}
}
multiset 允许冗余,其他跟set还是一样的
void test_set3()
{
multiset<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(3);
s.insert(3);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 有多个key,find找中序的第一个key
}
四、map
4.1 map的介绍
-
map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元
素,使用迭代器遍历map中的元素,可以得到一个有序序列 -
在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的
内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型
value_type绑定在一起,为其取别名称为pair:typedef pair<const key, T> value_type; -
map容器中的键值key不能修改,但元素值value可以修改
因为map底层是根据每个元素的键值key构建的 -
在内部,map中的元素总是按照键值key进行比较排序的
不传内部比较对象时,map中元素键值key默认按小于比较 -
map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序
对元素进行直接迭代 -
map支持下标访问符,即在[]中放入key,就可以找到与key对应的value
-
map的底层是平衡二叉搜索树(红黑树)
map查找某个元素时间复杂度为 l o g N log N logN
4.2 map的定义及使用
map的定义
// 构造一个key为string,value为char的容器
map<string, char> m1;
// 构造一个跟m1一样的容器
map<string, char> m2(m1);
// 迭代器构造m2的某段区间的容器
map<string, char> m3(m2.begin(), m2.end());
// key的比较方式改成大于
map<string, char, greater<string>> m4;
map的插入和删除
value_type是pair的别名
typedef pair<const key, T> calue_type;
因此插入时需要构造一个pair的匿名对象
void test_map()
{
map<string, string> dict;
// 构造一个pair的匿名对象去插入
dict.insert(pair<string, string>("int", "整型"));
// 用pair代码会很长,更常用的是make_pair
// make_pair是一个函数模板,能通过传参自动推导类型
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("count", "计数"));
// 已经有的key,会插入失败
dict.insert(make_pair("count", "(计数)"));
// map<string, string>::iterator dit = dict.begin();
auto dit = dict.begin();
while (dit != dict.end())
{
// 直接*dit无法通过编译.C++不支持返回两个值
// dit解引用后是一个pair的结构体,里面有两个值,并不支持流插入
// cout << (*dit).first << ":" << (*dit).second << endl;
cout << dit->first << ":" << dit->second << endl; // 结构体里的指针一般用箭头
dit++;
}
cout << endl;
// 根据key值删除
dict.erase(string);
//迭代器删除
map<string, string>::iterator pos = dict.find(sort);
if (pos != dict.end())
dict.erase(pos);
}
insert的返回值是pair
pair第一个成员是map的迭代器类型
第二个成员是bool类型
-
若插入元素的键值key在map中不存在
insert插入成功,并返回插入后元素的迭代器和true
-
若插入元素的键值key在map中已存在
则insert插入失败,并返回map中键值为key元素的迭代器和false
map的operator[ ]
operator[ ] 的返回值
[ ]operator实现的逻辑分为以下3个步骤:
- 调用insert函数插入键值对
- 拿出从insert函数获取到的迭代器
- 返回该迭代器位置元素的值value
代码分解
mapped_type& operator[] (const key_type& k)
{
//1. 调用insert函数插入键值对
pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
//2. 拿出从insert函数获取到的迭代器
iterator it = ret.first;
//3. 返回该迭代器位置元素的值value
return it->second;
}
[ ]的插入、修改、查找、插入+修改
以及统计水果出现的次数
void test_map2()
{
string arr[] = { "苹果", "香蕉", "西瓜", "梨子", "香蕉", "西瓜", "西红柿", "香蕉", "西瓜", "苹果", "西红柿" };
map<string, int> countMap;
//for (auto e : arr) // 统计水果出现次数
//{
// map<string, int>::iterator it = countMap.find(e);
// if (it == countMap.end())
// {
// countMap.insert(make_pair(e, 1));
// }
// else
// {
// it->second++;
// }
//}
for (auto& e : arr) // 方括号统计水果出现次数
{
countMap[e]++; // [] 的三个功能: 插入、修改、查找、插入+修改
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl; // 结构体里的指针一般用箭头
}
cout << endl;
}
// countMap[e]++; 这段代码底层实现
// V& operator[](const K& key)
// {
// pair<iterator, bool> ret = insert(make_pair(key, V()));
// return ret.first->second;
//}
void test_map3()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("count", "计数"));
dict.insert(make_pair("count", "(计数)"));
dict["left"]; // 插入
dict["right"] = "右"; // 插入+修改
dict["string"] = "(字符串)"; // 修改
cout << dict["string"] << endl; // 查找
cout << dict["endl"] << endl; // 查找
auto dit = dict.begin();
while (dit != dict.end())
{
cout << dit->first << ":" << dit->second << endl;
dit++;
}
cout << endl;
}
[ ]operator的返回值是key的value的引用
所以我们对该函数返回值的修改
实际就是对键值key的value的修改
multimap
multimap跟map基本一样
只是multimap允许键值冗余
find返回值是返回搜索树中序第一个键值
为key的元素的迭代器
由于冗余,调用operator[ ]时
返回键值应为哪个key的value引用
而存在歧义,因此multimap没有operator[ ]接口
如果支持迭代器就一定支持范围for
因为范围for的底层就是迭代器
五、map和set的区别
-
map元素是key-value(关键字-值)对
set元素是关键字
map和set都不允许插入重复关键字 -
set迭代器是const
所以不允许修改元素值
map可以修改value,但不能修改key
map和set底层红黑树依靠关键字保持有序性
所以不允许修改关键字 -
map支持下标操作,set则不支持
注意:map下标通过insert实现
也就是尝试插入一个查询键值对
如果存在则返回该键值对文章来源:https://www.toymoban.com/news/detail-777672.html
✨✨✨✨✨✨✨✨
本篇博客完,感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨文章来源地址https://www.toymoban.com/news/detail-777672.html
到了这里,关于【C++进阶04】STL中map、set、multimap、multiset的介绍及使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!