C++——STL算法_c++ stl算法

STL一些算法

像sotr(), copt(), find(), random_shuffle(), set_union, transform()等等，前面的博客已经介绍过了。

 C++——STL(标准模板库)_JAN6055的博客-CSDN博客https://blog.csdn.net/JAN6055/article/details/122746708?spm=1001.2014.3001.5501

C++——STL容器_JAN6055的博客-CSDN博客https://blog.csdn.net/JAN6055/article/details/122758690?spm=1001.2014.3001.5501

C++——仿函数_JAN6055的博客-CSDN博客https://blog.csdn.net/JAN6055/article/details/122766140?spm=1001.2014.3001.5501

 对于算法函数的设计，有两个通用的部分。

首先，用模板类提供泛型。

其次，用迭代器来表示容器访问数据的通用表示。

得益于此，STL算法通用性很强，适用于各种数据结构，小到数组，大到容器。

算法分类

STL算法分为四个部分

非修改序列操作

不修改容器中的内容，例如for_each()

修改序列操作

可以修改值或者修改顺序，例如transform(), random_shuffle()等

排序和相关操作

例如sort()等

通用数字运算

计算一些数学运算等，像两个容器的内部乘积，计算相邻对象差等等

前三组定义在<algorithm>头文件中最后一组定义在<numeric>中

按存放的位置来说

存放再原容器的叫就地算法

例如sort()

创建拷贝或者复制的叫复制算法

例如copy() 
有些算法可能会有两个版本STL的约定是，复制版本的名称以_copy结尾

或者有些函数有这样的版本，根据函数应用于容器的元素得到的结果来执行操作

这些版本通常以_if结尾

next_permutation() —— 关于排列组合的算法，将算法区间的内容转换为下一种排列方式。对于字符串，按照递增的方式进行，因此，如果要进行全排列，应该传入特定的顺序，如果区间已经处于最终的顺序，返回false,否则返回true。

例如8的全排列

int main()
{
    //注意：ACSII码是依次递增的
    string str = "12345678";
    while(next_permutation(str.begin(), str.end())){
        cout << str << endl;
    }
    return 0;
}

顺便一说，这个函数自会提供唯一的排列组合，即相同的排列组合不会出现两次

int main()
{
    string str = "all";
    while(next_permutation(str.begin(), str.end())){
        cout << str << endl;
    }
    return 0;
}

运行结果

 函数和容器方法

有时候，在处理某些情况的时候可能会有两种选择，用STL函数或者容器内集成的方法。假设要在链表中删除val = 4的元素，可以这样做

ostream & operator<<(ostream & os, list<int> & ls)
{
    ostream_iterator<int,char> out (cout, " ");
    copy(ls.begin(), ls.end(),out);
    return os;
}
int main()
{
    list <int> ls= {9,5,4,4,3,2,6,4,8,10,15}; //with C++ 11
    ls.remove(4);
    cout << "use list<int>::remove( & val = 4) result is : " << endl << ls;
    return 0;
}

上述的方法将自动调整链表长度

或者用STL函数

remove()——其接受三个参数，前两个是两个容器的迭代器，表示要删除的区间，最后一个表示要删除的值，但并不能自动调整大小，只是将未删除的元素放在前面覆盖，剩下的元素不变，并且返回删除后的超尾迭代器(不是原来容器中的超尾)。

int main()
{
    list <int> ls= {9,5,4,4,3,2,6,4,4,43,4}; //with C++ 11
    cout << "before list is : " << ls << endl;
    auto last =remove(ls.begin(), ls.end(),4);
    cout << "use std::remove result is : " << endl << ls << endl;
    ls.erase(last,ls.end());
    cout << "use erase : " << ls;
    return 0;
}

运行结果

STL与string

虽然string不是STL中的一元，但是某些方法也提供了STL的接口，像

begin()

end()

rbegin()

rend()

只要接口适配，也能应用STL的一些算法

 简单的使用STL

假设我们要让用户输入单词（假设只存储小写，即大写转小写），得到一个排好序的表（单词不重复），并且统计每个单词出现的次数

首先，保存单词很简单，vector

排序，可以用sotr，但这是就地算法，我们不希望改变原来的表，那么直接可以用另一个set来存储，因为其初始化的时候自动排序，同样方便查找

存储每个单词对应其出现的次数可以用pair来存入map中

map支持像这样的访问

["some thing"]

可以用其来简化代码

#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
//这样做的原因是tolower的函数原型是 int tolower (int),有些编译器可能不支持传入字符
char toLower(char ch) { return tolower(ch); }
string  & ToLower(string & st);
//注意这里必须是const，因为set里面的数据看作常量，不能修改，而且C++不允许将const 转换为非const
void display(const string & st);
int main()
{
    vector<string> words;
    cout << "输入单词直到quit结束：\n";
    string input;
    while( (cin >> input) && (input!="quit") ){
        words.push_back(input);
    }
    cout << "现在表中的数据是:\n";
    for_each(words.begin(), words.end(), display);
    cout << endl;
    set <string> wordset;
    transform(words.begin(), words.end(), insert_iterator< set<string> > (wordset,wordset.begin()), ToLower);
    cout << "排好序的表为：\n";
    for_each(wordset.begin(), wordset.end(), display);
    //string is key, int is data
    map <string,int> wordmap;
    set <string>::iterator it;
    for(it=wordset.begin();it != wordset.end();it++){
        //刚开始是空的，没有自动添加，*it是字符串
        wordmap[*it] = count(words.begin(), words.end(),*it);
    }
    cout << "表中单词出现的次数为: \n" << endl;
    //这里不能用for_each(), 因为map的底层模板类是pair, 并且没有对<< 进行重载
    for(it = wordset.begin(); it != wordset.end(); it++){
        cout << *it << ":" << wordmap[*it] << endl;
    }
    return 0;
}
 
string & ToLower(string & s)
{
    //再一次解释这个函数
    //转换：将前两个迭代器区间内的内容应用与仿函数并复制到区间的某一个位置
    transform(s.begin(), s.end(),s.begin(), toLower);
    return s;
}
void display(const string & st)
{
    cout << st << endl;
}

运行结果

输入单词直到quit结束：
hello
world
apple
banana
int
double
int
int
hello
nihao
apple
quit
现在表中的数据是:
hello
world
apple
banana
int
double
int
int
hello
nihao
apple

排好序的表为：
apple
banana
double
hello
int
nihao
world
表中单词出现的次数为: 

apple:2
banana:1
double:1
hello:2
int:3
nihao:1
world:1