第十一周(笔记)
11.3 11.4 STL中的平衡二叉树数据结构
- 有时需要在大量增加、删除数据的的同时,还要进行大量数据的查找,希望增加数据、删除数据、查找数据都能在log(n)复杂度完成
- 排序+二分查找显然不可以,因加入新数据就要重新排序
- 可以使用“平衡二叉树”数据结构存放数据,体现在STL中,就是以下四种“排序容器”:multiset,set,multimap,map
- 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>
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]);
}
multiset <int>::iterator i;
for (i = st.begin(); i!=st.end();i++) {
cout << *i << ",";
}
cout << endl;
i = st.find(22);
if (i == st.end())
cout << "not found" << endl;
st.insert(22);
i = st.find(22);
if (i == st.end())
cout << "not found" << endl;
else
cout << "found: " << * i << endl;
i = st.lower_bound(13);
cout << *i << endl;
i = st.upper_bound(8);
cout << * i << endl;
st.erase(i);
for (i = st.begin();i!=st.end();i++)
cout << *i << ",";
return 0;
}
- 自定义排序规则的multiset
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
struct Student {
char name[20];
int id;
int score;
};
Student students[] = {
{"Jack",112,78},
{"Mary",102,85},
{"Ala",333,92},
{"Zero",101,70},
{"Cindy",102,78}
};
struct Rule {
bool operator() (const Student & s1,const Student & s2) const {
if (s1.score != s2.score)
return s1.score > s2.score;
else
return (strcmp(s1.name,s2.name) < 0);
}
};
int main()
{
multiset <Student,Rule> st;
for (int i = 0;i<5;i++)
st.insert(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;
}
11.5 set
- set的用法
- set 和 multiset的区别在于容器里不能有重复的元素
- a和b重复 等价于 ”a必须排在b的前面“和 ”b必须排在a的前面“都不成立
- set插入元素可能不成功
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
int main()
{
set <int> st;
int a[10] = {1,2,3,8,7,7,5,6,8,12};
for (int i = 0;i<10;i++) {
st.insert(a[i]);
}
cout << st.size() << endl;
set <int> ::iterator i;
for (i = st.begin();i!=st.end();i++)
cout << * i << ",";
cout << endl;
pair<set<int>::iterator,bool> result = st.insert(2);
if (!result.second)
cout << * result.first << " already exists." << endl;
else
cout << * result.first << " inserted." << endl;
return 0;
}
|