std::map源码分析

默认构造的时候 初始化：

	void _Init()
		{	// create head/nil node and make tree empty
		_Myhead = _Buynode();
		_Isnil(_Myhead) = true;
		_Root() = _Myhead;
		_Lmost() = _Myhead, _Rmost() = _Myhead;
		_Mysize = 0;
		}

首先会分配头结点的内存：

	_Nodeptr _Buynode()
		{	// allocate a head/nil node
		_Nodeptr _Wherenode = this->_Alnod.allocate(1);
		int _Linkcnt = 0;


		_TRY_BEGIN
		this->_Alptr.construct(&_Left(_Wherenode), 0);
		++_Linkcnt;
		this->_Alptr.construct(&_Parent(_Wherenode), 0);
		++_Linkcnt;
		this->_Alptr.construct(&_Right(_Wherenode), 0);
		_CATCH_ALL
		if (1 < _Linkcnt)
			this->_Alptr.destroy(&_Parent(_Wherenode));
		if (0 < _Linkcnt)
			this->_Alptr.destroy(&_Left(_Wherenode));
		this->_Alnod.deallocate(_Wherenode, 1);
		_RERAISE;
		_CATCH_END
		_Color(_Wherenode) = _Black;
		_Isnil(_Wherenode) = false;
		return (_Wherenode);
		}

然后设置颜色为black；设置根节点和最左、最右节点。

2、operator[]操作的时候：

	mapped_type& operator[](const key_type& _Keyval)
		{	// find element matching _Keyval or insert with default mapped
		iterator _Where = this->lower_bound(_Keyval);
		if (_Where == this->end()
			|| this->comp(_Keyval, this->_Key(_Where._Mynode())))
			_Where = this->insert(_Where,
				value_type(_Keyval, mapped_type()));
		return ((*_Where).second);
		}

第一次插入的，时候lower_bound返回头结点，因为tree是空；

_Where == this->end()为真，执行

_Where = this->insert(_Where,
value_type(_Keyval, mapped_type()));

之后会执行：

	iterator insert(const_iterator _Where,
		const value_type& _Val)
		{	// try to insert node with value _Val using _Where as a hint

 #if _HAS_ITERATOR_DEBUGGING
		if (_Where._Mycont != this)
			_DEBUG_ERROR("map/set insert iterator outside range");
 #endif /* _HAS_ITERATOR_DEBUGGING */

		const_iterator _Next;

		if (size() == 0)
			return (_Insert(true, _Myhead, _Val));	// insert into empty tree
		else if (this->_Multi)
			{	// insert even if duplicate
			if (_Where == begin())
				{	// insert at beginning if before first element
				if (!_DEBUG_LT_PRED(this->comp,
					_Key(_Where._Mynode()), this->_Kfn(_Val)))
					return (_Insert(true, _Where._Mynode(), _Val));
				}
			else if (_Where == end())
				{	// insert at end if after last element
				if (!_DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val), _Key(_Rmost())))
					return (_Insert(false, _Rmost(), _Val));
				}
			else if (!_DEBUG_LT_PRED(this->comp,
				_Key(_Where._Mynode()), this->_Kfn(_Val))
				&& !_DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val), _Key((--(_Next = _Where))._Mynode())))
				{	// insert before _Where
				if (_Isnil(_Right(_Next._Mynode())))
					return (_Insert(false, _Next._Mynode(), _Val));
				else
					return (_Insert(true, _Where._Mynode(), _Val));
				}
			else if (!_DEBUG_LT_PRED(this->comp,
				this->_Kfn(_Val), _Key(_Where._Mynode()))
				&& (++(_Next = _Where) == end()
					|| !_DEBUG_LT_PRED(this->comp,
						_Key(_Next._Mynode()), this->_Kfn(_Val))))
				{	// insert after _Where
				if (_Isnil(_Right(_Where._Mynode())))
					return (_Insert(false, _Where._Mynode(), _Val));
				else
					return (_Insert(true, _Next._Mynode(), _Val));
				}
			}
		else
			{	// insert only if unique
			if (_Where == begin())
				{	// insert at beginning if before first element
				if (_DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val), _Key(_Where._Mynode())))
					return (_Insert(true, _Where._Mynode(), _Val));
				}
			else if (_Where == end())
				{	// insert at end if after last element
				if (_DEBUG_LT_PRED(this->comp,
					_Key(_Rmost()), this->_Kfn(_Val)))
					return (_Insert(false, _Rmost(), _Val));
				}
			else if (_DEBUG_LT_PRED(this->comp,
				this->_Kfn(_Val), _Key(_Where._Mynode()))
				&& _DEBUG_LT_PRED(this->comp,
					_Key((--(_Next = _Where))._Mynode()), this->_Kfn(_Val)))
				{	// insert before _Where
				if (_Isnil(_Right(_Next._Mynode())))
					return (_Insert(false, _Next._Mynode(), _Val));
				else
					return (_Insert(true, _Where._Mynode(), _Val));
				}
			else if (_DEBUG_LT_PRED(this->comp,
				_Key(_Where._Mynode()), this->_Kfn(_Val))
				&& (++(_Next = _Where) == end()
					|| _DEBUG_LT_PRED(this->comp,
						this->_Kfn(_Val), _Key(_Next._Mynode()))))
				{	// insert after _Where
				if (_Isnil(_Right(_Where._Mynode())))
					return (_Insert(false, _Where._Mynode(), _Val));
				else
					return (_Insert(true, _Next._Mynode(), _Val));
				}
			}

		return (insert(_Val).first);	// try usual insert if all else fails
		}

因为if (size() == 0)为真

所以

	iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
		const value_type& _Val)
		{	// add node with value next to _Wherenode, to left if _Addnode
		if (max_size() - 1 <= _Mysize)
			_THROW(length_error, "map/set<T> too long");
		_Nodeptr _Newnode = _Buynode(_Myhead, _Wherenode, _Myhead,
			_Val, _Red);

		++_Mysize;
		if (_Wherenode == _Myhead)
			{	// first node in tree, just set head values
			_Root() = _Newnode;
			_Lmost() = _Newnode, _Rmost() = _Newnode;
			}
		else if (_Addleft)
			{	// add to left of _Wherenode
			_Left(_Wherenode) = _Newnode;
			if (_Wherenode == _Lmost())
				_Lmost() = _Newnode;
			}
		else
			{	// add to right of _Wherenode
			_Right(_Wherenode) = _Newnode;
			if (_Wherenode == _Rmost())
				_Rmost() = _Newnode;
			}

		for (_Nodeptr _Pnode = _Newnode; _Color(_Parent(_Pnode)) == _Red; )
			if (_Parent(_Pnode) == _Left(_Parent(_Parent(_Pnode))))
				{	// fixup red-red in left subtree
				_Wherenode = _Right(_Parent(_Parent(_Pnode)));
				if (_Color(_Wherenode) == _Red)
					{	// parent has two red children, blacken both
					_Color(_Parent(_Pnode)) = _Black;
					_Color(_Wherenode) = _Black;
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Pnode = _Parent(_Parent(_Pnode));
					}
				else
					{	// parent has red and black children
					if (_Pnode == _Right(_Parent(_Pnode)))
						{	// rotate right child to left
						_Pnode = _Parent(_Pnode);
						_Lrotate(_Pnode);
						}
					_Color(_Parent(_Pnode)) = _Black;	// propagate red up
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Rrotate(_Parent(_Parent(_Pnode)));
					}
				}
			else
				{	// fixup red-red in right subtree
				_Wherenode = _Left(_Parent(_Parent(_Pnode)));
				if (_Color(_Wherenode) == _Red)
					{	// parent has two red children, blacken both
					_Color(_Parent(_Pnode)) = _Black;
					_Color(_Wherenode) = _Black;
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Pnode = _Parent(_Parent(_Pnode));
					}
				else
					{	// parent has red and black children
					if (_Pnode == _Left(_Parent(_Pnode)))
						{	// rotate left child to right
						_Pnode = _Parent(_Pnode);
						_Rrotate(_Pnode);
						}
					_Color(_Parent(_Pnode)) = _Black;	// propagate red up
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Lrotate(_Parent(_Parent(_Pnode)));
					}
				}

		_Color(_Root()) = _Black;	// root is always black
		return (_TREE_ITERATOR(_Newnode));
		}

直接插进去了。

[]操作类似一个find操作，如果没有，就分配一个node放在正确的位置，分配颜色， 然后把迭代器的第二个值引用返回，然后再设置。

如果存在，就修改呗。擦擦擦，就是酱紫。

2、如果这样insert的时候：

    MyMap testMap;
    testMap.insert(std::make_pair(1,2));
    testMap.insert(std::make_pair(1,4));

第二次就会失败，因为它会先查找到应该插入的地方的上一个节点，如果key相等，就return (_Pairib(_Where, false));

所以不会插入滴。好吧，昨天被同事指出这段代码的问题，今天终于把代码看了下！！