[学习笔记Day06]C++算法设计与分析：算法及其算法设计工具的认识！-资源刺客

算法的概述：

算法（algorithm）是指解题方案的准确且完整的描述，是一系列解决问题的清晰指令，也就是说算法能够对一定规范的输入在有限时间内获得所要求的输出。

算法具有5个特性：

有限性：一个算法总是在执行有限步之后结束，且每一步都可在有限时间内完成。
确定性：算法中每一条指令必须有确切的含义，不会产生二义性。
可行性：算法中每一条运算都必须是足够基本的，也就是说他们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。
输入性：一个算法有零个或多个输入。
输出型：一个算法有一个或多个输出。

算法设计工具 STL

STL 是一个功能强大的基于模板的容器库，通过直接使用现成的容器库，通过直接使用现成的标准化组件来大幅度提高算法设计的效率和可靠性。

数据结构容器	说明	头文件
verctor	向量	<vector>
string	字符串	<string>
deque	双端队列	<deque>
list	链表	<list>
stack	栈	<stack>
queue	队列	<queue>
priority_queue	优先队列	<queue>
set / multiset	集合 / 多重集合	<set>
map / multimap	映射 / 多重映射	<map>
unordered_set	哈希集合	<unordered_set>
unordered_map	哈希映射	<unordered_map>

常用的数据结构容器和相应头文件

通用算法	说明	头文件
accumulate(beg , end , initv)	返回[beg , end]范围内的元素再加上 initv	<numeric>
binary_search(beg , end , val)	在[beg , end]指定的有序序列中二分查找 val	<algorithm>
lower_bound(beg , end , val)	在[beg , end]指定的有序序列中二分查找第一个大于或等于 val 的位置	<algorithm>
upper_bound(beg , end , val)	在[beg , end]指定的有序序列中二分查找第一个大于 val 的位置	<algorithm>
max(a , b)	返回 a 和 b 中的最大值	<algorithm>
min(a , b)	返回 a 和 b 中的最小值	<algorithm>
swap(a ,b)	交换 a 和 b	<algorithm>
reverse(beg , end)	逆置[beg , end]范围内的元素	<algorithm>
prev_permutation(beg , end)	重置[beg , end]标记的排列为上一个排列	<algorithm>
next_permutation(beg , end)	重置[beg , end]标记的排列为下一个排列	<algorithm>
sort(beg , end [, comp])	根据比较关系 comp 对[beg , end]范围内的元素排序	<algorithm>
stable_sort(beg , end [,comp])	根据比较关系 comp 对[beg , end]范围内的元素采用稳定方法排序	<algorithm>
find(beg , end , val)	在[beg , end]范围内查找 val 元素	<algorithm>
find(beg , end , val , pred)	在[beg , end]范围内查找满足 pred 谓词的元素	<algorithm>

常用的 STL 通用算法和相应头文件

STL 迭代器：

其用于访问容器中的数据对象，迭代器像 C++ 中的指针，算法通过迭代器来定位和操作容器中的元素。

常用的迭代器：

iterator：指向容器中存放元素的迭代器，用于正向遍历容器中的元素
const_iterator：指向容器中存放元素的常量迭代器，只能读取容器中的元素
reverse_iterator：指向容器中存放元素的反向迭代器，用于反向遍历容器中的元素
const_reverse_iterator：指向容器中存放元素的常量反向迭代器，只能读取容器中的元素

迭代器的常用运算符：

++：正向移动迭代器
--：反向移动迭代器
*：返回迭代器所指的元素值

vector 向量容器：

vector 是一个向量类模板，相当于动态数组，用于存储具有相同数据类型的序列元素。

定义语法：

vector<int> v1;           //定义元素为 int 的向量 v1
vector<int> v2(10);       //指定 v2 的初始大小为10个元素
vector<int> v3(10, -1);   //指定 v3 的初始大小为10个元素，每个元素的初始值为 -1
vector<int> v4(a, a+5);   //用数组 a[0..4] 初始化 v4
vector<int> v5(v1);       //由 v1 复制产生 v5

函数	说明
empty()	判断容器是否为空
size()	返回容器中实际的元素个数
reserve(n)	为容器预分配 n 个元素的存储空间
[k]	返回容器中下标为 k 的元素
at(k)	与 [k] 相同
front()	获取容器中的首元素
back()	获取容器中的尾元素
push_back()	在容器的尾部添加一个元素
pop_back()	删除容器尾部的元素
insert(pos , e)	在 pos 位置插入元素 e
erase()	删除容器中某个迭代器或者迭代器区间指定的元素
clear()	删除容器中的所有元素
begin()	返回容器中首元素的迭代器
end()	返回容器中尾元素后面一个位置的迭代器
rbegin()	返回容器中尾元素的迭代器
rend()	返回容器中首元素前面一个位置的迭代器
capacity()	返回容器最多能容纳的元素个数
resize(n)	调整容器的大小，使其能容纳 n 个元素

主要的成员函数

内置数据类型排序：

vector<int> myv = {2,1,5,4,3};

sort(myv.begin(),myv.end(),less<int>());   //指定为递增排序
sort(myv.begin(),myv.end(),greater<int>());//指定为递减排序
sort(myv.begin(),myv.end());               //不指定 less<int>,默认为递增排序

//C++ 11及以上版本支持 Lambda 表达式
sort(myv.begin(),myv.end(),[](int a, int b) -> bool{ return a<b }); //指定为递增排序
sort(myv.begin(),myv.end(),[](int a, int b) -> bool{ return a>b }); //指定为递减排序

说明：less<T>、greater<T>均属于 STL 关系函数对象，分别支持对象之间的小于、大于比较，返回布尔值。

自定义数据类型的排序：

对于自定义数据类型（例如结构体或类），同样默认是以 less<T>(大小关系函数) 作为关系比较函数，但需要重载该函数。

实现排序的方法有两种：

在声明结构体类型中重载 < 运算符，以实现制定成员的递增或递减排序。
用户自己在结构体或类中重载函数调用运算符 () ，以实现按指定成员的递增或递减排序。

struct Stu {
      int no;
      string name;
      Stud(int _no ,string _name){
            no = _no;
            name = _name;
      }

      bool operator()(const Stud &s ,const Stud &t) const {
            return s.name < t.name;
      }
};

int main(){
      Stud a[] = {Stud(2 ,"Marry") ,Stud(1 ,"John") ,Stud(5 ,"Smith")};
      int no = sizeof(a) / sizeof(a[0]);
      vector<Stud> myv(a ,a+n);
      sort(myv.begin() ,myv.end());         //默认使用 < 运算符，按 no 递减排序
      sprt(myv.begin() ,myv.end() ,Cmp());  //使用 Cmp() 中的 () 运算符，按 name 递增排序
      return 0;
}

string 字符串容器

string 是一个保存字符序列的容器，他的所有元素为字符类型。其常用的操作包括增加、删除、修改、查找比较、连接、输入和输出等。同时，他还重载了许多运算符，包括+、+=、<、=、[]、<<和>>等。

定义语法：

string();                                                   //建立一个空的字符串

string(const string &str);                                  //用字符串 str 建立当前字符串

string(const string &str ,size_type i);                     //用字符串 str 起始于 i 的所有字符建立当前字符串

string(const string &str ,size_type i ,size_type len);      //用字符串 str 起始于 i 的 len 个字符建立当前字符串

string(const char * cstr);                                  //用 C-字符串 cstr 建立当前字符串

string(const char * cstr ,size_type len);                   //用 C-字符串 cstr 的开头 len 个字符建立当前字符串

string(size_type len ,char c);                              //用 len 个字符 c 建立当前字符串

注意： C-字符串 表示采用字符数组存放的字符串。例如：

char cstr[] = "China! Great Wall";      //C-字符串

string s1(cstr);                        //s1:China! Great Wall

string s2(s1);                          //s2:China! Great Wall

string s3(cstr ,7 ,11);                 //s3:Great Wall

string s4(cstr ,6);                     //s4:China

string s5(5 ,'A');                      //s5:AAAAA

函数	说明
empty()	判断当前字符串是否为空串
size()	返回当前字符串的实际字符个数（返回结果为 size_type 类型）
length()	返回当前字符串的实际字符个数
compare(const string &str)	返回当前字符串与字符串 str 的比较结果（在比较时，若两者相等，返回 0，若后者大于前者，返回 -1，反之返回 1）
[k]	返回当前字符串中下标为 k 的字符
at(k)	与 [k] 用法相同
front()	获取当前字符串的首字符
back()	获取当前字符串的尾字符
push_back()	在当前字符串的尾部添加一个字符
pop_back()	删除当前字符串尾部字符
append(str)	在当前字符串的尾部添加一个字符串 str
insert(size_type i ,const string &str)	在当前字符串的位置 i 插入一个字符串 str
find(string &s ,size_type pos = 0)	从当前字符串中的 pos 位置开始查找并返回字符串 s 的第一个位置，没有则返回 -1
replace(size_type i ,size_type len ,const string &str)	将当前字符串中起始于 i 位置的 len 个字符用一个字符串 str 替换
replace(iterator beg ,iterator end ,const string & str)	将当前字符串中 [beg , end] 区间的所有字符用字符串 str 进行替换
substr(size_type i)	返回当前字符串起始于 i 位置的子串
substr(size_type i ,size_type len)	返回当前字符串起始于 i 位置的长度为 len 的子串
clear()	删除当前字符串中的所有字符
erase(size_type i)	删除当前字符串从 i 位置开始的所有字符
erase(size_type i ,size_type len)	删除当前字符串从 i 位置开始的 len 个字符

string 成员函数（常用操作字符串）

练习

一个字符串 s 中有许多个单词（单词内不含空格），求单词的数量

void main(){
     string str = "My name is John!";
     int n = str.length();
     
     if (n <= 0) return;
     
     int ans = 0;
     int i = 0;
     while(i < n && str[i] != "") i++;
     int j = str.find(" " ,i);
     while(j != -1){
          ans++;
          i = j;
          while(i < n && str[i] != "") i++;
          j = str.find(" " ,i);
     }

     if(i == n)return ans;
     else return ans+1;
}

deque 双端队列容器

deque 是一个双端队列类模板。就是将其中的所有元素看成一个序列，这样有两个端点（分别称为队头端和队尾端）。由于 deque 的组织结构特殊，按序号查找元素的性能低于 vector 但好于 list。

定义语法：

deque<int> dq1;                              //定义元素为 int 的双端队列 dq1

deque<int> dq2(10);                          //指定 dq2 的初始化大小为10个 int 元素

deque<int> dq3(10 ,-1);                      //指定 dq3 的10个元素的初值均为-1

deque<int> dq4(dq2.begin() ,dq2.end());      //用 dq2 的所有元素初始化 dq4

函数	说明
empty()	判断双端队列容器是否为空队
size()	返回双端队列容器中元素的个数
front()	取队头元素
back()	去队尾元素
push_front(e)	在对头插入元素
push_back(e)	在队尾插入元素
pop_front(e)	删除队头的一个元素
pop_back(e)	删除队尾的一个元素
erase()	从双端队列容器中删除一个或几个元素
clear()	从双端队列容器中的所有元素
begin()	返回容器中首元素的迭代器
end()	返回容器中尾元素后面一个位置的迭代器
rbegin()	返回容器中尾元素的迭代器
rend()	返回容器中首元素前面一个位置的迭代器

主要的成员函数

注意：在调用 back() 和 front() 及其后端出队函数之前务必通过 empty() 检测是否为空。

list 链表容器

list 是一个双端链表类模板，可以从任何地方快速插入与删除。list 容器插入元素比 vector 容器快，另外对每个元素单独分配空间，所以不存在空间不够需要重新分配空间的情况。

定义语法：

list<int> l1;              //定义元素为 int 的链表 l1

list<int> l2(10);          //指定链表 l2 的初始化大小为10个 int 元素

list<int> l3(10 ,-1);      //指定 l3 的10个元素的初值均为-1

list<int> l4(a ,a+5);      //用数组 a[0..4] 的所有元素初始化 l4

函数	说明
empty()	判断链表容器是否为空队
size()	返回链表容器中元素的个数
push_back(e)	在链表的尾部插入元素
pop_back(e)	删除链表尾部的一个元素
remove()	删除链表容器中所有指定值得元素
remove_if(cmp)	删除链表容器中的满足条件的元素
erase()	从双端队列容器中删除一个或几个元素
unique()	删除链表容器中相邻的重复元素
clear()	从双端队列容器中的所有元素
insert(pos , e)	在 pos 位置插入元素 e，即将元素 e 插入迭代器 pos 指定元素之前
insert(pos , n , e)	在 pos 位置插入 n 个元素 e
insert(pos , pos1 , pos2)	在迭代器的 pos 处插入 [pos1 , pos2) 的元素
reverse()	反转链表
sort()	对链表容器中的元素排序
begin()	返回容器中首元素的迭代器
end()	返回容器中尾元素后面一个位置的迭代器
rbegin()	返回容器中尾元素的迭代器
rend()	返回容器中首元素前面一个位置的迭代器

主要的成员函数

注意：STL 提供的 sort() 通用排序算法主要用于支持随机访问的容器，而 list 容器不支持随机访问，为此 list 容器提供了 sort() 成员函数用于排序，类似的还有 unique()、reverse()、merge() 等 STL 算法。

stack （栈容器）

stack 是一个栈类模板，和数据结构中的栈一样，具有后进先出的特点。默认的底层容器是 deque，也可以指定为 vector 或者 list，比如：

stack<int> st1;             //默认底层容器为 deque

stack<int,vector<int>> st2; //指定底层容器为 vector

stack<int,list<int>> st3;   //指定底层容器为 list

函数	说明
empty()	判断栈容器是否为空
size()	返回栈容器中实际的元素个数
push()	元素 e 进栈
top()	返回栈顶元素
pop()	元素出栈

主要的成员函数

queue（队列容器）

queue 是一个队列类模板，和数据结构中的队列一样，具有先进先出的特点。其默认的底层是 deque，也可以是 list，但是不能指定 vector 为底层容器。

函数	说明
empty()	判断队列容器是否为空
size()	返回队列容器中实际的元素个数
front()	返回对头元素
back()	返回队尾元素
push()	元素 e 进队
pop()	元素出队

主要的成员函数

priority_queue （优先队列容器）

priority_queue 是一个优先队列类模板。其默认底层容器是 vector，也可以指定 deque 容器，但不能指定 list 为底层容器。

函数	说明
empty()	判断优先队列容器是否为空
size()	返回有限队列容器中实际的元素个数
push(e)	元素 e 进队
top()	获取对头元素
pop()	元素出队

主要的成员函数

优先队列元素优先级的高低由队列中数据元素的关系函数（比较运算符）确定，其底层一般采用完全二叉树顺序，元素越优先出队的优先队列称为大根堆，反之。

元素为内置数据类型的优先队列

对于 C/C++ 内置数据类型，默认以 less<T> （小于关系函数）作为关系比较函数，值越大优先级越高，可以改为以 greater<T> 作为关系比较函数，这样值越大优先级越低。

priority_queue<int> pq1;                          //默认为大根堆

priority_queue<int,vector<int>,greater<int>> pq2; //小根堆

C++ 11 以后的版本支持 Lambda 表达式，即用 Lambda 表达式表示排序中的比较方式，例如：

auto comp1 = [](int a ,int b){return a < b};
priority_queue<int ,deque<int> ,decltype(comp1)> pq1(comp1); //大根堆

auto comp2 = [](int a ,int b){return a > b};
priority_queue<int ,deque<int> ,decltype(comp2)> pq2(comp2); //小根堆

元素为自定义类型的堆

对于自定义数据类型，例如结构体数据，同样默认是以 less<T>（小于关系函数）作为关系比较函数，但需要重载该函数。

实现优先队列主要有三种方式：

在声明结构体类型中重载 < 运算符以指定优先级（如 priority_queue<Stud> pq1调用默认的函数）< 运算符创建堆 pq1 （是大根堆还是小根堆由 < 重载函数体确定）
在声明结构体类型中重载 > 运算符以指定优先级（如 priority_queue<Stud ,vector<Stud> ,greater<Stud>> pq2 调用重载） > 运算符创建堆 pq2，此时需要指定优先队列的底层容器（这里为 vector，也可以是 deque）
用户自己在结构体或类中重载函数调用运算符 () 以指定元素的优先级（如 priority_queue<Stud ,vector<Stud> ,StudCmp> pq3）调用 StuCmp 结构体的 () 运算符创建堆 pq3，此时需要制定优先队列的底层容器（这里为 vector，也可以是 deque）

struct Stud{
      int no;
      string name;
      Stud(int n ,string na){
            no = n;
            name = na;
      }

      bool operator<(const Stud &s) const{
            return no < s.no;//no 越大越优先
      }

      bool operator>(const Stud &s) const{
            return no > s.no;//no 越大越优先
      }
};

//StudCmp 结构体
struct StudCmp{
      bool operator()(const Stud &s ,const Stud &t) const {
            return s.name < t.name;  //name 越大越优先
      }
}

int main(){
      Stud a[] = {Stud(2,"Marry"),Stud(1,"John"),Stud(5,"Smith")};
      int n = sizeof(a) / sizeof(a[0]);
      priority_queue<Stud> pq1(a,a+n);                                       //默认 < 运算符
      cout << "pq1 出队顺序："
      while(!pq1.empty()){                                                   //按 no 递减输出
            cout << "[" << pq1.top().no << "," << pq1.top().name << "]\t";
            pq1.pop();
      }
      cout << endl;
      
      priority_queue<Stud ,deque<Stud> ,greater<Stud>> pq2(a ,a+n);
      cout << "pq2 出队顺序："
      while(!pq2.empty()){                                                     //按 no 递增输出
            cout << "[" << pq2.top().no << "," << pq2.top().name << "]\t";
            pq2.pop();
      }
      cout << endl;
      
      priority_queue<Stud ,deque<Stud> ,StudCmp> pq3(a ,a+n);
      cout << "pq3 出队顺序："
      while(!pq3.empty()){                                                      //按 name 递减输出
            cout << "[" << pq3.top().no << "," << pq3.top().name << "]\t";
            pq3.pop();
      }
      cout << endl;
      return 0;
}

set（集合容器）/ multiset（多重集合容器）

set 和 multiset 是集合类模板，都属于关联容器，所谓关联容器就是每个元素有一个 key（关键字），通过 key 进行元素操作，关键字与元素的位置没有对应关系，所以关联容器不提供顺序容器中的 front()、push_front()、back()、push_back() 以及 pop_back() 运算。

set 中的元素的关键字是唯一的，multiset 中的元素的关键字可以不唯一。他们内部采用红黑树组织，默认情况下按关键字自动进行升序排列，所以查找、插入和触发运算的速度比较快，同时支持集合的交、差和并等运算。

定义语法：

int a[] = {10,20,30,40,50};
struct Cmp{
      bool operator()(const int&a ,const int& b) const{
            return a < b;
      }
}

set<int> s1;
set<int> s2(a ,a+5);
set<int> s3(s2)
set<int> s4(s2.begin() ,s2.end());
set<int ,Cmp> s5;

方法	说明
empty()	判断容器是否为空
size()	返回容器中实际的元素个数
find(k)	若容器中存在关键字 k 的元素，返回该元素的迭代器，否则返回 end()
count(k)	返回容器中关键字 k 出现的次数
upper_bound(k)	返回一个迭代器，指向第一个关键字大于 k 的元素
lower_bound(k)	返回一个迭代器，指向第一个关键字大于或等于 k 的元素
insert()	插入元素
erase()	删除容器中的一个或几个元素
clear()	删除容器中的所有元素。
begin()	用于正向迭代，返回容器中首元素的迭代器
end()	用于正向迭代，返回容器中尾元素后面一个位置的迭代器
rbegin()	用于反向迭代，返回容器中尾元素的迭代器
rend()	用于反向迭代，返回容器中首元素前面一个位置的迭代

set 的主要成员函数

map（映射容器）/multimap（多重映射容器）

map 和 multimap 是映射类模板，同样属于关联容器，即按关键字 key 进行元素操作。但与 set 和 multiset 不同，map 和 multimap 中的元素属于 pair 结构体，pair 结构体是内置类型。

struct pair{
      T first;  //第一分量，map 中对应的 key
      T second; //第二分量，map 中对应的 value
}

例如：顶一个对象 p 表示一个平面坐标点并输入坐标

pair<int,int> p;
cin >> p.first >> p.second; //输入坐标

同时 pair 对 ==、=!、<、>、<=、>= 共6个运算符进行重载，提供了按照字典序对元素进行大小比较的运算符模板。

定义语法：

map<char,int> mp1;

mp1['a'] = 10;
mp1['b'] = 30;
mp1['c'] = 50;
mp1['d'] = 70;

map<char,int> mp2(mp1.begin() ,mp1.end());
map<char,int> mp3(mp2);

函数	说明
empty()	判断容器是否为空
size()	返回容器中实际的元素个数
map[k]	返回关键字为 k 的元素，当不存在时插入以 k 为关键字的元素
find()	在容器中查找元素
count()	容器中指定关键字的元素个数（map 中只有 0 或 1）
insert(e)	插入一个元素 e 并返回该元素的位置
erase()	删除容器中的一个或几个元素
clear()	删除所有元素
begin()	用于正向迭代，返回容器中首元素的迭代器
end()	用于正向迭代，返回容器中尾元素后面一个位置的迭代器
rbegin()	用于反向迭代，返回容器中尾元素的迭代器
rend()	用于反向迭代，返回容器中首元素前面一个位置的迭代

map 的主要成员函数

三种插入元素的方式：

map<char,int> mp;

mp.insert(pair<char,int>('a',1));             //方式一
mp.insert(map<char,int>::value_type('b',2));  //方式二
mp['c'] = 3;                                  //方式三

获取元素：

int num = mp['a'];

修改元素：

mp['c'] = 4;

判断某个元素是否存在：

if(mp.find('a') == mp.end()){
      //不存在
} else {
      //存在
}

或者

if(mp.find('a') == 0){
      //不存在
} else {
      //存在
}

unordered_set（哈希集合容器）

unordered_set 与 set 类似，每个元素对应一个关键字，所有元素的关键字是唯一的，只是 unordered_set 容器采用哈希表实现，利用拉链法解决冲突，所有元素都是无序排列的。

函数	方法
empty()	判断容器是否为空
size()	返回容器的长度
count(k)	返回容器中关键字 k 出现的次数，结果为 0 或 1
find(k)	如果容器中存在关键字 k 的元素，返回其迭代器，否则返回 end()
insert(e)	插入元素 e
erase()	从容器中删除一个或几个元素
clear()	删除所有元素
begin()	返回当前容器中首元素的迭代器
end()	返回当前容器中尾元素后一个位置的迭代器

主要成员函数

unordered_map（哈希映射容器）

unordered_map 与 map 类似，每个元素都为 pair 类型，所有元素的关键字都是唯一的，只是 unordered_map 容器采用哈希表实现，利用拉链法解决冲突，所有元素都是无序排列的。

函数	方法
empty()	判断容器是否为空
size()	返回容器的长度
map[k]	返回关键字 k 的元素，当不存在时以 k 作为关键字插入一个元素
at[k]	同 map[k]
count(k)	返回容器中关键字 k 出现的次数，结果为 0 或 1
find(k)	如果容器中存在关键字 k 的元素，返回其迭代器，否则返回 end()
insert(e)	插入元素 e
erase()	从容器中删除一个或几个元素
clear()	删除所有元素
begin()	返回当前容器中首元素的迭代器
end()	返回当前容器中尾元素后一个位置的迭代器