概述
一、关联容器map和multimap
C++STL库中，有一组关联容器，其中就包含map,map顾名思意，就是一个映射，学过基础数学的都明白，STL中的map底层是通过红黑树来实现的，这个可以参看一下《STL源码剖析》中，对红黑树的详细说明，包括单旋，双旋转等。在一些算法书籍上也总结很多的优秀的学习方法，这里就不再详细说明红黑树的算法实现了。
看一下c++ STL中的定义：
//Map
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;
//since c++17
namespace pmr {
template <class Key, class T, class Compare = std::less<Key>>
using map = std::map<Key, T, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>
}
//multimap
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class multimap;
//since C++ 17
namespace pmr {
template <class Key, class T, class Compare = std::less<Key>>
using multimap = std::multimap<Key, T, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}
二、二者的不同
STL中有Map和Multimap两种，都是将KEY/VALUE pair做为元素基本单位，即使没有学过这个的，但是搞过NOSQL的可能也一下子也能明白。区别在于，Map是一一映射，而Multimap是一对多映射。它们两个都是根据Key值进行自动排序的，这才是重点。Key和Value都必须是可拷贝或者可移动的（Move语义），假如指定了排序规则，Key还必须是可比较的。
在底层的实现中，由于后者存在有相同的Key，所以在插入时，会使用equal而不是unique来进行操作RB_tree.
三、源码分析
看一下源码：
template <class _Kty, class _Ty, class _Pr = less<_Kty>, class _Alloc = allocator<pair<const _Kty, _Ty>>>
class map : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false>> {
// ordered red-black tree of {key, mapped} values, unique keys
public:
static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<pair<const _Kty, _Ty>, typename _Alloc::value_type>,
_MISMATCHED_ALLOCATOR_MESSAGE("map<Key, Value, Compare, Allocator>", "pair<const Key, Value>"));
using _Mybase = _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false>>;
using _Nodeptr = typename _Mybase::_Nodeptr;
using key_type = _Kty;
using mapped_type = _Ty;
using key_compare = _Pr;
using value_compare = typename _Mybase::value_compare;
using value_type = pair<const _Kty, _Ty>;
......
using const_reference = const value_type&;
using iterator = typename _Mybase::iterator;
using const_iterator = typename _Mybase::const_iterator;
using reverse_iterator = typename _Mybase::reverse_iterator;
using const_reverse_iterator = typename _Mybase::const_reverse_iterator;
using _Alnode = typename _Mybase::_Alnode;
using _Alnode_traits = typename _Mybase::_Alnode_traits;
#if _HAS_CXX17
using insert_return_type = _Insert_return_type<iterator, typename _Mybase::node_type>;
#endif // _HAS_CXX17
map() : _Mybase(key_compare()) {}
explicit map(const allocator_type& _Al) : _Mybase(key_compare(), _Al) {}
map(const map& _Right) : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(_Right._Getal())) {}
map(const map& _Right, const allocator_type& _Al) : _Mybase(_Right, _Al) {}
explicit map(const key_compare& _Pred) : _Mybase(_Pred) {}
map(const key_compare& _Pred, const allocator_type& _Al) : _Mybase(_Pred, _Al) {}
template <class _Iter>
map(_Iter _First, _Iter _Last) : _Mybase(key_compare()) {
insert(_First, _Last);
}
template <class _Iter>
map(_Iter _First, _Iter _Last, const key_compare& _Pred) : _Mybase(_Pred) {
insert(_First, _Last);
}
template <class _Iter>
map(_Iter _First, _Iter _Last, const allocator_type& _Al) : _Mybase(key_compare(), _Al) {
insert(_First, _Last);
}
template <class _Iter>
map(_Iter _First, _Iter _Last, const key_compare& _Pred, const allocator_type& _Al) : _Mybase(_Pred, _Al) {
insert(_First, _Last);
}
map& operator=(const map& _Right) {
_Mybase::operator=(_Right);
return *this;
}
map(map&& _Right) : _Mybase(_STD move(_Right)) {}
map(map&& _Right, const allocator_type& _Al) : _Mybase(_STD move(_Right), _Al) {}
map& operator=(map&& _Right) noexcept(_Alnode_traits::is_always_equal::value&& is_nothrow_move_assignable_v<_Pr>) {
_Mybase::operator=(_STD move(_Right));
return *this;
}
mapped_type& operator[](key_type&& _Keyval) { // find element matching _Keyval or insert value-initialized value
return _Try_emplace(_STD move(_Keyval)).first->_Myval.second;
}
void swap(map& _Right) noexcept(noexcept(_Mybase::swap(_Right))) {
_Mybase::swap(_Right);
}
using _Mybase::insert;
template <class _Valty, enable_if_t<is_constructible_v<value_type, _Valty>, int> = 0>
pair<iterator, bool> insert(_Valty&& _Val) {
return this->emplace(_STD forward<_Valty>(_Val));
}
template <class _Valty, enable_if_t<is_constructible_v<value_type, _Valty>, int> = 0>
iterator insert(const_iterator _Where, _Valty&& _Val) {
return this->emplace_hint(_Where, _STD forward<_Valty>(_Val));
}
private:
template <class _Keyty, class... _Mappedty>
pair<_Nodeptr, bool> _Try_emplace(_Keyty&& _Keyval, _Mappedty&&... _Mapval) {
const auto _Loc = _Mybase::_Find_lower_bound(_Keyval);
if (_Mybase::_Lower_bound_duplicate(_Loc._Bound, _Keyval)) {
return {_Loc._Bound, false};
}
_Mybase::_Check_grow_by_1();
const auto _Scary = _Mybase::_Get_scary();
const auto _Inserted = _Tree_temp_node<_Alnode>(_Mybase::_Getal(), _Scary->_Myhead, piecewise_construct,
_STD forward_as_tuple(_STD forward<_Keyty>(_Keyval)),
_STD forward_as_tuple(_STD forward<_Mappedty>(_Mapval)...))
._Release();
// nothrow hereafter
return {_Scary->_Insert_node(_Loc._Location, _Inserted), true};
}
......
public:
template <class... _Mappedty>
pair<iterator, bool> try_emplace(const key_type& _Keyval, _Mappedty&&... _Mapval) {
const auto _Result = _Try_emplace(_Keyval, _STD forward<_Mappedty>(_Mapval)...);
return {iterator(_Result.first, _Mybase::_Get_scary()), _Result.second};
}
......
};
template <class _Traits>
class _Tree { // ordered red-black tree for map/multimap/set/multiset
public:
using value_type = typename _Traits::value_type;
using allocator_type = typename _Traits::allocator_type;
protected:
using _Alty = _Rebind_alloc_t<allocator_type, value_type>;
using _Alty_traits = allocator_traits<_Alty>;
using _Node = _Tree_node<value_type, typename _Alty_traits::void_pointer>;
using _Alnode = _Rebind_alloc_t<allocator_type, _Node>;
using _Alnode_traits = allocator_traits<_Alnode>;
using _Nodeptr = typename _Alnode_traits::pointer;
using _Scary_val = _Tree_val<conditional_t<_Is_simple_alloc_v<_Alnode>, _Tree_simple_types<value_type>,
_Tree_iter_types<value_type, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, value_type&, const value_type&,
_Nodeptr>>>;
static constexpr bool _Multi = _Traits::_Multi;
enum _Redbl { // colors for link to parent
_Red,
_Black
};
......
};
从上面可以看到它的基本数据结构是以Tree为定义的，注释中“ordered red-black tree for map/multimap/set/multiset”说明了所有。
四、应用例程
看一下具体的应用例程(https://en.cppreference.com/)：
#include <iostream>
#include <map>
#include <string>
#include <string_view>
struct FatKey { int x; int data[1000]; };
struct LightKey { int x; };
// Note: as detailed above, the container must use std::less<> (or other
// transparent Comparator) to access these overloads.
// This includes standard overloads, such as between std::string and std::string_view.
bool operator<(const FatKey& fk, const LightKey& lk) { return fk.x < lk.x; }
bool operator<(const LightKey& lk, const FatKey& fk) { return lk.x < fk.x; }
bool operator<(const FatKey& fk1, const FatKey& fk2) { return fk1.x < fk2.x; }
void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
std::cout << comment;
for (const auto& [key, value] : m) {
std::cout << key << " = " << value << "; ";
}
std::cout << "n";
}
int main()
{
// Create a map of three strings (that map to integers)
std::map<std::string, int> m { {"CPU", 10}, {"GPU", 15}, {"RAM", 20}, };
print_map("Initial map: ", m);
m["CPU"] = 25; // update an existing value
m["SSD"] = 30; // insert a new value
print_map("Updated map: ", m);
//multimap demo
std::multimap<int,char> example = {{1,'a'},{2,'b'}};
auto search = example.find(2);
if (search != example.end()) {
std::cout << "Found " << search->first << " " << search->second << 'n';
} else {
std::cout << "Not foundn";
}
// transparent comparison demo
std::multimap<FatKey, char, std::less<>> example2 = { { {1, {} },'a'}, { {2, {} },'b'} };
LightKey lk = {2};
auto search2 = example2.find(lk);
if (search2 != example2.end()) {
std::cout << "Found " << search2->first.x << " " << search2->second << 'n';
} else {
std::cout << "Not foundn";
}
// Obtaining const iterators.
// Compiler decides whether to return iterator of (non) const type by way of accessing
// map; to prevent modification on purpose, one of easiest choices is to access map by
// const reference.
const auto& example2ref = example2;
auto search3 = example2ref.find(lk);
if (search3 != example2.end()) {
std::cout << "Found " << search3->first.x << ' ' << search3->second << 'n';
// search3->second = 'c'; // error: assignment of member
// 'std::pair<const FatKey, char>::second'
// in read-only object
}
}
运行结果是：
Initial map: CPU = 10; GPU = 15; RAM = 20;
Updated map: CPU = 25; GPU = 15; RAM = 20; SSD = 30;
Found 2 b
Found 2 b
Found 2 b
五、注意点
使用Map赋值时，尽量不要使用类似数组方式的形式进行赋值，如 map_test[3] = “test”,这种方式会导致如果没有KEY（3）对应的元素，就自动插入这个值，而产生不必要的麻烦。同样，查找一定要使用find函数而不是挨个自己比较。
Map和Multimap在新的标准环境下，一般不推荐使用了，主要是这东西线程不安全操作起来还有各种小细节需要考虑，搞不好就进了坑了。基本上现在推荐使用的都是无序容器unordered_map,在后面的章节会对其进行详细分析。
六、总结
明白这两个Map在意义在于掌握STL中的映射使用，更重要的是明白RB_Tree的应用，明白使用库其实是屏蔽了复杂的数据结构在背后的，而不是用不到数据结构。
最后
以上就是发嗲流沙为你收集整理的跟我学C++中级篇——STL的容器Map三、源码分析的全部内容，希望文章能够帮你解决跟我学C++中级篇——STL的容器Map三、源码分析所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[LeetCode]LRU Cache](/uploads/reation/bcimg7.png)
发表评论 取消回复