学步园

set和map都是继承 _Tree。而红黑树的修改操作需要频繁地进行比较操作，_Tree的设计将比较函数放在了模板列表中，使用trait技术，可以说最大限度的增加了自由度。

基于trait技术

_Tree容器中元素的比较操作调用trait中的comp成员对象，comp是一个仿函数对象：具体可参见_Tree::insert函数：

_Pairib insert(const value_type& _Val)<br /> { // try to insert node with value _Val<br /> _Nodeptr _Trynode = _Root();<br /> _Nodeptr _Wherenode = _Myhead;<br /> bool _Addleft = true; // add to left of head if tree empty<br /> while (!_Isnil(_Trynode))<br /> { // look for leaf to insert before (_Addleft) or after<br /> _Wherenode = _Trynode;<br /> _Addleft = _DEBUG_LT_PRED(this->comp,<br /> this->_Kfn(_Val), _Key(_Trynode));<br /> _Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode);<br /> }<br /> if (this->_Multi)<br /> return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));<br /> else<br /> { // insert only if unique<br /> iterator _Where = _TREE_ITERATOR(_Wherenode);<br /> if (!_Addleft)<br /> ; // need to test if insert after is okay<br /> else if (_Where == begin())<br /> return (_Pairib(_Insert(true, _Wherenode, _Val), true));<br /> else<br /> --_Where; // need to test if insert before is okay<br /> if (_DEBUG_LT_PRED(this->comp,<br /> _Key(_Where._Mynode()), this->_Kfn(_Val)))<br /> return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));<br /> else<br /> return (_Pairib(_Where, false));<br /> }<br /> } 其中的_DEBUG_LT_PRED宏使用了comp仿函数对象去比较。

{multi}map和set都是基于_Tree，它们各自有trait的实现，set的trait叫_Tset_traits，map的trait叫_Tmap_traits，它们出了一些typename类型的定义，还有一个共同点，定义了仿函数成员对象：_Pr comp; // the comparator predicate for keys。

因为trait中有一个仿函数对象，所以set和map的构造函数中都支持传递比较仿函数对象参数。

仿函数的使用

给比较函数提供了更大的自由度，仿函数较函数指针最大好处它可以持有自己的局部状态local state。

传统比较函数只和两个被比较的元素有关，但是有时候元素间的比较需要第三个参数的参与，比如float间比较需要一个阈值。

struct my_greater<br /> : public binary_function<float, float, bool><br /> { // functor for operator>=<br /> bool operator()(const float& _Left, const float& _Right) const<br /> { // apply operator>= to operands<br /> return (_Left - _Right >= threshold);<br /> }<br /> float threshold;<br /> }; 

测试代码：

void testInsertStatus(bool b)<br /> {<br /> if(b)<br /> cout << "Insert success!!!!!!!!!!!!!!!!/n";<br /> else<br /> cout << "The item already exists!!!!!!/n";<br /> }<br /> // Test program<br /> int main( )<br /> {<br /> typedef set<float, my_greater> SetType;<br /> typedef SetType::iterator SetIter;<br /> pair<SetIter, bool> insertRet;<br /> my_greater compare;<br /> compare.threshold = 1.0f;<br /> SetType mySet1(compare);<br /> insertRet = mySet1.insert(0.1f); testInsertStatus(insertRet.second);<br /> insertRet = mySet1.insert(0.2f); testInsertStatus(insertRet.second);<br /> insertRet = mySet1.insert(1.5f); testInsertStatus(insertRet.second);<br /> copy(mySet1.begin(), mySet1.end(), ostream_iterator<float>(cout, " "));<br /> cout << endl;<br /> compare.threshold = 0.05;<br /> SetType mySet2(compare);<br /> insertRet = mySet2.insert(0.1f); testInsertStatus(insertRet.second);<br /> insertRet = mySet2.insert(0.2f); testInsertStatus(insertRet.second);<br /> insertRet = mySet2.insert(1.5f); testInsertStatus(insertRet.second);<br /> copy(mySet2.begin(), mySet2.end(), ostream_iterator<float>(cout, " "));<br /> return 0;<br /> }

通过修改my_greater的阈值，构造出不同规格的set集合。

//output：

Insert success!!!!!!!!!!!!!!!!

The item already exists!!!!!!

Insert success!!!!!!!!!!!!!!!!

1.5 0.1

Insert success!!!!!!!!!!!!!!!!

Insert success!!!!!!!!!!!!!!!!

Insert success!!!!!!!!!!!!!!!!

1.5 0.2 0.1