学步园

stl源码片段：

	_Pairib insert(const value_type& _Val)
		{	// try to insert node with value _Val
		_Nodeptr _Trynode = _Root();
		_Nodeptr _Wherenode = _Myhead;
		bool _Addleft = true;	// add to left of head if tree empty
		while (!_Isnil(_Trynode))
			{	// look for leaf to insert before (_Addleft) or after
			_Wherenode = _Trynode;
			_Addleft = this->comp(this->_Kfn(_Val), _Key(_Trynode));
			_Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode);
			}

		if (this->_Multi)
			return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
		else
			{	// insert only if unique
			iterator _Where = _TREE_ITERATOR(_Wherenode);
			if (!_Addleft)
				;	// need to test if insert after is okay
			else if (_Where == begin())
				return (_Pairib(_Insert(true, _Wherenode, _Val), true));
			else
				--_Where;	// need to test if insert before is okay

			if (this->comp(_Key(_Where._Mynode()), this->_Kfn(_Val)))
				return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
			else
				return (_Pairib(_Where, false));
			}
		}

stl中的map继承自_Tree，该片段中的变量_Myhead是一个指向Root节点的指针，该Root节点为插入的第一个元素。

依照上述语句，对于示例：

#include <iostream>
#include <map>

int main()
{
	std::map<int, int> col1;
	col1.insert(std::make_pair(2, 1));
	col1.insert(std::make_pair(1, 1));
}

执行col1.insert(std::make_pair(2, 1));进行第一次insert的时候，
会分配Root节点，该节点的_Left、_Right和_Parent都指向_Myhead，_Myhead的_Left、_Right和_Parent也都指向Root节点，
如下图所示：

执行col1.insert(std::make_pair(1, 1));进行第二次insert的时候，会根据less<int>比较操作建立Left节点，
如下图所示：