源码剖析：STL中关联式容器之map
本文深入分析了STL中map容器的实现原理。map是基于红黑树(RB-tree)实现的关联容器，元素以键值对(pair)形式存储，按key自动排序。文章详细解析了map的底层结构，包括模板参数、迭代器类型定义等核心组成。重点介绍了map的构造函数、操作函数（如insert、erase、find等）以及重载运算符的实现方式，这些功能大多通过调用RB-tree的接口完成。与set容器相比，map允许修改实值(value)但不能修改键值(key)，且提供[]运算符方便元素访问
前言
在上一篇博客中主要讲解了关联式容器set，其set的主要操作是调用RB-tree的操作函数来实现的，而本篇博客将重点讲解关联式容器map
了解容器map
容器map的特性主要是：所有元素都会根据元素的键值自动被排序
关于容器map中的元素，其所有元素都是pair，即是一对值。其中pair分为实值(value)和键值(key)，在pair中第一个元素被视为键值，第二个元素被视为实值，在map中不允许两个元素拥有相同的键值（容器set只有实值）。具体的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()){} pair(const T1& a, const T2& b) : first(a), second(b) {}}在容器map中可以通过提供的迭代器对实值进行修改，但不能修改其键值。而在容器set中，迭代器不能修改实值（它并没有键值）
容器map的结构
在容器map中除去有关于STL的萃取定义以外，还在其中定义了仿函数用于比较容器map中的键值，具体源码如下：
//容器map的结构源码template<class Key, class T, class Compare = less<Key>, //默认采用递增排序 class Alloc = alloc>class map{public: typedef Key key_type; //键值类型 typedef T data_type; //实值类型 typedef T mapped_type; typedef pair<const Key, T> value_type; //元素类型 typedef Compare key_compare; //键值比较函数 //定义用于键值比较的仿函数 class value_compare : public vinary_function<value_type, value_type, bool>{ friend class map<Key, T, Compare, Alloc>; protected: Compare comp; value_compare(Compare c) : comp(c){} public: bool operator()(const value_type& x, const value_type& y) const{ return comp(x.first, y.first); } };private: //封装红黑树定义 typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;public: //指针与常数指针 typedef typename rep_type::pointer pointer; typedef typename rep_type::const_pointer const_pointer; //引用与常数引用 typedef typename rep_type::reference redefence; typedef typename rep_type::const_rederence const rederence; //迭代器与常数迭代器 typedef typename rep_type::iterator iterator; typedef typename rep_type::const_iterator const_iterator; //反向迭代器与常量反向迭代器 typedef typename rep_type::reverse_iterator reverse_iterator; typedef typename rep_type::const_reverse_iterator const_reverse_iterator; typedef typename rep_type::size_type size_type; //容器大小类型 typedef typename rep_type::difference_type difference_type; //迭代器间距离}容器map的构造函数
在了解了容器map的模板结构后，以下是容器map的构造函数：
//容器map的构造函数map() : t(Compare()){}explicit map(const Compare& comp) : t(comp){}template <class InputIterator>map(InputIterator first, InputIterator last) : t(Compare){ t.insert_unique(first, last);}template <class InputIterator>map(InputIterator first, InputIterator last, const Compare& comp) : t(comp){ t.insert_unique(first, last);} map(const map<Key, T, Compare, Alloc>& x) : t(x.t){}map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x){ t = x.t; return *this;}容器map的操作函数
以下代码是关于map的操作函数，关于map的许多操作也是调用RB-tree的操作来实现的
//容器map的操作函数key_compare key_comp() const { return t.key_com; }value_compare value_comp() const { return value_compare(t.key_comp()); }iterator begin() { return t.begin(); }const_iterator begin() const { return t.begin(); }iterator end() { reutrn t.end(); }const_iterator end() const { return t.end(); }reverse_iterator rbegin() { return t.rbegin(); }const_reverse_iterator rbegin() { return t.rbegin(); }reverse_iterator rend() { return t.rend(); }const_reverse_iterator rend() { return t.rend(); }bool empty() const { return t.empty(); }size_type size() const { return t.size(); }size_type max_size() const { return t.max_size(); }void swap(map<Key, T, compare, Alloc>& x) { t.swap(x.t); }pair<iterator, bool> insert(const value_type& x){ return t.insert_unique(x);}iterator insert(iterator position, const value_type& x){ return t.insert_unique(position, x);}template<class InputIterator>void insert(InputIterator first, InputIterator last){ t.insert_unique(first, last);}void erase(iterator position) { t.rease(position); }size_type erase(const key_type& x) { return t.rease(x); }void erase(iterator first, iterator last) { t.erase(first, last); }void clear() { t.clear(); }iterator find(const key_type& x) { return t.find(x); }const_iterator find(const key_type& x) const { return t.find(x); }size_type count(const key_type& x) const { return t.count(x); }iterator lower_bound(const key_type& x) { return t.lower_bound(x); }const_iterator lower_bound(const key_type& x) const { return t.upper_bound(x);}pair<iterator, iterator> equal_range(const key_type& x){ return t.equal_range(x);}pair<const_iterator, const_iterator> equal_range(const key_type& x) const { return t.equal_range(x);}容器map的重载运算符函数
//容器map的重载运算符函数friend bool operator==_STL_NULL_TMPL_ARGS (const map&, const map&);friend bool operator<_STL_NULL_TMPL_ARGS (const map&, const map&);T& operator[](const key_type& k){ return (*((insert(value_type(k, T()))).first)).second;}template<class Key, class T, class Compare, class Alloc>inline bool operator==(const map<Key, T, Compare, Alloc>& x, const map<Key, T, Compare, Alloc>& y){ return x.t == y.t;}template<class Key, class T, class Compare, class Alloc>inline bool operator<(const map<Key, T, Compare, Alloc>& x, const map<Key, T, Compare, Alloc>& y){ return x.t < y.t;}PS：由于关联式容器中的set和map大多数是基于RB-tree实现的，所以就没有过多分析其源码，想了解其内容可以具体阅读博客《STL源码刨析：红黑树（RB-tree）》
5次原文点赞；这里的喜欢仅保存在本机