STL泛型算法

目录

泛型算法概述

STL定义了一组泛型算法(generic algorithm),大多数算法都定义在头文件algorithm中,还有一组数值泛型算法定义在头文件numeric

泛型算法可以用于不同类型的元素和多种容器类型,所以称它们是"泛型的"

迭代器令泛型算法不依赖于容器,但依赖于元素类型的操作

※关键概念:泛型算法永远不会执行容器的操作

泛型算法本身不会执行容器的操作,它们只会运行与迭代器之上,甚至无需理会保存元素的是不是容器

泛型算法可能改变容器中保存元素的值,也可能在容器内移动元素,但永远不会改变底层容器的大小,添加或删除元素是容器/迭代器的工作,泛型算法自身永远不会做这样的操作

练习10.1:编写程序,读取int序列存入vector中,打印有多少个元素的值等于给定值

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	vector<int>vec = { 27,210,12,47,109,83 };
	int val = 83;
	cout << count(vec.cbegin(), vec.cend(), val) << endl;
	system("pause");
	return 0;
}

练习10.2:重做上一题,但读取string序列存入list中

#include<iostream>
#include<string>
#include<list>
#include<algorithm>
using namespace std;
int main() {
	list<string>lis = { "27","210","12","47","109","83" };
	string val = "83";
	cout << count(lis.cbegin(), lis.cend(), val) << endl;
	system("pause");
	return 0;
}

泛型算法的结构

只读算法

对于只读算法,通常最好使用cbegin()和cend()
如果计划使用算法返回的迭代器来改变元素的值,就需要使用begin()和end()

※泛型算法中的"泛型操作"必须对元素类型是可行的

例:对vec中的元素求和,和的初值是init_sum

vector<_Ty>vec;
accumulate(vec.cbegin(), vec.cend(), init_sum);

vec中的元素可以是int,或者是double、long long,或者其他任何可以加到_Ty上的类型

操作两个序列的算法一般只接受三个迭代器
例:equal用于确定两个序列是否保存相同的值

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

※确保泛型算法不会访问不存在的元素

那些只接受一个单一迭代器来表示第二个序列的算法,都假定第二个序列至少与第一个序列一样长
确保算法不会试图访问第二个序列中不存在的元素是程序员的责任

练习10.3:用accumulate求一个vector中的元素之和

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main() {
	vector<int>vec = { 27,210,12,47,109,83 };
	cout << accumulate(vec.cbegin(), vec.cend(), 0) << endl;
	system("pause");
	return 0;
}

练习10.4:假定v是一个vector< double >,那么调用accumulate(v.cbegin(), v.cend(), 0)有何错误?
调用accumulate(v.cbegin(), v.cend(), 0)等价于执行以下代码:

int sum = 0;
for (const int&val : v)
	sum += val;
return sum;

0是int型,sum += val;语句会发生强制类型转换,导致可能得不到预期结果

练习10.5:调用accumulate(v.cbegin(), v.cend(), string(""))会发生什么?(v = vector< string >)
调用结果为v中所有string元素首尾连接而成的string

写容器元素的算法

泛型算法不改变容器大小,所以使用这类算法时,必须确保序列原大小不小于要求算法写入的元素数目

例:将迭代器表示范围内的每个元素置为0

fill(vec.begin(), vec.end(), 0);

※泛型算法不检查写操作

泛型算法不检查写入位置是否合法,也不检查写操作本身是否合法

vector<int>vec;
fill_n(vec.begin(), 10, 0);

错误,vec是空的,写入位置不合法

vector<string>vec(10);
fill(vec.begin(), vec.end(), 3.14);

错误,string未定义double的转换构造函数,写操作不合法

back_insert_iterator和back_inserter

back_insert_iterator是插入迭代器(insert iterator)
通常通过迭代器想容器元素赋值时,值会被赋予迭代器指向的元素
通过插入迭代器赋值时,值会被添加到容器中

back_inserter是定义在头文件iterator中的一个函数
back_inserter接受一个容器引用,返回一个与该容器绑定的插入迭代器

vector<int>vec;					//空的vector
auto iter = back_inserter(vec);	//通过back_inserter获取与vec绑定的插入迭代器
*it = 42;						//vec中现在有一个元素,值为42
*it = 0;						//vec中现在有两个元素,分别是{42, 0}

通过上例可以发现,通过back_insert_iterator赋值不仅会向容器中添加元素,还会引起迭代器向后移动

通过插入迭代器使用泛型算法会改变容器的大小

vector<int>vec;					//空的vector
auto iter = back_inserter(vec);	//通过back_inserter获取与vec绑定的插入迭代器
fill_n(iter, 10, 0);			//添加10个元素到vec

上例是否违背了"泛型算法不改变容器大小"?
不违背,改变容器大小的不是泛型算法本身,而是插入迭代器,泛型算法的操作是基于迭代器的

拷贝算法(copy)

copy接受三个迭代器,前两个表示一个输入范围,第三个表示目的序列的起始位置
copy将输入范围中的元素拷贝到目的序列中

可以用copy实现内置数组的拷贝,代码如下:

int a1[] = { 0,1,2,3,4,5,6,7,8,9 };
int a2[sizeof(a1) / sizeof(*a1)];
auto ret = copy(begin(a1), end(a1), a2);

练习10.6:编写程序,使用fill_n将一个序列中的int值都设置为0

int arr[10];
fill_n(begin(arr), 10, 0);

练习10.7:下面的程序是否有错误?如果有,请改正
(a)

vector<int>vec;
list<int>lst;
int i;
while (cin >> i)
	lst.push_back(i);
copy(lst.cbegin(), lst.cend(), vec.begin());

错误,vec是空的,写操作不合法,改正如下:

list<int>lst;
int i;
while (cin >> i)
	lst.push_back(i);
vector<int>vec(lst.size());
copy(lst.cbegin(), lst.cend(), vec.begin());

(b)

vector<int>vec;
vec.reserve(10);	//reserve为容器预留空间
fill_n(vec.begin(), 10, 0);

错误,reserve方法为容器预留空间,但容器size外的预留空间同样是out_of_range的,改正如下:

vector<int>vec;
vec.resize(10);	//resize调整容器的大小
fill_n(vec.begin(), 10, 0);

练习10.8:“泛型算法不改变容器大小”,这句话在使用back_inserter时依然成立吗?
成立,改变容器大小的不是泛型算法本身,而是插入迭代器,泛型算法的操作是基于迭代器的

重排容器元素的算法

排序算法(sort)

sort算法可以依靠<运算符实现,凡是重载了<运算符的数据类型都可以利用sort排序
sort算法也可以依靠仿函数实现,详情戳sort仿函数

"删除"相邻重复元素(unique)

unique算法可以"删除"相邻重复元素,并返回一个指向不重复值范围末尾的迭代器,如

vector<int>vec = { 1,1,1,1,1,3,3,3,3,1,1, };
auto end = unique(vec.begin(), vec.end());
for (auto iter = vec.begin(); iter != end; iter++)
	cout << *iter << ' ';

输出结果:1 3 1

unique并不是真的删除元素,只是覆盖了相邻的重复元素,这符合"泛型算法不改变容器大小"
要真的删除元素,必须使用容器操作,如erase方法
*实验发现unique返回的迭代器以后的元素没有发生改变,猜测unique的实现方式类似于双指针

练习10.9:设计程序,消除vector< string >中重复的单词

void elimDups(vector<string>&words) {
	sort(words.begin(), words.end());
	auto end = unique(words.begin(), words.end());
	words.erase(end, words.end());
}

练习10.10:泛型算法为什么设计成不能直接改变容器大小?
1.泛型算法的所有操作被迭代器隔离的,这使泛型算法不依赖于容器,使泛型算法具有普适性
2.如果泛型算法可以直接改变容器大小,这会导致算法对容器类型有依赖性,这就破坏了泛型算法的普适性

上一篇:word2vec方法代码学习


下一篇:SpringBoot图片上传demo