STL 初步
sort用法
sort排序区间为下标范围为[n1,n2)的元素
从小到大排序：
从大到小排序：
1
| sort(数组名+n1,数组名+n2,greater<type>());
|
自定义排序规则：
sort函数的第三个参数可以是函数对象也可以是函数指针；
1.cmp
如：
1
2
3
4
5
6
7
| bool cmp (int a,int b){
return a > b;
}
bool cmp (stu a,stu b){
return a.score > b.score;
}
sort(a,a+len;cmp);
|
2.重载
如：
1
2
3
4
5
6
7
8
9
10
11
| struct rule{
bool operator() ( const T & name1,const T & name2) const {
return name1 < name2;
}
};
struct rule {
bool operator() (const Student & s1,const Student & s2) const {
return s1.id < s2.id;
}
};
sort(a,a+len;rule());
|
stl里的二分查找算法
二分查找(一种写法)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
typedef struct x List;
struct x{
int a[10000];
int len;
}p;
int ef(List p,int find){
int left,right,mid,no=-1;
left=1;
right=p.len;
while(left<=right){
mid=(left+right)/2;
if(find<p.a[mid])
right=mid-1;
else if(find>p.a[mid])
left=mid+1;
else
return mid;
}
return no;
}
int main()
{
int num,find;
List p;
scanf("%d",&p.len);
for(int i=1;i<=p.len;i++){
scanf("%d",&p.a[i]);
}
scanf("%d",&find);
num=ef(p,find);
if(num==-1)
printf("Not found!");
else
printf("%d",p.a[num]);
return 0;
}
|
stlL提供在排好序的数组上进行二分查找的算法，查找区间为下标范围为[n1,n2)的元素
包括binary_search，lower_bound和upper_bound
注意：这里查找的规则是依据sort排序的规则而定的，所以不一定是值相等就找到
binary_search
1
| binary_search(数组名+n1，数组名+n2,值,(排序规则));
|
用upper_bound二分查找上界
1
| type * upper_bound(数组名+n1,数组名+n2,值,(排序规则));
|
返回一个指针 type * p，表示在值后面的第一个相邻元素;
用lower_bound二分查找下界
1
| type * lower_bound(数组名+n1,数组名+n2,(排序规则));
|
也返回一个指针 type* p (p可换），表示在值前面的第一个相邻元素；
应用举例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Rule {
bool operator()( const int & a1,const int & a2) const {
return a1%10 < a2%10;
}
};
void Print(int a[],int size) {
for(int i = 0;i < size;++i) {
cout << a[i] << "," ;
}
cout << endl;
}
#define NUM 7
int main()
{
int a[NUM] = { 12,5,3,5,98,21,7};
sort(a,a+NUM);
Print(a,NUM);
int * p = lower_bound(a,a+NUM,5);
cout << *p << "," << p-a << endl;
p = upper_bound(a,a+NUM,5);
cout << *p << endl;
cout << * upper_bound(a,a+NUM,13) << endl;
sort(a,a+NUM,Rule());
Print(a,NUM);
cout << * lower_bound(a,a+NUM,16,Rule()) << endl;
cout << lower_bound(a,a+NUM,25,Rule()) - a<< endl;
cout << upper_bound(a,a+NUM,18,Rule()) - a << endl;
if( upper_bound(a,a+NUM,18,Rule()) == a+NUM)
cout << "not found" << endl;
cout << * upper_bound(a,a+NUM,5,Rule()) << endl;
cout << * upper_bound(a,a+NUM,4,Rule()) << endl;
return 0;
}
|
STL中的平衡二叉树数据结构
目的是使增加数据、删除数据、查找数据都能在 log(n)复杂度完成
用到下面四种“排序容器”：multiset,set,multimap,map；
multiset
multiset用法：
定义了一个multiset变量st，st里面可以存放T类型的数据，并且能自动排序(默认a<b为true)。开始时st为空
可用 st.insert添加元素，st.find查找元素，st.erase删除元素，复杂度 都是 log(n)
举例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #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;
输出：1,7,8,8,12,13,13,14,19,21
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;
输出：
not found
found:22
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;
}
输出：
13
12
1,7,8,8,13,13,14,19,21,22
|
multiset 上的迭代器:
1
| multiset<T>::iterator p;
|
p是迭代器，相当于指针，可用于指向multiset中的元素。访问multiset中的元素要通过迭代器
与指针的不同：
multiset上的迭代器可 ++ ，—， 用 != 和 == 比较，不可比大小，不可加减整数，不可相减
st.begin() 返回值类型为 multiset::iterator, 是指向st中的头一个元素的迭代器
st.end() 返回值类型为 multiset::iterator, 是指向st中的最后一个元素后面的迭代器
对迭代器 ++ ,其就指向容器中下一个元素，— 则令其指向上一个元素
自定义排序规则的multiset 用法：
1
2
3
| multiset<int,greater<int> > st;
multiset<int,Rule1> st;
multiset<Student,Rule1>::iterator p;
|
set
学set前先了解一下pair模板的用法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| pair<T1,T2>
等价于：
struct {
T1 first;
T2 second;
};
例如：pair<int, double> a;
等价于：
struct {
int first;
double second;
} a;
a.first = 1;
a.second = 93.93;
|
注意：first和second不能更换
set和multiset的区别在于容器里不能有重复元素
这里的重复也是依据预先定义的规则才有意义
set插入元素可能不成功（重复）
set在插入时返回的result.second如果为零，表示因重复而无法插入
1
| pair<set<int>::iterator, bool> result = st.insert(2);
|
multimap
multimap容器里的元素，都是pair形式的
1
2
3
4
5
6
| multimap<T1,T2> mp
struct {
T1 first;
T2 second;
};
|
multimap中的元素按照first排序，并可以按first进行查找，默认”a.first < b.first” 为true
应用举例：
一个学生成绩录入和查询系统，接受以下两种输入:
Add name id score
Query score
name是个不超过16字符的字符串，中间没有空格，代表学生姓名。id 是个整数，代表学号。score是个整数，表示分数。学号不会重复，分数 和姓名都可能重复。
两种输入交替出现。第一种输入表示要添加一个学生的信息，碰到这 种输入，就记下学生的姓名、id和分数。第二种输入表示要查询，碰到这 种输入，就输出已有记录中分数比score低的最高分获得者的姓名、学号 和分数。如果有多个学生都满足条件，就输出学号最大的那个学生的信 息。如果找不到满足条件的学生，则输出“Nobody”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| 输入样例：
Add Jack 12 78
Query 78
Query 81
Add Percy 9 81
Add Marry 8 81
Query 82
Add Tom 11 79
Query 80
Query 81
输出样例：
Nobody
Jack 12 78
Percy 9 81
Tom 11 79
Tom 11 79
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
struct StudentInfo {
int id;
char name[20];
};
struct Student {
int score;
StudentInfo info;
};
typedef multimap<int,StudentInfo> MAP_STD;
int main()
{
MAP_STD mp;
Student st;
char cmd[20];
while( cin >> cmd ) {
if( cmd[0] == 'A') {
cin >> st.info.name >> st.info.id >> st.score ;
mp.insert(make_pair(st.score,st.info ));
}
else if( cmd[0] == 'Q' ){
int score;
cin >> score;
MAP_STD::iterator p = mp.lower_bound (score);
if( p!= mp.begin()) {
--p;
score = p->first;
MAP_STD::iterator maxp = p;
int maxId = p->second.id;
for(; p != mp.begin() && p->first == score; --p) {
if( p->second.id > maxId ) {
maxp = p;
maxId = p->second.id ;
}
}
if( p->first == score) {
if( p->second.id > maxId ) {
maxp = p;
maxId = p->second.id ;
}
}
cout << maxp->second.name << " " << maxp->second.id << " " << maxp->first << endl;
}
else cout << "Nobody" << endl;
}
}
return 0;
}
|
map
和multimap区别在于：
不能有关键字重复的元素
可以使用 [] ，下标为关键字，返回值为first和关键字相同的元素的second
当然插入元素也可能失败
[]的用法如下：
1
2
3
4
5
6
7
8
9
10
| struct Student {
string name;
int score;
};
typedef map<string,int> MP;
......
Student students[5] = {{"Jack",89},{"Tom",74},{"Cindy",87},{"Alysa",87},{"Micheal",98}};
......
cout << mp["Jack"] << endl;
mp["Jack"] = 60;
|
很实用的例子：
单词词频统计程序
输入大量单词，每个单词，一行，不超过20字符，没有空格。 按出现次数从多到少输出这些单词及其出现次数 。出现次数相同的，字典序靠前的在前面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 输入样例：
this
is
ok
this
plus
that
is
plus
plus
输出样例：
plus 3
is 2
this 2
ok 1
that 1
|
首先你要知道，大量意味着常规的二分加排序的方法必然超时，而用自定义排序规则的set和方便存储的map就可以高效解决问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;
struct Word {
int times;
string wd;
};
struct Rule {
bool operator () ( const Word & w1,const Word & w2) const {
if( w1.times != w2.times)
return w1.times > w2.times;
else
return w1.wd < w2.wd;
}
};
int main()
{
string s;
set<Word,Rule> st;
map<string,int> mp;
while( cin >> s )
++ mp[s] ;
for( map<string,int>::iterator i = mp.begin();
i != mp.end(); ++i) {
Word tmp;
tmp.wd = i->first;
tmp.times = i->second;
st.insert(tmp);
}
for(set<Word,Rule>::iterator i = st.begin();
i != st.end(); ++i)
cout << i->wd << " " << i->times << endl;
return 0;
}
|
