关联式容器
- 包括 map、multimap、set 以及 multiset 这 4 种容器。
- 和序列式容器区别:
a . 关联式容器在存储元素时还会为每个元素在配备一个键,整体以键值对的方式存储到容器中。
b . 相比前者,关联式容器可以通过键值直接找到对应的元素,而无需遍历整个容器。
c . 另外,关联式容器在存储元素,默认会根据各元素键值的大小做升序排序。
d . 相比其它类型容器,关联式容器查找、访问、插入和删除指定元素的效率更高。
注意 : 关联式容器所具备的这些特性,归咎于 STL 标准库在实现该类型容器时,底层选用了 「红黑树」
关联式容器名称 | 特点 |
---|---|
map | 定义在 |
set | 定义在 头文件中,使用该容器存储的数据,各个元素键和值完全相同,且各个元素的值不能重复(保证了各元素键的唯一性)。该容器会自动根据各个元素的键(其实也就是元素值)的大小进行升序排序(调用 std::less)。 |
multimap | 定义在 |
multiset | 定义在 头文件中,和 set 容器唯一的不同在于,multiset 容器中存储元素的值可以重复(一旦值重复,则意味着键也是重复的)。 |
除此之外,C++ 11 还新增了 4 种哈希容器,即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说,它们也属于关联式容器,但哈希容器底层采用的是哈希表,而不是红黑树。
map
- map 各个键值对的键和值可以是任意数据类型,包括 C++ 基本数据类型(int、double 等)、使用结构体或类自定义的类型
- 与此同时,在使用 map 容器存储多个键值对时,该容器会自动根据各键值对的键的大小,按照既定的规则进行排序。默认情况下,map 容器选用std::less排序规则(其中 T 表示键的数据类型), 其会根据键的大小对所有键值对做升序排序
- 使用 map 容器存储的各个键值对,键的值既不能重复也不能被修改。换句话说,map 容器中存储的各个键值对不仅键的值独一无二,键的类型也会用 const 修饰,这意味着只要键值对被存储到 map 容器中,其键的值将不能再做任何修改。
1. 初始化
std::map<std::string, std::strig> my_map1 = {{"k1", "v1"},{"k2", "v2"}};
std::map<std::string, std::strig> my_map1 = {std::make_pair("k1", "v1"),std::make_pair("k2", "v2")};
2. 迭代器
- map 容器配备的是双向迭代器
- lower_bound(key) :返回的是指向第一个键不小于 key 的键值对的迭代器;
- upper_bound(key) :返回的是指向第一个键大于 key 的键值对的迭代器;
- equal_range(key) :该方法会返回一个 pair 对象,其中的 2 个元素都是迭代器类型,其中 pair.first 实际上就是 lower_bound(key) 的返回值,而 pair.second 则等同于 upper_bound(key) 的返回值。
注意: 上述更加适用于multimap, map 只会返回一个结果。
3. map插入方式
- 使用 [ ] 运算符:
a. 当操作对象为 map 容器中已存储的键值对时,则借助 [ ] 运算符,既可以获取指定键对应的值,还能对指定键对应的值进行修改
b. 反之,若 map 容器内部没有存储以 [ ] 运算符内指定数据为键的键值对,则使用 [ ] 运算符会向当前 map 容器中添加一个新的键值对,为默认值。 - insert() 成员方法
a. 无需指定插入位置,直接将键值对添加到 map 容器中:
//1、引用传递一个键值对
pair<iterator,bool> insert (const value_type& val);
//2、以右值引用的方式传递键值对
template <class P>
pair<iterator,bool> insert (P&& val);
如果成功插入 val,则该迭代器指向新插入的 val,bool 值为 true;
如果插入 val 失败,则表明当前 map 容器中存有和 val 的键相同的键值对(用 p 表示),此时返回的迭代器指向 p,bool 值为 false。
注意: 使用这种方法,不会覆盖原有的值意思是如果本来存在一个key,那么就插入失败。文章来源:https://www.toymoban.com/news/detail-653468.html
4. 如何向一个map容器中添加一个元素,有什么区别?
- map::operator[]和map::insert两种方法都可以实现向map容器中添加一个元素的目的。至于它们之间的区别,这里需要分类讨论:被添加的元素事先在map中不存在;被添加的元素事先在map中已存在。
被添加的元素事先在map中不存在
- map::operator[]会在map中创建一个元素(k, v),其中v通过默认构造函数创建。map::operator[]返回v的引用,紧接着v被赋予为新值。听上去已经有点冗余了。
- 而map::insert高效很多,直接使用目标值构造一个v,不需要赋值操作。
- 结论就是如果被添加的元素事先在map中不存在,map::insert的效率要好于map::operator[]。
被添加的元素事先在map中存在
- map::operator[]会返回一个引用,指向map中相同k对应的v,之后用目标值更新原来的v。
- 而map::insert就复杂了,如果元素事先已经在map中存在,map::insert会以失败告终,详见测试代码执行结果打印出来的“failed in testmap.insert(make_pair(2, 100.4));”。2. map::insert如果想要达到更新的目的,需要根据insert操作的结果作出进一步赋值操作。这里隐含着pair对象的构建和析构,是相较于map::operator[]多余的操作。
- 结论就是如果被添加元素事先在map中存在,map::operator[]的效率要好于map::insert。
5. STL之map容器的三种插入方式insert emplace emplace_hint哪种效率更高
- 结论: C++11新增的emplace() 和 emplace_hint()都比insert效率高
- 原因: 使用 insert() 向 map 容器中插入键值对的过程是,先创建该键值对,然后再将该键值对复制或者移动到 map 容器中的指定位置;
- 使用 emplace() 或 emplace_hint() 插入键值对的过程是,直接在 map 容器中的指定位置构造该键值对。
template <class... Args>
pair<iterator,bool> emplace (Args&&... args);
//参数 (Args&&... args) 指的是,这里只需要将创建 新键值对所需的数据作为参数直接传入即可,此方法可以自行利用这些数据构建出指定的键值对。另外,该方法的返回值也是一个 pair 对象,其中 pair.first 为一个迭代器,pair.second 为一个 bool 类型变量:
当该方法将键值对成功插入到 map 容器中时,其返回的迭代器指向该新插入的键值对,同时 bool 变量的值为 true;
当插入失败时,则表明 map 容器中存在具有相同键的键值对,此时返回的迭代器指向此具有相同键的键值对,同时 bool 变量的值为 false。
//创建并初始化 map 容器
std::map<string, string>mymap;
//插入键值对
pair<map<string, string>::iterator, bool> ret = mymap.emplace("STL教程", "http://c.biancheng.net/stl/");
cout << "1、ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
注意: []直接不参与战争
引用链接:https://blog.csdn.net/weixin_39703605/article/details/108190578文章来源地址https://www.toymoban.com/news/detail-653468.html
到了这里,关于面试之快速学习STL-map的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!