---

layout: post

title: 侯捷STL学习（九）

date: 2017-07-21

tag: 侯捷STL

第十九节 容器rb_tree

• Red-Black tree是自平衡二叉搜索树。
  
  

• rb_tree的封装

• 清楚传入模板的参数列表；然后构建了一个虚空结点header

• KeyOfValue表示怎么从value中取出key

• identity函数(Gnu C独有)就是表示同一个数的意思
  
  

• handle-body,采用OOP的思想，构建G4.9

• 一个红黑树的大小为4个字节
  
  

• test Rb_tree

#include <set>

#include <functional>

#include <iostream>

namespace jj31

{

void test_Rb_tree()

{

	//G2.9 vs. G2.9 :

	  //rb_tree => _Rb_tree,

	  //identity<> => _Identity<>

	  //insert_unique() => _M_insert_unique()

	  //insert_equal() => _M_insert_equal()

	cout << "\ntest_Rb_tree().......... \n";

	_Rb_tree<int, int, _Identity<int>, less<int>> itree;

	cout << itree.empty() << endl;  //1

	cout << itree.size() << endl;   //0

	itree._M_insert_unique(3);

	itree._M_insert_unique(8);

	itree._M_insert_unique(5);

	itree._M_insert_unique(9);

	itree._M_insert_unique(13);

	itree._M_insert_unique(5);  //no effect, since using insert_unique().

	cout << itree.empty() << endl;  //0

	cout << itree.size() << endl;   //5

	cout << itree.count(5) << endl; //1

	itree._M_insert_equal(5);

	itree._M_insert_equal(5);

	cout << itree.size() << endl;   //7, since using insert_equal().

	cout << itree.count(5) << endl; //3

}

}

容器set,multiset

• set、multiset元素的value和key合一，value就是key.
  
  
• 容器set实现
• const_iterator实现set不能改变容器元素的值
• 使用identity表示set已经知道key和value是相同的
  
  

容器map,multimap

• map/multimap的iterator不能改变key,可以改变value
  
  
• map的结构
• pair将key和data合成value;将key设置为const，这样通过迭代器就不会改变key的值。
  
  
• select1st实现
  
  
• map容器独特的operator[]操作，可以进行插入操作
• 直接调用insert快一些