STL(标准模板库)笔记---平衡二叉树multiset

本系列是观看北大郭炜老师程序与算法课程的笔记，用于复习与巩固。

STL中的平衡二叉树数据结构

• 有时需要在大量增加、删除数据的同时， 还要进行大量数据的查找
• 希望增加数据、删除数据、查找数据都能在 log(n)复杂度完成
• 排序+二分查找显然不可以，因加入新数据就要重新排序
• 可以使用“平衡二叉树”数据结构存放数据，体现在STL中，就是以 下四种“排序容器” ：
  multiset、set、multimap、map

multiset

1. multiset 用法

multiset< T > st

• 定义了一个multiset变量st，st里面可以存放T类型的数据，并且能自 动排序。开始st为空
• 排序规则：表达式 “a < b” 为true，则 a 排在 b 前面
• 可用 st.insert添加元素，st.find查找元素，st.erase删除元素，复杂度 都是 log(n)

#include <iostream> 
#include <cstring> 
#include <set> //使用multiset和set需要此头文件 
using namespace std; 
int main() 
{ 
	multiset<int> st; 
	int a[10]={1,14,12,13,7,13,21,19,8,8 }; 
	for(int i = 0;i < 10; ++i) 
		st.insert(a[i]); //插入的是a [i]的复制品
	multiset<int>::iterator i; //迭代器，近似于指针 
	for(i = st.begin(); i != st.end(); ++i) 
		cout << * i << ","; cout << endl; 
		
//输出：1,7,8,8,12,13,13,14,19,21

i = st.find(22); //查找22，返回值是迭代器 
if( i == st.end())  //找不到则返回值为 
	end() cout << "not found" << endl; 
st.insert(22);  //插入 22 
i = st.find(22); 
if( i == st.end()) 
	cout << "not found" << endl; 
else 
	cout << "found:" << *i <<endl; 
//找到则返回指向找到的元素的迭代器

//输出：
//		not found 
//		found:22

i = st.lower_bound(13); 
//返回最靠后的迭代器 it，使得[begin(),it)中的元素 
//都在 13 前面 ，复杂度 log(n) 
cout << * i << endl; 
i = st.upper_bound(8); 
//返回最靠前的迭代器 it，使得[it,end())中的元素 
//都在 8 后面，复杂度 log(n) 
cout << * i << endl; st.erase(i); //删除迭代器 i 指向的元素，即12 
for(i = st.begin(); i != st.end(); ++i) 
	cout << * i << ","; return 0; 
}

//输出：
//13
//12
//1,7,8,8,13,13,14,19,21,22

2. multiset 上的迭代器

multiset< T >::iterator p

• p是迭代器，相当于指针，可用于指向multiset中的元素。访问multiset中的元素要通 过迭代器
• 与指针的不同：
  multiset上的迭代器可 ++ ，--， 用 != 和 == 比较，不可比大小，不可加减整数，不可相减

3. 自定义排序规则的multiset 用法

#include <iostream> 
#include <cstring> 
#include <set> 
using namespace std; 
struct Rule1 { 
	bool operator()( const int & a,const int & b) const {
		 return (a%10) < (b%10); 
	}//返回值为true则说明a必须排在b前面 
}; 
int main()  { 
	multiset<int,greater<int> > st; //排序规则为从大到小 
	int a[10]={1,14,12,13,7,13,21,19,8,8 }; 
	for(int i = 0;i < 10; ++i) 
		st.insert(a[i]); 
	multiset<int,greater<int> >::iterator i;  
	for(i = st.begin(); i != st.end(); ++i) 
		cout << * i << ","; 
	cout << endl;
//输出： 21,19,14,13,13,12,8,8,7,1,

	multiset<int,Rule1 > st2; //st2的元素排序规则为：个位数小的排前面 
	for(int i = 0;i < 10; ++i) 
		st2.insert(a[i]); 
	multiset<int,Rule1>::iterator p; 
	for(p = st2.begin(); p != st2.end(); ++p) 
		cout << * p << ","; 
	cout << endl; 
	p = st2.find(133); 
	cout << * p << endl;
	return 0;
} 
//输出： 1,21,12,13,13,14,7,8,8,19, 13 

	multiset<int,Rule1 > st2; 
	//st2的元素排序规则为：个位数小的排前面 
	for(int i = 0;i < 10; ++i) 
		st2.insert(a[i]); 
	multiset<int,Rule1>::iterator p; 
	for(p = st2.begin(); p != st2.end(); ++p) 
		cout << * p << ","; 
	cout << endl; 
	p = st2.find(133); 
	cout << * p << endl;
	return 0;
} 
//输出： 1,21,12,13,13,14,7,8,8,19, 13 

find(x): 在排序容器中找一个元素y，使得 “x必须排在y前面”和 “y必须排在x前面” 都不成立

int main() 
{ 
	multiset<Student,Rule> st; 
	for(int i = 0;i < 5;++i) 
		st.insert(students[i]); //插入的是students[i]的复制品 
	multiset<Student,Rule>::iterator p; 
	for(p = st.begin(); p != st.end(); ++p) 
		cout << p->score <<" "<<p->name<<" " << p->id <<endl; 
	Student s = { "Mary",1000,85}; 
	p = st.find(s); 
	if( p!= st.end()) 
	cout << p->score <<" "<< p->name<<" " << p->id <<endl; 
return 0; 
} 
/*
92 Ala 333 
85 Mary 102 
78 Cindy 102 
78 Jack 112 
70 Zero 101 
85 Mary 102
*/