Think World

从个人成长角度来说，从经历中学点什么总是重要的

0%

Posted on Edited on

list的底层结构

环形双向链表

List的重要性质：

  1. 插入操作(insert) 和 接合操作(splice)都不会造成原有的list失效，只有删除时，指向被删除元素的那个迭代器会失效，其他不受影响 ; 而vector的迭代器，如果插入导致原来的数组容量扩充，会造成所有的迭代器失效
  2. 不支持随机存取，下标操作和at()函数

list的相关操作

https://leetcode-cn.com/problems/lru-cache/

list的定义和构造函数

1
2
3
4
5
6
7
8
list<A> listname;
list<A> listname(size);
list<A> listname(size, value);
list<A> listname(elselist);
list<A> listname (first,last);// 

int iv[5] ={5,6,7,8,9};
list<int> ilist2(iv,iv+sizeof(iv)//sizeof(int))

list的插入和删除

list插入

1
2
3
4
5
6
void push_front(const A& x); //作为头节点
void push_back(const A& x);


iterator insert(iterator position, const A& x); //在迭代器position所指的位置之前 插入结点，内容为x,position不失效

list删除操作

1
2
3
4
5
void pop_front();
void pop_back();

iterator erase(iterator position);//只是被删除的结点迭代器失效，
void remove(const T& value); //将数值为value的所有元素都移除

list的移动和拼接操作

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
//下面拼接操作中，x中的元素也有变化

splice(iterator position,list& x); //将x拼接到position所指的位置之前，x不同于position所指的list
splice(iterator position, list& x, iterator i);// i指向 list x中的一个元素，将i接合与position之前。 i和position可以指向同一个list，swap操作

splice(iterator position, list& x ,iterator first ,iterator last);
//将 list x中的[first，last）中的元素拼接到position中

   
    // splicing lists

#include <iostream>

#include <list>

#include <string>

#include <algorithm>

using namespace std;

int main ()

{

  list<int> mylist1, mylist2;

  list<int>::iterator it;

  // set some initial values:

  for (int i=1; i<=4; i++)

     mylist1.push_back(i);      // mylist1: 1 2 3 4

  for (int i=1; i<=3; i++)

     mylist2.push_back(i*10);   // mylist2: 10 20 30

  it = mylist1.begin();

  ++it;                         // points to 2

  mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4

                                // mylist2 (empty)

                                // "it" still points to 2 (the 5th element)                                     

  mylist2.splice (mylist2.begin(),mylist1, it);
                               // mylist1: 1 10 20 30 3 4
                                // mylist2: 2
                                // "it" is now invalid.
  it = mylist1.begin();
  advance(it,3);                // "it" points now to 30
 mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                // mylist1: 30 3 4 1 10 20
}

list中的高级算法

algorithm 中常见的库函数 https://blog.csdn.net/cl939974883/article/details/104225232

merge()

tips:

0.algorithm 里的反转函数接口:reverse(first,last) 参数为容器的迭代器起始位置和终止位置1.string和vector和deque只能使用模板库算法里的反转函数
2.list可以使用算法里的和list类的reverse
3.stack和queue没有迭代器，自然不能使用算法里的reverse,其类也没有提供反转的成员函数
4.set和map的元素是按照键值排序的，不能修改键值，不可反转.
————————————————
版权声明：本文为CSDN博主「嘻嘻作者哈哈」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43971252/article/details/88566605

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
73
74
75
76
77
78
79
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
using namespace std;

int main()
{
	string str("abcde");
	reverse(str.begin(), str.end());         //string使用<algorithm>里的reverse ,string类自身没有reverse成员函数
	cout << "string elem : ";
	for (int i = 0; i < str.size(); i++)
		cout << str.at(i) << "   ";
	cout << "\n\n";

	vector<int> v{ 1,2,3,4,5,6 };
	reverse(v.begin(), v.end());            //vector使用<algorithm>里的reverse,vector类自身也没有reverse成员函数
	cout << "vector elem : ";
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
		cout << *it << "   ";
	cout << "\n\n";
	
	list<int> l{ -1,-2,-3,-4,-5,-6 };
	reverse(l.begin(), l.end());           //list使用算法里的
	cout << "list elem : ";
	for(list<int>::iterator it=l.begin();it!=l.end();it++)
		cout << *it << "   ";
	cout << "\n";
	l.reverse();                         //list使用自身类的reverse成员函数
	cout << "list elem : ";
	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
		cout << *it << "   ";
	cout << "\n\n";

	//queue和stack容器不支持遍历操作，没有迭代器，所以不能使用算法里的反转函数，其类也没有提供反转的成员函数
	queue<int> myq;
	myq.emplace(1);
	myq.push(2);
	
	stack<int> mys;
	mys.emplace(6);
	mys.push(7);

	deque<int> myd{ 2,4,6,8 };
	reverse(myd.begin(), myd.end());       //deque容器使用算法里的反转函数，deque类没有reverse成员函数
	cout << "deque elem : ";
	for (deque<int>::iterator it = myd.begin(); it != myd.end(); it++)
		cout << *it << "  ";
	cout << "\n\n";

	//因为set和map是关联式容器，在插入元素时就已经根据键值排好序了，如果反转会使元素变成无序状态，从而破会容器组织
	set<int> s;
	s.insert(10);
	s.insert(9);
	s.insert(8);
	//reverse(s.begin(), s.end());
	cout << "set elem : ";
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
		cout << *it << "  ";
	cout << "\n\n";

	map<int, string> m;
	m.insert(make_pair(0, "小王"));
	m.insert(make_pair(1, "小玲"));
	//reverse(m.begin(), m.end());
	cout << "map elem : " << "\n";
	for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
		cout << "key : " << it->first << "  value : " << it->second << endl;
	cout << "\n\n";

	system("pause");
	return 0;
}

sort

list中数据类型为基本类型，例如为整数类型排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream> 
#include <list>
using namespace std;
 
int main()
{
    list<int> num;
    num.push_back( 1 );
    num.push_back( 3 );
    num.push_back( 2 );
    num.push_back( 9 );
    num.push_back( 5 );
    num.sort();
    list<int>::iterator vi;
    for( vi=num.begin();vi!=num.end();vi++) 
    {
        cout  << *vi << endl;
    } 
    
    return 0;
}

list中的类型为自定义类型

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
#include <iostream> 
#include <list>
using namespace std;
 
 
class student
 {
    public:
      int age;
      student()
      {}
      student(int a)
      {
          this->age=a;
      }
  public:
      bool operator < (student b)
     {
           return this->age < b.age;
     }
 
     bool operator > (student b)
     {
           return this->age > b.age;
     } 
 
 }; 
 
int main()
{
    list<student> num;
    num.push_back( student(1) );
    num.push_back( student(5));
    num.push_back( student(2));
    num.push_back( student(6));
    num.sort();
   // sort(num.begin(),num.end());
    list<student>::iterator vi;
 
    for( vi=num.begin();vi!=num.end();vi++) 
    {
        cout  << vi->age << endl;
    }
    num.clear();
    
}

3、自定义规则进行排序

3.1 使用函数对象 (参考[2]）
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
#include<iostream>
#include<list>
using namespace std;
 
class A{
public:
 int a,b;
 A(int t1,int t2){a=t1,b=t2;}
};
 
 
struct node{
 bool operator()(const A& t1,const A& t2){
  return t1.a<t2.a;    //会产生升序排序,若改为>,则变为降序
 }
};
 
int main() {
 list<A> list_a;
 A a1(1,2), a2(4,6), a3(2,8);
 list_a.push_back(a1);
 list_a.push_back(a2);
 list_a.push_back(a3);
 
 list_a.sort(node()); //排序操作； 
 
 list<A>::iterator ite;
 ite=list_a.begin();
 for(int i=0;i<3;i++)  {cout<<ite->a<<endl; ite++;}
 
 return 0;
 
}
3.2 使用回调函数自定义排序规则：（参考[3]）
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
#include<iostream>
#include<list>
using namespace std;
 
class A{
public:
 int a,b;
 A(int t1,int t2){a=t1,b=t2;}
};
 
bool compare(A a1, A a2){
	return a1.a < a2.a;  //会产生升序排列，若改为>,则会产生降序； 
}
 
int main() {
 list<A> list_a;
 A a1(1,2), a2(4,6), a3(2,8);
 list_a.push_back(a1);
 list_a.push_back(a2);
 list_a.push_back(a3);
 
 list_a.sort(compare); //排序操作； 
 
 list<A>::iterator ite;
 ite=list_a.begin();
 for(int i=0;i<3;i++)  {cout<<ite->a<<endl; ite++;}
 
 return 0;
 
}

Posted on Edited on

经常使用的STL和数据结构

经典题型－－分类总结

hash_map相关

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

采用O(n)的解决方案：

思路1: set-遍历nums，对于每一个nums[i]，对外进行扩张，…num[i-1]…num[i+1]…查看是否都在数组中，直到不能扩张为止，

对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表unordered_map存储数组中数，这样查看一个数是否存在即能优化至 O(1)的时间复杂度。

同时考虑到同一连续序列向两边扩张的结果是相同的，所以我们增加一个访问标记，去重

unordered_map<int,bool> flags . flags.find(k)!＝flags.end()表明在该集合中，　flags[k]==true表明它属于某个连续的子序列中，不用要再扩张

​ 时间复杂度：O(n),　空间复杂度：O(n)

思路2：本身查找的过程类似于聚类，采用并查集，find,union..利用unordered_map<int,int> map用来存储

(参考leetcode sheet)

594.最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1

利用map存储时，按照key有序排列，map<int,int> count，　count[k]表示k在原数组中出现的次数[注意map只能利用key下标或者迭代器遍历]

如果pre_it->first == later->first-1,则可以构成和谐子序列，计算长度

二分法查找

153.寻找旋转排序数组中的最小值

154.寻找旋转排序数组中的最小值 II

33.搜索旋转排序数组

81. 搜索旋转排序数组 II

刷题心得，这类题目特点:在每个分段序列中都是有序的，前面的最小值大于(等于)后半的最小值。

实际套路题，利用二分，只需分析清楚　在每种比较条件下，应该走哪个分支　[注意下标的开闭区间]

排序(归并思路)

4. 寻找两个正序数组的中位数

Posted on Edited on

单调栈

从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈

  • 单调递增栈：(上面元素是最小元素) 单调递增栈就是从栈底到栈顶数据是从大到小
  • 单调递减栈：(上面元素是最大元素) 单调递减栈就是从栈底到栈顶数据是从小到大

应用题目1

​ 1.视野总和

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2

==转换：从后向前遍历，计算所有元素与上一个比它大的元素的间隔之和==

1
2
3



应用题目2

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入: [2,1,5,6,2,3]

输出: 10

单调栈用法：

官方给出的题解是利用单调栈计算出每个点展开左右边界，保存在了left和right中 （我自己写时，也想到这个问题，不过没有采用合适的数据结构vector,而是采用栈–自己之所以采用栈是为了配合单调栈，但其实是每个结点都需要保存他的左右边界)

如何确定左右边界

单调栈中保存从左到右遍历 递增序列的index 每个结点的左边界为栈中相邻+靠栈低的元素（从左遍历，最近的且小于该处高度的点） 单调栈保存index

结点的右边界为 右侧第一个小于当前高度的索引，所以最开始入栈时，是不确定的

确定某个左右边界的时间：
  • 右边界 当结点从单调栈中弹出时，计算它的右边界。 按照单调栈的结构，当结点遇到第一个比它高度小的结点，该结点就会被弹出。这就是它的右边界，如果遍历完数组，仍在栈中，默认右边界为n
  • 左边界 当结点压入栈中时，计算它的左边界。 左边界为当前栈顶元素，如果栈为空则是-1 再把该节点的index压入栈
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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
          int n = heights.size();
    vector<int> left(n),right(n,n);//用于保存左右边界

    stack<int> index;///用于增序排列
    for(int i=0;i<heights.size();i++){
        while(! index.empty() && heights[i]<= heights[index.top()]){
            right[index.top()] = i;//右边界可以确定了
            index.pop();
        }
        left[i]= index.empty()?-1:index.top(); //它的左边界也可以确定了
        index.push(i);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int temp =heights[i]*(right[i]-left[i]-1);
        if(ans<temp){
            ans = temp;
        }
    }
    return ans;
    }
};

​ 应用题目3

456. 132 模式

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/132-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.empty()){
            return false;
        }
        stack<int> item;
        item.push(nums[nums.size()-1]);
        int max_k = INT_MIN;
        for(int i=nums.size()-2;i>=0;i--){
            if(nums[i]<max_k){
                return true;
            }
            while(!item.empty() && item.top()<nums[i] ){
                max_k = item.top();
                item.pop();
            }
            item.push(nums[i]);
        }
        return false;
    }
};

递减栈(栈顶保存最小的元素）
回顾本题解决思路
寻找是否有132模式

从右到左进行遍历

我们希望确定3之后，2是3右侧小于3的最大的数，方便更好地判断 1是否存在。

  • 如何确定32结构

从右到左遍历
这里利用递减栈可以 保存当前值 距离 右侧第一个大于它的数 之间，最大的那个元素(保存在max_k中)
即维护递减栈过程中，更新当前pop的最大值

  • 何时确定？
    • 确定32结构:
      遍历栈时，如果有nums[i]>item.top()，更新max_k，保存最新的32结构
    • 要一开始就判断是否存在 1
      如果nums[i] <max_k ,则一定存在132模式

Posted on Edited on

线性表

总结写在前：

线性表

​ 二分，归并

题目1：

​ 给定两个已经排序好的数组，找到两者所有元素中第k大的元素

1
2


Posted on Edited on

STL常见函数模板

查找

利用二分查找的方法在一个排好序的数组中进行查找

‘upper_bound’ && ‘lower_bound’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
upper_bound(begin,end,num);
/*
对于从小到大的排序数组，upper_bound()从数组的begin位置到end-1位置二分查找第一个大于num的数字，如果找到，则返回该数组的迭代器;反之，返回end迭代器


对于从大到小的排序数组，upper_bound()从数组的begin位置到end-1位置二分查找第一个小于num的数字，如果找到，则返回该数组的迭代器;反之，返回end迭代器

*/

lower_bound(begin,end,num);
/*
对于从小到大的排序数组，upper_bound()从数组的begin位置到end-1位置二分查找第一个大于等于num的数字，如果找到，则返回该数组的迭代器;反之，返回end迭代器


对于从大到小的排序数组，upper_bound()从数组的begin位置到end-1位置二分查找第一个小于等于num的数字，如果找到，则返回该数组的迭代器;反之，返回end迭代器

*/

应用：

leetcode: Remove Duplicates from Sorted Array

删除

‘unique()’

1
2
3
unique(); //用于去除相邻的重复元素（只保留一个），使用前需要对数组进行排序.
//实际上只是把重复元素放到数组的后方
//返回，去重后最后一个元素的地址

Posted on Edited on

图论

图的存储结构

点：只关注顶点的编号，可以不存储;如果存储，可以使用线性表存储图的顶点集合(v1,v2,….vn)

边：采用邻接矩阵，邻接表，边表表示

邻接矩阵

  • 顶点表: 用一个一维数组存储图中顶点的信息，
  • 边表：用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵
1
2
3
4
5
6
7
8
#define MaxVertexNum 100
typedef char VertexType			//顶点编号的数据类型
typedef int EdgeType				//有权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum]; 										//顶点表，可以省略
	EdgeType Edge[MaxVertexNum][MaxVertexNum]; 	//边表
	int vexnum,arcnum;
} MGraph;

邻接表

用线性表存储每个顶点发出的边。定长数组A[n][d],可变长数组vector

1
2
3
4
5
6
7
8
vector<int> Grap [numP]; // 有向无权图
Grap[i].push_back(j);//增加一条边<i,j >


const int maxn =1e4+10;//最大结点数
vector<pair<int,int>> E[maxn];//有向有权图
Grap[i][j];//Grap[i]访问第i个vector,每个vector作为一个动态数组，存储若干pair对，保存边的终点和权值
//该边的起点是i，终点是E[i].first,边的权重是E[i].second.

邻接链表

对于每个顶点建立一个单链表，第i个单链表中的结点包含顶点$v_i$的所有邻接顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Node{//有权图的边顶点结构
    int index;//边的终点的下标
    int cost;//边的权重
    struct Node* link;//指向下一条弧的指针
};
struct HeadNode{//顶点
    int index;//顶点的信息
    struct Node *adjacent;//指向第一条依附该顶点的弧的指针
};

typedef struct{
	HeadNode* Grap= new HeadNode[vexnum];//创建包含10个点的图
	int vexnum;//顶点的个数
} MGraph;


邻接链表表示无向图

邻接链表 V.S. 邻接矩阵

图的遍历

最小生成树

最短路问题

对于无权图而言，可以利用广度优先搜索查找单源最短路径

对于有权图而言，可以利用Dijkstra算法计算单源最短路径，利用Floyd算法计算顶点之间的最短路

Dijkstra算法

保存的数据:

1
2
3
dist[] ;//记录从源点v0到其他顶点之间的最短路径长度

path[];//记录从源点到顶点之间最短路径的前驱结点,不是必要的

算法步骤：(默认源点为v0)

  • 初始化，集合S初始化为{0}，dist[]的初始值为 dist[i] = arcs[0][i], i=1,2,..n-1

  • 从顶点集合 V-S中选择出 $v_j$,满足$dist[j] =Min (dist[i] | v_i \in V-S )$, $ v_j$就是当前求得的，一条从v0出发的最短路径的终点

  • 修改从v0出发到集合 V-S上的任一顶点 vk可达的最短路径长度：如果dist[j]+ arcs[j][k] <dist[k] ,则更新dist[k] = sidt[j]+arcs[j][k];

  • 重复步骤 2-3,操作共n-1次，直到所有顶点都包含在S中

    图结构采用邻接链表的方式存储

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//
// Created by doriswang on 2021/2/28.
//
#include<iostream>
struct Node{
    int index;//边的终点
    int cost;//边的权重
    struct Node* link;//指向下一条弧的指针
};
struct HeadNode{
    int index;//顶点的信息
    struct Node *adjacent;//指向第一条依附该顶点的弧的指针
};
HeadNode* CreatGrap(int Pnum,int Enum){
    HeadNode* Head = new HeadNode[Pnum];
    for(int i=0;i<Enum;i++){
        int strP =0;
        int endP= 0;
        int cost;
        std::cin>>strP>>endP>>cost;//输入一条边
        Node* temp = new Node();
        temp->index=endP;
        temp->cost=cost;
        temp->link = NULL;
        if(Head[strP].adjacent==NULL){//顶点的第一条边
            Head[strP].adjacent = temp;
        }
        else{
            Node* ptr=Head[strP].adjacent;
            for(;ptr->link;ptr=ptr->link){}
            ptr->link = temp;
        }

    }
    return Head;
}

int* Dijkstra(int v,int Pnum,HeadNode* Head) {//计算各个顶点到v点的最短路径
    //输入 strP,endP,cost ; 边的起点和终点，以及边的权重，利用邻接表存储图信息
    int *pre = new int[Pnum];//保存前一个将诶点
    int *dist = new int[Pnum];
    int *s = new int[Pnum];
    for (int i = 1; i < Pnum; i++) {
        pre[i] = -1;
        dist[i] = 0x0fff;
        s[i] = 0;//数组s[i]=1,表示0-i的最短路径已经计算结束
    }
    dist[v] = 0;
    for (int j = 1; j < Pnum; j++) //计算n-1次
    {
        int mindist = 0x0fff;//循环：确定即将被访问的顶点u
        int u = 0;
        for (int i = 1; i < Pnum; i++) {
            if (dist[i] < mindist && s[i] == 0) {
                mindist = dist[i];
                u = i;
            }
        }
        s[u] = 1;
        for (Node *p = Head[u].adjacent; p; p = p->link) {
            int k = p->index;
            if (dist[u] + p->cost < dist[k]) {
                dist[k] = dist[u] + p->cost;
                pre[k] = u;
            }
        }
    }
    return pre;
}
int main(){
    int Pnum=0;//顶点个数
    int Enum=0;//边的个数
    std::cout<<"依次输入顶点的个数，边的个数，以及边的起点，终点，权重"<<std::endl;
    std::cin>> Pnum;
    std::cin>> Enum;
    HeadNode* headlist = CreatGrap(Pnum,Enum);
    int strP = 0;
    int endP =0;
    std::cout<<"输入你要计算最短路径的起点和终点"<<std::endl;
    std::cin>>strP>>endP;
    int* pre = Dijkstra(strP,Pnum,headlist);
    std::cout<<endP;
    int end=pre[endP];
    while(end!=strP){
        std::cout<<" "<<end;
        end = pre[end];
    }
    std::cout<<" "<<strP;

}

两点之间的所有最短路

队列优化的Dijkstra算法

pat1003

解法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
26
27
28
29
30
31
void AdvancedDijkstra(int s){
    fill(dis,dis+maxN,0x3fffffff);//初始化
    dis[s]=0;//保存各顶点到源点之间的距离
    priority_queue<pair<int,int>> q;//默认是大根堆
    q.push(make_pair(0,s));
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        if( vis[u]==1) continue;
        vis[u]=1;
        for(int i=0;i<E[u].size();++i){//利用u到v，更新源点到v的最短路径和cost
            int v = E[u][i].first,w =E[u][i].second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                num[v]=num[u];
                pre[v].clear();
                pre[v].push_back(u);
                MaxCost[v]=MaxCost[u]+cost[v];//更新最短路，必须更新MaxCost
                if(vis[v]==0) q.push(make_pair(-dis[v],v));
            }
            else if(dis[v]==dis[u]+w){
                pre[v].push_back(u);
                num[v]+=num[u];
                if(MaxCost[v]<MaxCost[u]+cost[v]){
                    MaxCost[v]=MaxCost[u]+cost[v];
                }
                if(vis[v]==0) q.push(make_pair(-dis[v],v));
            }
        }
    }
}

解法2：

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
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int MaxN = 510;
const int INF = 0x3fffffff;
int edge[MaxN][MaxN],dist[MaxN],num[MaxN],MaxCost[MaxN],Cost[MaxN];
bool vis[MaxN];
void Dijkstra(int s,int numP){
    num[s]=1;
    MaxCost[s]=Cost[s];
    dist[s]=0;
    for(int i=0;i<numP;i++){
        int MinDis = INF;
        int u=-1;
        for(int j=0;j<numP;j++) {
            if (MinDis > dist[j] && !vis[j]) {
                MinDis = dist[j];
                u = j;
            }
        }
        if(u==-1) {
                return;
        }
        vis[u]=true;
        for(int j=0;j<numP;j++){
            if(edge[u][j]+dist[u]<dist[j]){
                dist[j]=edge[u][j]+dist[u];
                num[j]=num[u];
                MaxCost[j]=MaxCost[u]+Cost[j];
            }
            else if(edge[u][j]+dist[u] == dist[j]){
                num[j]+=num[u];
                if(MaxCost[j]<MaxCost[u]+Cost[j]){
                    MaxCost[j]=MaxCost[u]+Cost[j];
                }
            }
        }
    }

}

Posted on Edited on

STL中map的基本用法

pair

map中存储的基本数据类型是pair,首先我们简单介绍一下pair的基本结构

pair 定义在<map.h>中，

pair是有两个变量的结构体，变量的默认权限是public，都可以访问，只是first设置为const，不能修改键值

底层实现

结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T1,class T2>
   struct pair{
       typedef T1 first_type;
       typedef T2 second_type;
       
       T1 first;
       T2 second;
       
       pair(): first(T1()) ,second(T2()){}
       
       pair(const T1& a,const T2& b): first(a) ,second(b) { }
     #ifdef	__STL_MEMBER_TEMPLATES
       template<class U1,class U2>
       pair(const pair<U1,U2>& p) :dirst(p.first),second(p.second){}
       #endif  
   }

重载

1
2
3
4
5
6
7
8
9
10
template <class T1, class T2>
inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) { 
  return x.first == y.first && x.second == y.second; 
}


template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) { 
  return x.first < y.first || (!(y.first < x.first) && x.second < y.second); 
}

成员函数 make_pair

1
2
3
4
template<class T1, classT2>
inline pair<T1,T2> make_pair(const T1& x,const T2& y){
		return pair<T1,T2>(x,y);
}

map

map存储的基本数据类型是pair,数据结构是RB-tree，可以理解为关联数组。可以使用键作为下标来获得相应的值。关联的本质在于元素的值与某个特定的键相关联。

map元素的键值是唯一的，multimap允许重复元素

map的insert必须是以pair为存储结构，当然也可以直接使用make_pair构造一个临时pair

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
map c / multimap c; //产生一个空的map或者multimap，不包含任何因素
map c(op) / multimap c(op); //以op为排序准则，产生一个空的map
map c1(c2) / multimap c1(c2) ; //产生某个map或者multimap对象的副本，所有元素均被复制

map c(beg,end) /multimap c(beg,end); //以区间(beg,end)内的元素产生一个新的map/multimap

map c(beg,end,op) / multimap c(beg,end,op) //以区间(beg,end)内的元素产生一个新的map/multimap，排序准则为op
   */

map<int,double>  m1;
map<int,double,greater<int>> m2; //降序排列
map<int,double,less<int>> m3; //升序排列

//采用插入方式，增加元素
//对应迭代器的声明
map<int ,double>::iterator itm;

增加元素

1
2
3
4
5
6
7
8
9
10
11
12
    //方式1：提前先定义好pair
	pair<string, int> p;
	p.first = "zero", p.second = 0;
	m.insert(p); 
    
    //方式2：使用make_pair方式创建临时pair对象
	m.insert(make_pair("one", 1));
	
////[key] 自动添加，参考符号重载
	m["two"]=3;
	
	std::cout<<m["three"]; //输出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
class map {
public:
	...
public:
    // 实际调用的是RB-tree的key_comp函数
  key_compare key_comp() const { return t.key_comp(); }
    // value_comp实际返回的是一个仿函数value_compare
  value_compare value_comp() const { return value_compare(t.key_comp()); }
    // 以下的begin, end等操作都是调用的是RB-tree的接口
    
   //迭代器
  iterator begin() { return t.begin(); }
  const_iterator begin() const { return t.begin(); }
    
  iterator end() { return t.end(); }
  const_iterator end() const { return t.end(); }
    
   
  reverse_iterator rbegin() { return t.rbegin(); }
  const_reverse_iterator rbegin() const { return t.rbegin(); }
  reverse_iterator rend() { return t.rend(); }
  const_reverse_iterator rend() const { return t.rend(); }
    
    //判断是否为空
  bool empty() const { return t.empty(); }
    
    //计算尺寸
  size_type size() const { return t.size(); }
  size_type max_size() const { return t.max_size(); }
    
    // 交换, 调用RB-tree的swap, 实际只交换count
  void swap(map<Key k, T t, Compare, Alloc>& x) { t.swap(x.t); }
    ...
};
template <class Key, class T, class Compare, class Alloc>
inline void swap(map<Key, T, Compare, Alloc>& x, 
                 map<Key, T, Compare, Alloc>& y) {
  x.swap(y);
}

重载

==,<

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//大小比较，取决于值的大小
class map {
public:
	...
public:
  map(const map<Key, T, Compare, Alloc>& x) : t(x.t) {}
  map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x)
  {
    t = x.t;
    return *this; 
  }
    ...
};
template <class Key, class T, class Compare, class Alloc>
inline bool operator==(const map<Key, T, Compare, Alloc>& x, 
                       const map<Key, T, Compare, Alloc>& y) {
  return x.t == y.t;
}

template <class Key, class T, class Compare, class Alloc>
inline bool operator<(const map<Key, T, Compare, Alloc>& x, 
                      const map<Key, T, Compare, Alloc>& y) {
  return x.t < y.t;
}

[]

1
2
3
4
5
6
7
8
9
10
11
12
class map {
public:
	...
public:
    // 1.  insert(value_type(k, T()) : 查找是否存在该键值, 如果存在则返回该pair, 不存在这重新构造一该键值并且值为空
	// 2.  *((insert(value_type(k, T()))).first) : pair的第一个元素表示指向该元素的迭代器, 第二个元素指的是(false与true)是否存在,  first 便是取出该迭代器而 * 取出pair.
	// 3.  (*((insert(value_type(k, T()))).first)).second : 取出pair结构中的second保存的数据
  T& operator[](const key_type& k) {
    return ( *(  (  insert(value_type(k, T()))   ).first)  ).second;
  }
    ...
};

常用操作

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
//swap() ,交换两个键值的内容
std::cout<<mm["1"]<<" "<<mm["2"]<<std::endl;
std::swap(mm["1"],mm["2"]); 
std::cout<<mm["1"]<<" "<<mm["2"];

//erase
iterator erase（iterator it);//通过一个条目对象删除

iterator erase（iterator first，iterator last）//删除一个范围

size_type erase(const Key&key);//通过关键字删除

clear()//就相当于enumMap.erase(enumMap.begin(),enumMap.end());



//count(const Key& key)
size_type count(const Key& key )  const;//函数功能是返回元素在map/multimap中出现的次数。对于map型容器，返回值只有 0/1
    

//find,其功能是返回指向key的迭代器。如果键值key对应的元素不存在，在函数返回迭代器end()
iterator find(const Key& key);
const_iterator find(const Key& key ) const;


补充1:

在STL中，map,set，multimap，multiset底层都是用红黑树实现，都是有序的

相关操作的复杂度

1
2
3
插入: O(logN)
查看:O(logN)
删除:O(logN)

hash_map, hash_set, hash_multimap, and hash_multiset
上述四种容器采用哈希表实现，不同操作的时间复杂度为：

1
2
3
插入:O(1)，最坏情况O(N)
 查看:O(1)，最坏情况O(N)
 删除:O(1)，最坏情况O(N)。

unordered_map 和 hash_map的内部结构都是用哈希表来实现，但是在C++11中，hash_map已经被舍弃了，最好建议使用unordered_map

更详细的相关区别： https://blog.csdn.net/chen134225/article/details/83106569

参考资料：

https://github.com/GritCS/STL/blob/master/30%20map.md

Posted on Edited on In

总览

插入排序

每次将一个待排序的记录按照其关键字的大小插到前面已经排好序的子序列中

直接插入排序

源码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(T A[], int length){
    for(int i=1;i<length;++i){
        if(A[i]<A[i-1]){//前0-i-1个元素是排好序的元素,
            // 如果A[i]>A[i-1]不移动元素
            int temp = A[i];
            int j;
            for(j=i-1;(temp<A[j])&&(j>=0);--j){
                A[j+1]=A[j];
            }
            A[j+1]=temp;
        }
    }
}

性能分析

最好 最坏 平均
时间 O(n) //只需要比较，不需要移动 $O(n^2)$ $O(n^2)$
空间 O(1) O(1) $O(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
template< class T>
void InsertSort2(T A[] ,int len){
    for(int i=1;i<len;i++){

        if(A[i]<A[i-1]){
            int temp = A[i];
            //利用折半查找，找到要插入的元素;
            int start = 0;
            int end=i-1;
            while(start<end ){
                int mid = (start+end)/2;
                if(A[mid]<temp){//要插入的元素，应该是在右边，找到第一个大于temp的
                    start=mid+1;
                }else{
                    end = mid;
                }
            }//跳出该循环的条件是，end=start，其中end指向最左侧大于A[i]的下标
            for(int j=i-1;j>=end;j--){
                A[j+1]=A[j];
            }
            A[end]=temp;
        }
    }
}

性能分析

希尔排序

由于直接插入排序算法更适用于 基本有序的排序表和数据量不大的排序表。

希尔排序基于这两点进行改进，缩小增量排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void ShellSort(T A[],int len){
   for(int d =len/2l;d>1;d=d/2){
       for(int i=d+1;i<len;i++)//起始位置
       {
           if (A[i] < A[i - d]) {
               int temp = A[i];
               int j = 0;
               for (j = i - d; j > 0 && temp < A[j]; j -= d) {
                   A[j + d] = A[j];
               }
               A[j + d] = temp;
           }
       }
   }
}

交换排序

交换：跟据序列中两个元素关键点的比较结果来对换这两个记录在序列中的位置

冒泡排序

从后往前两两比较相邻元素的值，

源码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void BubbleSort(T A[] , int len){
	bool flag = false;
    while(!flag){
        flag = true;
        for(int i=0;i<len;i++){
            for(int j=0;j<len-1;j++){
                if(A[i]>A[i+1]){
                    std::swap(A[i],A[i+1]);
                    flag = false;
                }
            }
        }
    }
}

性能分析

最好 最坏 平均
时间 O(n) //只需要比较，不需要移动 $O(n^2)$ $O(n^2)$
空间 O(1) O(1) $O(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
26
27
28
template<class T>
int Partition(T A[], int start,int end){
    T base = A[start];
    int low=start;
    int high=end;
    while(low<high){//low指向小于等于元素，high指向大于元素
        while(A[low]<=base){//会自动跳过base
            low++;
        }
        while(A[high]>base){
            high--;
        }
        if(low<high){
            std::swap(A[low],A[high]);//交换两个
        }
    }
    std::swap(A[high],A[start]);//high指向最右侧的最大元素
    return high;
}
template<class T>
void QuickSort(T A[],int start, int end){
    //不断分治
    if(start<end){
        int mid = Partition(A,start,end);
        QuickSort(A,start,mid-1);
        QuickSort(A,mid+1,end);
    }
}

性能分析

最好 最坏 平均
时间 O(log_ n) //只需要比较，不需要移动 $O(n)$ $O(log_2 n)$
空间 $O(n *log_2 n)$ $O(n^2)$ 约等于$O(n*log_2 n)$

最快的内部排序，不稳定的排序方法

选择排序

简单选择排序

选择排序基本思想：每一趟在后面n-i-1个待排序元素中选取关键字最小的元素;作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下一个就不用再选了

源码

性能分析

最好 最坏 平均
时间 O(n) //只需要比较，不需要移动 $O(n^2)$ $O(n^2)$
空间 O(1) O(1) $O(1)$

不稳定的排序方法

堆排序

源码实现(大根堆为例)

1
2
3
4
5
6
7
8
9
10
void HeapSort(){
	//初始建堆
    build();
    //堆排序
    for(int i=1;i<n-1;i++){
        swap(1,hlen);
        hlen--;
        down(1); //不断删除最大结点
    }
}

之前总结过堆的相关笔记

性能分析

最好 最坏 平均
时间 $O(n *log_2 n)$ $O(n *log_2 n)$ $O(n *log_2 n)$
空间 O(1) O(1) $O(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
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
 template<class T>
 void Merge(T A[], int left,int mid,int right){
     int i=left;
     int j=mid;
     int size = right-left;
     T* B= new T(size);
     int k=0;
     while(i<mid&&j<right){
         if(A[i]<A[j]){//A[i]在前
             B[k]=A[i];
             i++;
             k++;
         }else{
             B[k]=A[j];
             j++;
             k++;
         }
     }
     if(i<mid){
         while(i<mid){
             B[k++]=A[i++];
         }
     }
     if(j<right){
         while(j<right){
             B[k++]=A[j++];
         }
     }
     for(int k=0;k<size;k++){
         A[k+left]=B[k];
     }
 }

template<class T>
void MergeSort(T A[],int len){
    T *B=new T[len];
   int d=1;
   int start=0;
   int end=len;
   while(start+d<=end){
       for(int i=start;i<=end;i+=2*d){
           if(i+2*d<end)
           {
               Merge(A,i,i+d,i+2*d);//左闭右开
           }else if(i+d<end){
               Merge(A,i,i+d,end);
           }
           //剩余一个数组，不需要排序
       }
       d=d<<1;//乘2
   }
}
最好 最坏 平均
时间 $O(n *log_2 n)$ $O(n *log_2 n)$ $O(n *log_2 n)$
空间 O(n) O(n) $O(n)$

是一种稳定的排序方式

基数排序

不基于比较和移动进行排序，而是基于关键字各位的大小进行排序

最高次序位法(MSD)：先最高位进行分桶，对桶内记录进行排序，然后按次高位排序，最后按最低位排序。

最低次序位法(LSD)：首先按最低位排序，然后按下一个次低位排序，..，最后按最高位排序。

比较适合链表结构，辅助空间：r+1个队头指针和队尾指针，n个link域

一般如果r<<n,时间复杂度是O(n p)

源码实现

略

内排序总结

如果文件的初始状态已经按关键字基本有序，则选用直接插入或者冒泡排序。

在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移。任何借助“比较”的排序算法，至少需要$O(nlog^2n)$

2021-02-24_13-01

Posted on Edited on

优先级队列：

按照事先约定的优先级，可以始终高效查找并访问优先级最高数据项的数据结构

维护了数据项的一个偏序关系

操作接口

1
2
3
4
5
6
7
8
size(); //报告优先级队列的规模

 insert(); //将指定词条插入优先级队列
   
    
 getMax();
    
 delMax(); //删除优先级最大的词条

应用实例:Huffman编码树，堆

Huffman编码树：略

堆

原理：

​ 主要求解问题：O(1)的算法在n个给定的整数中找最大值, 有限偏序集的极值必然存在，堆用来维护一个偏序关系

性质：

​ 1.完全二叉树

​ 2.保存有序关系. 小根堆:每个结点的值都小于其子结点的值;

​ 大根堆: 每个结点的值都大于其子结点的值;

物理结构:

​ 有序列表

主要操作:

​ ==上浮操作== —当大根堆的元素变大时，该结点可能会==上浮== —O(log n)

1
2
3
4
5
6
7
inline void up(int index){ //处于index的元素变大
    int i=index;
    while( i>1 && h[i]>h[i/1]){//对于大根堆来说，如果子结点大于父结点，一定需要交换
        swap(h[i],h[i/2]);
        i>>1;
    }
}

​ ==下沉操作==—当大根堆的元素变小时，该结点可能会==下沉== —-O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
inline void down(int index){
    int i=index;
    while( (2*i<= len &&  h[2*i] > h[i]) ||
         (2*i+1<=len && h[2*i+1] > h[i])  ) {
        	int temp = 2*i;         //temp用于保存 较大的元素的下标
       		if( h[2*i+1] > h[i] ){
            	temp++; //temp为2*i+1
        	}
    	swap(h[index], h[temp]);
        i=temp ;//判断是否需要继续下沉
    }
}

​ ==插入操作==–O(log n)–在数组最末尾插入元素,再做up操作

1
2
3
4
5
inline void insert(int x){ //插入x
	len++;
	h[len] = x;
	up(len);
}

​ ==删除操作==–O(log n)–删除第index个元素，为了不破坏堆的性质，把h[len]移动到index处，堆元素个数减一，再判断做up(index) 还是down(index)

1
2
3
4
5
6
7
8
9
10
inline void delete(index ){
    int t=h[index];
    h[index]=h[len];
    len--;
    if( h[index] >t ) 
        up(index);
    else
        down(index);
    return t;
}

过程: 初始建堆

​ 方法1：执行n次insert操作,时间复杂度O(n*log n)

1
2
3
4
void build(){
	for(int i=1; i<=n;i++)
		insert(a[i]);
}

​ 方法2：执行n/2次down操作 

1
2
3
4
5
6
void build(){
    len = n;
    for(int i=1;i<n;i++) h[i]=a[i];
    for(int i=n/2;i>=1;i--) down(i);
}

堆排序

初始建堆 O(n),堆排序算法为 O(n log n)

时间复杂度：最好，最坏，平均情况相同

1
2
3
4
5
6
7
8
9
10
void HeapSort(){
	//初始建堆
    build();
    //堆排序
    for(int i=1;i<n-1;i++){
        swap(1,hlen);
        hlen--;
        down(1); //不断删除最大结点
    }
}

(小根堆相反)

STL中堆的使用

方法1：<queue>中的priority_que

初始化方式
1
2
template<typename T, typename Container=std::vector<T>,typename Compare=std::less<T> >
class priority_queue
基本操作
1
2
3
4
5
6
7
8
9
10
11
push(const T& obj);// 将obj的副本放到容器的适当位置，这通常会包含一个排序操作。

push(T& obj); //将obj放到容器的适当位置，这通常会包含一个排序操作。

emplace(T constructor a rgs...);
//通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
top();//：返回优先级队列中第一个元素的引用。
pop();//：移除第一个元素。
size();//：返回队列中元素的个数。
empty()//：如果队列为空的话，返回true。
swap(priority_queue<T>& other);//：和参数的元素进行交换，所包含对象的类型必须相同。
使用

1.最基本的使用方法，对于一串数字建堆（默认为大根堆）

1
priority_queue<int> heap;

2.自定义

1
2
3
priority_queue<int,vector<int>, greater<int> > qi2;//最小堆

priority_queue<int,vector<int>, less<int> >qi3; //最大堆

  • 使用自定义的cmp类，重载operator

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    struct Node{
    	int x;
        int y;
        int val;
       Node(int a,int b,int valin):x(a),y(b),val(valin){}
    };

    struct cmp{
        bool operator()(const Node& a, const Node& b){
            return a.val<b.val;//大根堆
        }
    }

    priority_queue<Node,vector<Node>, cmp> heap;//建堆
    heap.pop();//出堆
    heap.push();//入堆
    heap.top(); //获取堆顶元素

方法2：利用vector

这种法法需要#include<algorithm> #include <functional>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> a;
//建堆
make_heap(a.begin(),a.end(), less<int>() );//最大堆
make_heap(a.begin(),a.end(), greater<int>() );//最小堆
//pop
pop_heap(a.begin(),a.end(), less<int>() );//最大值出堆
pop_heap(a.begin(),a.end(), less<int>() );//最小值出堆


//插入元素
push_heap(a.begin(),a.end(),cmp);
//堆排序

sort_heap(a.begin(),a.end(),cmp);
// push_heap ( begin , end )   将最后一个元素插入堆中（堆自动调整）
// pop_heap ( begin , end )   将第一个元素从堆中删去（堆自动调整），并放到最后
// find ( begin , end , value ) 从begin到end查找value，若找不到，返回end

Posted on Edited on

**STL(Standard Template Library)**概念

​ 6大组件： 容器，算法，迭代器，仿函数，适配器，空间配置器

STL的优点：1.不需要额外安装其他软件包

​ 2.实现了数据结构和算法的分离

​ 3.程序员可以不用思考STL具体的实现过程，封装易用

​ 4.高可重用性(模板类，模板函数)

​ 5.高性能

​ 6.高移植性

​ 7.跨平台性

容器：

​ 序列式容器：容器的元素的位置是由 进入容器的时机和地点来决定

​ 关联式容器：容器已有规则，通常提供键值key作为索引

​

vector

动态增长原理

vector：动态数组,可变数组,单口容器

动态增长原理：当插入新元素的时候，如果空间不足，vector会重新申请更大的一块内存空间，将源空间数据拷贝到新空间，释放旧空间数据，再把新元素插入新申请空间.注意：一旦引起空间重新配置，指向原vector的所有迭代器都失效了

3个迭代器属性：start,finish,end_of_storage

finish: 指向数组中最后一个元素的下一个位置

vector常用API

vector构造函数

1
2
3
4
5
6
7
8
9
10
vector<T> V; //利用模板实现类实现 ，默认构造函数

vector(v.begin(), v.end() );  //v为vector<T>
//将v[begin(), end()] 区间中的元素拷贝给本身

vector(n,elem ); //构造函数将n个elem拷贝给本身

//第一个赋值函数
int arr[] ={0,1,2,3,4};
vector<int> vl(arr,arr + sizeof(arr)/sizeof(int) );

其他基本操作

属性获取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public:
	// 获取数据的开始以及结束位置的指针. 记住这里返回的是迭代器, 也就是vector迭代器就是该类型的指针.
    iterator begin() { return start; }
    iterator end() { return finish; }
	// 获取值
	reference front() { return *begin(); }
    reference back() { return *(end() - 1); } 

// 获取右值
	const_iterator begin() const { return start; }
    const_iterator end() const { return finish; }

	const_reference front() const { return *begin(); } //首元素
	const_reference back() const { return *(end() - 1); }//最后一个元素


    // 获取基本数组信息
	size_type size() const { return size_type(end() - begin()); }	 // 数组元素的个数
    size_type max_size() const { return size_type(-1) / sizeof(T); }	// 最大能存储的元素个数
    size_type capacity() const { return size_type(end_of_storage - begin()); }	// 数组的实际大小
元素访问方法
1
2
3
4
5
6
7
8
vector<typename T> c;

c.at(index);
c[index]; //这两种访问方式返回值都是引用，可读可写

c.front();//返回第一个元素
c.back();//返回最后一个元素

增删改查

  • push和pop操作都只是对尾部finish进行操作的

  • erase清除是一个左闭右开的区间.

1
2
void push_back(const T& x);
vector<T ,Alloc> ::insert(iterator position, size_type n, const T& x); //从position开始，插入n个元素，元素的初值是x
1
2
3
4
5
6
7
void pop_back(); //将尾端元素拿掉，并调整大小

iterator erase(iterator first,iterator last); //清除[first,last) 中的所有元素,return first
  
iterator erase(iterator position); //清除某个位置上的元素 return position

void clear() { erase(begin(), end()); }
容器的调整
1
2
void reserve(size_type n)//修改容器的实际大小
void resize (size_type new_size)
vector遍历
1.使用迭代器
1
2
3
4
5
6
7
8
9
10
template<class T>
void Iter_for(vector<T>& vt){
	T temp;
	vector<T> :: iterator iter;
	for(iter=vt.begin(); iter!=vt.end(); iter++){
		temp =*iter;
		std::cout<<temp<<std::endl;
	}
}

2.for_at
1
2
3
4
5
6
7
8
9
10
template<class T>
void at_for(vector<T>& vt){
	T temp;
    int i=0;
    int m=vt.size();
    for(i=0;i<m;i++){
        temp=vt.at(i);
        std::cout<<temp<<std::endl;
    }
}
3. STL for_each

for_each原型

1
2
3
4
5
 template < typename InputIterator, typename Function >
Function for_each(InputIterator beg, InputIterator end, Function f)  {
  while(beg != end) 
    f(*beg++);
}
1
2
3
4
5
6
7
8
9
10
11
#include<algorithm>
#include<iostream>
#include<vector>
void print(const int& temp){
    std::cout<<temp<<endl;
}
void main(){
    int nums[4]={1,2,3,4};
   	vector<int> myvt=std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
    std::for_each(ptr.begin(),ptr.end(),print)
}

vector高级编程

元素查找和搜索

使用STL通用算法find()

1
2
3
4
template<class InputIterator,class T> inline
 InputIterator find(InputIterator first,InputIterator last, const T& value);

InputIterator find_if(InputIterator first,InputIterator last,Predicate predicate);
元素排序

使用STL通用算法sort()

sort()底层实现是插入排序优化的快排，时间复杂度是 n*log2(n)

1.跟据元素自身定义的大小关系，进行升序排序
1
2
template <class RandomAccessIterator>
   inline void sort(RandomAccessIterator first, RandomAccessIterator);

使用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>

#include<vector>
#include<algorithm>

void print(const int& temp){
    std::cout<< temp<<" ";
}
int main(){
    int nums[] = {34,1,89,0,3,5,11};
    std::vector<int> ptr = std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
    //遍历方法
    std::for_each(ptr.begin(),ptr.end(),print);

    //sort两个参数
    std::sort(ptr.begin(),ptr.end());
    std::cout<<std::endl;
    std::for_each(ptr.begin(),ptr.end(),print);
}
/**
34,1,89,0,3,5,11
0,1,3,5,11,34,89
**/
2.利用cmp函数定义大小关系，bool cmp{};
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
#include<iostream>

#include<vector>
#include<algorithm>

void print(const int& temp){
    std::cout<< temp<<" ";
}
bool cmp(int a,int b){
    return (a>b);//升序排列
}
int main(){
    int nums[] = {34,1,89,0,3,5,11};
    std::vector<int> ptr = std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
    //遍历方法
    std::for_each(ptr.begin(),ptr.end(),print);

    //sort三个参数
    std::sort(ptr.begin(),ptr.end(),cmp);
    std::cout<<std::endl;
    std::for_each(ptr.begin(),ptr.end(),print);
}
/**
34 1 89 0 3 5 11 
89 34 11 5 3 1 0 
**/