C++(STL):31 ---关联式容器map源码剖析

用户3479834

发布于 2021-02-03 06:46:49

1.7K00

代码可运行

文章被收录于专栏：游戏开发司机游戏开发司机

运行总次数：0

代码可运行

map的特性

所有元素都会根据元素的键值自动被排序

map中的pair结构

map的所有元素类型都是pair，同时拥有实值（value）和键值（key）
pair的第一个元素视为键值，第二个元素视为实值
map不允许两个元素拥有相同的键值
下面是stl_pair.h中pair的定义：

//代码摘录与stl_pair.h
template <class _T1, class _T2>
struct pair {
typedef _T1 first_type;
typedef _T2 second_type;


_T1 first;
_T2 second;
pair() : first(_T1()), second(_T2()) {}
pair(const _T1& __a, const _T2& __b) : first(__a), second(__b) {}


#ifdef __STL_MEMBER_TEMPLATES
template <class _U1, class _U2>
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
#endif
};

map的迭代器

不可以根据map的迭代器改变节点的键值，但是可以通过map的迭代器改变节点的实值
因此，map iterators既不是一种constant iterators，也不是一种mutable iterators

map拥有与list的相同的某些性质

当客户端对它进行元素新增（insert）操作或删除（erase）操作时，操作之前的所有迭代器在操作完成之后依然有效（当然，被删除的那个元素的迭代器无效）

map的底层结构

由于RB-tree是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map是以RB-tree为底层机制
又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map操作行为，都只是转调用RB-tree的操作行为而已
下面是map的结构：

map源码

下面是map的源代码摘录

//代码摘录与stl_map.h
template <class _Key, class _Tp, class _Compare, class _Alloc>
class map {
public:


// requirements:


__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);


// typedefs:


typedef _Key                  key_type;  //键值类型
typedef _Tp                   data_type; //数据（实值）类型
typedef _Tp                   mapped_type;
typedef pair<const _Key, _Tp> value_type; //元素类型（键值/实值）
typedef _Compare              key_compare; //键值比较函数


//以下定义一个functor，作用就是调用“元素比较函数”
class value_compare
: public binary_function<value_type, value_type, bool> {
friend class map<_Key,_Tp,_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:
//以下定义表述类型。以map元素类型（一个pair）的第一类型，作为RB-tree节点的键值类型
typedef _Rb_tree<key_type, value_type,
_Select1st<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t;  // 以红黑树实现map
public:
typedef typename _Rep_type::pointer pointer;
typedef typename _Rep_type::const_pointer const_pointer;
typedef typename _Rep_type::reference reference;
typedef typename _Rep_type::const_reference const_reference;
typedef typename _Rep_type::iterator iterator;
//注意上面一行，map不像set，map使用的是RB-tree的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;
typedef typename _Rep_type::allocator_type allocator_type;


//注意，map一定使用底层RB-tree的insert_unique()而非insert_equal()
//multimap才使用insert_equal()
// allocation/deallocation


map() : _M_t(_Compare(), allocator_type()) {}
explicit map(const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) {}


#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
map(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }


template <class _InputIterator>
map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
#else
map(const value_type* __first, const value_type* __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }


map(const value_type* __first,
const value_type* __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }


map(const_iterator __first, const_iterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }


map(const_iterator __first, const_iterator __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }


#endif /* __STL_MEMBER_TEMPLATES */


map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
map<_Key,_Tp,_Compare,_Alloc>&
operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
{
_M_t = __x._M_t;
return *this;
}


//以下所有mao操作，RB-tree都已提供，mao只要调用即可
// accessors:


key_compare key_comp() const { return _M_t.key_comp(); }
value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
allocator_type get_allocator() const { return _M_t.get_allocator(); }


iterator begin() { return _M_t.begin(); }
const_iterator begin() const { return _M_t.begin(); }
iterator end() { return _M_t.end(); }
const_iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() { return _M_t.rbegin(); }
const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
reverse_iterator rend() { return _M_t.rend(); }
const_reverse_iterator rend() const { return _M_t.rend(); }
bool empty() const { return _M_t.empty(); }
size_type size() const { return _M_t.size(); }
size_type max_size() const { return _M_t.max_size(); }
_Tp& operator[](const key_type& __k) {
iterator __i = lower_bound(__k);
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first))
__i = insert(__i, value_type(__k, _Tp()));
return (*__i).second;
}
void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }


// insert/erase


pair<iterator,bool> insert(const value_type& __x)
{ return _M_t.insert_unique(__x); }
iterator insert(iterator position, const value_type& __x)
{ return _M_t.insert_unique(position, __x); }
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last) {
_M_t.insert_unique(__first, __last);
}
#else
void insert(const value_type* __first, const value_type* __last) {
_M_t.insert_unique(__first, __last);
}
void insert(const_iterator __first, const_iterator __last) {
_M_t.insert_unique(__first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */


void erase(iterator __position) { _M_t.erase(__position); }
size_type erase(const key_type& __x) { return _M_t.erase(__x); }
void erase(iterator __first, iterator __last)
{ _M_t.erase(__first, __last); }
void clear() { _M_t.clear(); }


// map operations:


iterator find(const key_type& __x) { return _M_t.find(__x); }
const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
size_type count(const key_type& __x) const {
return _M_t.find(__x) == _M_t.end() ? 0 : 1;
}
iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
const_iterator lower_bound(const key_type& __x) const {
return _M_t.lower_bound(__x);
}
iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
const_iterator upper_bound(const key_type& __x) const {
return _M_t.upper_bound(__x);
}


pair<iterator,iterator> equal_range(const key_type& __x) {
return _M_t.equal_range(__x);
}
pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}


#ifdef __STL_TEMPLATE_FRIENDS
template <class _K1, class _T1, class _C1, class _A1>
friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
const map<_K1, _T1, _C1, _A1>&);
template <class _K1, class _T1, class _C1, class _A1>
friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
const map<_K1, _T1, _C1, _A1>&);
#else /* __STL_TEMPLATE_FRIENDS */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
#endif /* __STL_TEMPLATE_FRIENDS */
};

insert函数：
- 返回pair类型。pair参数1位返回的元素，第2个参数为bool，表示是否插入成功。插入成功的话pair参数1才保存返回的节点元素
- 底层交给RB-tree的insert_unique去执行

pair<iterator,bool> insert(const value_type& __x){ return _M_t.insert_unique(__x); }

下标运算符（[]）：
- 左值运用：内容可被修改
- 右值运用：内容不可被修改

map<std::string, int> simap;
simap[std::string("dongshao")] = 1;         //左值运用
int number = simap[std::string("dongshao")];//右值运用

下标运算符的定义如下

map的使用案例

#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;


int main()
{
map<std::string, int> simap;
simap[std::string("jjhou")] = 1;
simap[std::string("jerry")] = 2;
simap[std::string("jason")] = 3;
simap[std::string("jimmy")] = 4;


std::pair<std::string, int> value(std::string("david"), 5);
simap.insert(value);


map<std::string, int>::iterator simap_iter = simap.begin();
for (; simap_iter != simap.end(); simap_iter++)
std::cout << simap_iter->first << ": " << simap_iter->second << std::endl;
std::cout << std::endl;


int number = simap[std::string("jjhou")];
std::cout << number << std::endl << std::endl;




map<std::string, int>::iterator iter;
iter = simap.find(std::string("mchen"));
if (iter != simap.end())
std::cout << "mchen found" << std::endl;
else
std::cout << "mchen not found" << std::endl;
iter = simap.find(std::string("jerry"));
if (iter != simap.end())
std::cout << "jerry found" << std::endl;
else
std::cout << "jerry not found" << std::endl;
std::cout << std::endl;


iter->second = 9;
int number2 = simap[std::string("jerry")];
std::cout << number2 << std::endl;
return 0;
}