与STL、算法初识_stl algoriph

与STL初识

STL基本概念：

全称：Standard Template Library ，标准模板库，从广义上分为容器（contanier），算法(algoriyhm)，迭代器（iterator）。

*以下会对string（字符串类型），stack（栈），queue（队列），priority_queue（优先队列），vector（动态数组），unique（去重），set和multiset，map和multimap，生成队列进行总结学习。 *

string

string类主要进行对字符串对象的操作（初始化，字符串复制、比较、连接，查询字符串长度，判断字符串是否为空，访问字符串中的单个字符）

#include<iostream>
#include<string>//使用string类必须包含<string>头文件！！！！

using namespace std
int main()
{
	string s1="hello world";//对s1对象进行初始化（常用形式）
	
	string s2;
	s2=s1;//将s1复制到s2

	string s3="Hello";
	s3>s2?cout<<"s3大"<<endl:cout<<"s2大"<<endl;//s2与s3进行比较，字符串的大小关系依据字典顺序定义，且区分大小写（小写字母>大写字母）

	string s4=" world";
	s3+=s4;//string对象可以用'+'、'+='进行拼接，会将s4的内容追加到s3的后面

	cout<<s4.size()<<endl;//可返回字符串长度

	if(!s3.empty())
		cout<<s3<<endl;//empty()，如果对象为空返回1，如果对象不为空则返回0

	for(int i = 0;i < s4.size();i++)
		cout<<s4[i]<<" ";//可以通过下标访问字符串中的指定位置的字符，对象的下标范围从0到s4.size()-1
}
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

getline()函数
语法：getline(is , s);
注意：

1. 两个参数：输入流对象，存放读入字符串的对象。
2. 直接使用string，如果输入的字符串中有空格将无法完全读入，因为string遇空格或换行会结束输入；而getline()只有遇换行时才会结束读入。

stack-栈

栈中的数据遵从后进先出的原则

#include<bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);

	stack<int>s;//定义：stack<数据类型>对象名
	s.push(1);//向栈内压入一个元素
	s.push(2);//向栈内压入一个元素
	s.push(3);//向栈内压入一个元素
	cout << "Top: " << s.top() << endl;//s.top()函数返回栈顶元素值 因为元素遵从后进先出的原则 此时栈顶是3
	cout << "Size: " << s.size() << endl;//s.size()函数返回栈内元素个数
	s.pop();//s.pop()函数移除栈顶元素
	cout << "移除后Top: " << s.top() << endl;//3已经被移除，剩余元素继续遵从后进先出的原则 此时栈顶是2
	cout << "Size: " << s.size() << endl;
	
	if (s.empty()) //与string中empty()函数类似
		cout << "Is empty" << endl;
	else
		cout << "Is not empty" << endl; 
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

queue-队列

队列是一种先进先出的数据结构，从尾端进入，从顶端取出！

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    queue<int>s;//定义：queue<数据类型>对象名

	//s.push()函数 将元素置入队列中
    s.push(1);//将1置入队列中
    s.push(2);//将2置入队列中
    s.push(3);//将3置入队列中

    cout << "Front: " << s.front() << endl;//s.front()函数 返回队列中第一个元素
    cout << "Back: " << s.back() << endl;//s.back()函数 返回队列中最后一个元素

    s.pop();//移除队列中第一个元素

    cout << "Size: " << s.size() << endl;
    cout << "Front: " << s.front() << endl;
    cout << "Back: " << s.back() << endl;

    return 0;
}

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

另：

1. queue中也有empty()函数，作用效果和栈中的empty()函数相似
2. s.begin()为b中第一个元素的位置，s.end()为s中最后一个元素的下一个位置

vector-动态数组

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    vector<int> a;//定义vector<数据类型> 对象名

    for (int i = 0; i < 5; i++)
    {
        a.push_back(5 - i);//尾插法，将元素插入到数组的末端
    }

    cout << "Size: " << a.size() << endl;

    a.pop_back();//尾删法  将数组最尾端的元素删除

    a[0] = 1;//a[0]本来是5，这里给他赋了一个新值

    cout << "Size: " << a.size() << endl;

    for (int i = 0; i < (int)a.size(); i++)
    {
        cout << a[i] << ", " ;
    }
    cout << endl;
    return 0;
}

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

算法

sort

两种形式：
（1）sort(begin , end);//默认排序从小到大
（2）sort(begin , end ,cmp);

形式1：

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);

    int a[10];

    vector <int> b;//创建动态数组

 	for(int i=0;i<5;i++)
 	{
  		cin>>a[i];

        b.push_back(a[i]);//利用尾插法 将a[i]插入到动态数组b中
 	}

 	sort(a,a+5);//sort(a+i,a+j);从下标为i的元素到下标j-1的元素进行排序

 	sort(b.begin(),b.end());//b.begin()为b中第一个元素的位置，b.end()为b中最后一个元素的下一个位置

 	for(int i=0;i<5;i++)
  		cout<<a[i]<<" ";

    cout<<endl;

 	for(int i=0;i<5;i++)
  		cout<<b[i]<<" ";

 	return 0;

}
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

形式二：

#include<bits/stdc++.h>
using namespace std;
struct sd
{
  int x;
  int y
  
}a[123461];

bool cmp(sd a,sd b)
{
    return a.y<b.y;//a.y ，b.y表示比较大小的量，<表示排序的方式
}

int main()
{
    int m,n,t;

    while(cin>>t)
    {
        for(int i=0;i<t;i++)
            cin>>a[i].x>> a[i].y;

        sort(a,a+t,cmp);//在自定义cmp()中，【return '<' 则升序排列】【return '>' 则降序排列】

        for(int i=0;i<t;i++)
            cout<<a[i].x<<" "<< a[i].y <<endl;
    }
}

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

另：

typedef struct index
{
    int a, b;
}point;
//这段代码相当于给index起了一个别名（point）
1
2
3
4
5

priority_queue-优先队列

pop端是权值最大的值

#include<bits/stdc++.h>
#define pow2(a) ((a)*(a))//计算传入元素a^2
#define dist2(x, y) (pow2(x) + pow2(y))//计算出入的x^2+y^2

using namespace std;

struct coord
{
    int x, y;
	
	//重载'<' 认为比较标准为下x，y两数平方和的大小
    const bool operator<(const coord &b)const
    {
        return (dist2(x, y) < dist2(b.x, b.y));
    }
};
int main()
{
    priority_queue<coord> s;//定义：priority_queue<数据类型> 对象名

    coord a;//实例化对象
    
    a.x = 3, a.y = 2;
    s.push(a);//将（3，2）放入优先队列
    
    a.x = 1, a.y = 2;
    s.push(a);//将（，2）放入优先队列

    a.x = 2, a.y = 2;
    s.push(a);//将（2，2）放入优先队列

    cout << "Size: " << s.size() << endl;

    cout << "Top: " << s.top().x << ", " << s.top().y << endl;//访问优先队列顶端元素

    s.pop();//删除优先队列顶端元素

    cout << "Top: " << s.top().x << ", " << s.top().y << endl;

    return 0;
}

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

unique-去重

作用：去除容器或数组中相邻元素的重复出现的元素！
注意事项：
1.去除不是真正意义上的删除，而是将重复的元素放到容器和数组的末尾，然后返回去重之后最后一个 元素的地址
2.unique针对是相邻元素，若数组或容器无序，先用sort排序以后再去重

有两种形式：
形式一(默认形式)：

iterator unique(iterator it_1,iterator it_2);

其中这两个参数表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> a = {1,3,3,4,5,6,6,7};//若未排序，需要先用sort排序

	//得到unique的起始和终止位置
    vector<int>::iterator it_1 = a.begin();
    vector<int>::iterator it_2 = a.end();
    
    cout<<"去重前的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i];
    cout<<endl;

    unique(it_1,it_2);//对[it_1,it_2)范围内进行去重
    
    cout<<"去重后的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i];
    cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

可看出并没有进行删除

形式二：

iterator unique(iterator it_1,iterator it_2,bool MyFunc);

bool MyFunc()的作用是自定义如何才算相等的元素

#include<bits/stdc++.h>
using namespace std;

static bool myfunc(int i, int j)
{
    return (i + 1) == j;//自定义认为，只有i+1==j时 才达到去重要求，即”3和4相等的”，“4和5是相等的”，“5和6是相等的”
}
int main()
{

    vector<int> a = {1,3,3,4,5,6,6,7};
    vector<int>::iterator it_1 = a.begin();
    vector<int>::iterator it_2 = a.end();

    cout<<"去重前的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i];
    cout<<endl;

    unique(it_1,it_2,myfunc);//三个参数是自定义了相等的条件

    cout<<"去重后的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i];
    cout<<endl;
}

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

生成排列

需要头文件: #include <algorithm>

bool next_permutation(begin, end);
改变区间内元素的顺序，产生下一个排列。

bool prev_permutation(begin, end);
产生前一个排列。

end为最后一个元素的下一个位置。

upper_bound 和 lower_bound

先sort排序

upper_bound(begin, end, value);
返回>value的元素的第一个位置。

lower_bound(begin, end, value);
返回>=value的元素的第一个位置。

num[] = {1,2,2,3,4,5};
lower_bound(num, num + 6, 2)为num + 1 //找到元素2的下界
upper_bound(num, num + 6, 2)为num + 3 //找到元素2的上界

set 和 multiset

头文件: #include <set>

set 和 multiset会根据特定的排序准则，自动将元素排序

区别：
1.set 不允许元素重复
2.ultiset允许元素重复

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    
    set<string>s1;//set<数据类型> 对象名
    
    set<string>::iterator iter1;//设置一个新的迭代器
    
    s1.insert("abc");//安插一个副本，返回新元素的位置
    s1.insert("abc");//安插一个副本，返回新元素的位置
    s1.insert("abc");//安插一个副本，返回新元素的位置
    s1.insert("bca");//安插一个副本，返回新元素的位置
    s1.insert("aaa");//安插一个副本，返回新元素的位置
    
    cout << "ITERATE:" << endl;
    for (iter1 = s1.begin(); iter1 != s1.end(); iter1++)
    {
        cout << (*iter1) << endl;
    }//遍历容器
    
    cout << "FIND:" << endl;
    iter1 = s1.find("abc");
    
    if(iter1 != s1.end()) 
    {
        cout << *iter1 << endl;
    }
    else
    {
        cout << "NOT FOUND" << endl;
    }
    return 0;
}

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

另：
1.s.erase(elem) – 移除与elem元素相等的所有元素，返回被移除 的元素个数。
2.s.erase(pos) – 移除迭代器pos所指位置上的元素，无返回值。
3.s.clear() – 移除全部元素，将整个容器清空。
4.s.size() – 返回容器大小。
5.s.empty() – 返回容器是否为空。
6.s.count(elem) – 返回元素值为elem的元素的个数。
7.s.lower_bound(elem) – 返回 元素值>= elem的第一个元素位置。
8.s.upper_bound(elem) – 返回元素值 > elem的第一个元素的位置。
以上位置均为一个迭代器。
9.s.begin() – 返回一个双向迭代器，指向第一个元素。
10.s.end() – 返回一个双向迭代器，指向最后一个元素的下一个位置

map和multimap

头文件: #include <map>

所有元素都会根据元素的键值自动排序，map的所有元素都是pair，pair的第一个元素被视为键值，第二个元素为实值。

注意事项：
1.map不允许两个元素有相同的键值。
2.multimap允许两个元素有相同的键值。

另：
1.m.count(key) 返回键值等于key的元素的个数
2.m.lower_bound(key) 返回键值等于key的元素的第一个可安插 的位置
3.m.upper_bound(key) 返回键值等于key的元素的最后一个可安 插的位置