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
*/