STL源码刨析：关联式容器之map

本文主要是介绍STL源码刨析：关联式容器之map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

        1.前言

        2.了解容器map

        3.容器map的结构

        4.容器map的构造函数

        5.容器map的操作函数

        6.容器map的重载运算符函数

---

前言

        在上一篇博客中主要讲解了关联式容器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）》

这篇关于STL源码刨析：关联式容器之map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---