关联容器 — map
最后更新于：2022-04-01 19:54:19
和set类似，也采用了rb_tree作为底层容器，但每个节点是一个pair对象，它关联了键值和实值。键值不允许修改，但实值是可以修改的，等下的代码也会有所说明。
下面是map的代码框架：
~~~
template , class Alloc = alloc> // 默认采用递增顺序
class map {
public:
typedef Key key_type; // 键值类型
typedef T data_type; // 实值类型
typedef T mapped_type;
typedef pair value_type; // 注意const Key，表示无法修改键值
typedef Compare key_compare;
....
private:
// select1st抽取出value_type（pair）内的first元素
typedef rb_tree, key_compare, Alloc> rep_type;
rep_type t; // 底层容器——红黑树
public:
....
typedef typename rep_type::iterator iterator; // 实值可以修改
....
map() : t(Compare()) {}
explicit map(const Compare& comp) : t(comp) {}
....
key_compare key_comp() const { return t.key_comp(); }
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() { return t.end(); }
....
// 下标操作，存在相同键值的节点则返回，否则插入再返回
// insert返回pair，iterator指向红黑树的某个节点
// 下标操作返回迭代器的第二个元素，即实值
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
// 插入/删除
pair insert(const value_type& x) { return t.insert_unique(x); }
iterator insert(iterator position, const value_type& x) {
return t.insert_unique(position, x);
}
....
// map相关操作
iterator find(const key_type& x) { return t.find(x); }
size_type count(const key_type& x) const { return t.count(x); }
iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
pair equal_range(const key_type& x) {
return t.equal_range(x);
}
friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
};
~~~
参考：
《STL源码剖析》 P237.
';