C++泛型算法_C_内存溢出

文章目录

- - - 泛型算法
    - - 例1：打印输出
      - 泛型算法的分类
      - 例2：求和、求积
        例3：将vector的所有元素设为0
        例4：transform（），类似于函数映射：y=2x+1
        例5：排序sort（）
        例6：去除重复值
      - 迭代器的分类
      - 例7：查找find（）
        例8：复制copy（）
        例9：替换replace（）
        例10：逆转reverse（）
        例子11：`first` 到 `last` 的路程
      - 一些特殊的迭代器

泛型算法

泛型算法：可以支持多种类型的算法
这里重点讨论 C++ 标准库中定义的算法

●

例1：打印输出

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::for_each(v.cbegin(), v.cend(), PrintFunc);
}

结果：

2 0 2 2 0 4 0 1

为什么要引入泛型算法而不采用方法的形式

内建数据类型不支持方法
计算逻辑存在相似性，避免重复定义

如何实现支持多种类型：使用迭代器作为算法与数据的桥梁

泛型算法通常来说都不复杂，但优化足够好
一些泛型算法与方法同名，实现功能类似，此时建议调用方法而非算法

std::find V.S. std::map::find

泛型算法的分类

读算法：给定迭代区间，读取其中的元素并进行计算

accumulate / find / count

例2：求和、求积

#include 
#include 
#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 9,8,7,6,5,4,3,2,1 };
	std::for_each(v.begin(), v.end(), PrintFunc);
	int sum = std::accumulate(v.begin(), v.end(), 0);
	int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
	std::cout <<"\nsum:" << sum << std::endl;
	std::cout << "product:" << product << std::endl;
}

结果：

9 8 7 6 5 4 3 2 1
sum:45
product:362880

写算法：向一个迭代区间中写入元素

单纯写 *** 作： fill / fill_n
读 + 写 *** 作：transform / copy
注意：写算法一定要保证目标区间足够大

例3：将vector的所有元素设为0

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 9,8,7,6,5,4,3,2,1 };
	std::fill(v.begin(), v.end(), 0);//将vector的所有元素设为0
	std::for_each(v.begin(), v.end(), PrintFunc);
}

结果：

0 0 0 0 0 0 0 0 0

例4：transform（），类似于函数映射：y=2x+1

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}
int Add(int x) {
	return 2*x+1;
}

int main() {
	std::vector<int> v = { 9,8,7,6,5,4,3,2,1 };
	std::vector<int> u(9);
	std::transform(v.begin(), v.end(),u.begin(),Add);
	std::for_each(u.begin(), u.end(), PrintFunc);
}

结果：

19 17 15 13 11 9 7 5 3

排序算法：改变输入序列中元素的顺序

sort / unique

例5：排序sort（）

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 9,8,7,6,5,4,3,2,1 };
	std::sort(v.begin(), v.end());
	std::for_each(v.cbegin(), v.cend(), PrintFunc);
}

结果：

1 2 3 4 5 6 7 8 9

例6：去除重复值

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::sort(v.begin(), v.end()); // 先排序
	auto last = std::unique(v.begin(), v.end());// 删除相邻重复元素
	v.erase(last, v.end());//删除多余元素
	std::for_each(v.begin(), v.end(), PrintFunc);// 打印结果
}

结果：

0 1 2 4

迭代器的分类

泛型算法使用迭代器实现元素访问

迭代器	支持	典型应用
输入迭代器（InputIterator）	可读，可递增	find 算法
输出迭代器（OutputIterator）	可写，可递增	copy 算法
前向迭代器（ForwardIterator）	可读写，可递增	replace 算法
双向迭代器（BidirectionalIterator）	可读写，可递增递减	reverse 算法
随机访问迭代器（RandomAccessIterator）	可读写，可增减一个整数	sort 算法

例7：查找find（）

#include 
#include 
#include 

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	int x = 5;
	auto result1 = std::find(v.begin(), v.end(),x);
	if (result1 == v.end()) {
		std::cout << "x does not contain" << std::endl;
	}
	else{
		std::cout << *result1 << std::endl;
	}	
}

结果：

x does not contain

例8：复制copy（）

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::vector<int> u(8);
	std::cout << "v:" << std::endl;
	std::for_each(v.begin(), v.end(), PrintFunc);

	std::copy(v.begin(), v.end(), u.begin());
	std::cout << "\nu:" << std::endl;
	std::for_each(u.begin(), u.end(), PrintFunc);
}

结果：

v:
2 0 2 2 0 4 0 1
u:
2 0 2 2 0 4 0 1

例9：替换replace（）

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::vector<int> u(8);
	std::cout << "before v:" << std::endl;
	std::for_each(v.begin(), v.end(), PrintFunc);

	std::replace(v.begin(), v.end(), 0,8);
	std::cout << "\nafter v:" << std::endl;
	std::for_each(v.begin(), v.end(), PrintFunc);
}

结果：

before v:
2 0 2 2 0 4 0 1
after v:
2 8 2 2 8 4 8 1

例10：逆转reverse（）

#include 
#include 
#include 

void PrintFunc(int x) {
	std::cout << x << " ";
}

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::vector<int> u(8);
	std::cout << "before v:" << std::endl;
	std::for_each(v.begin(), v.end(), PrintFunc);

	std::reverse(v.begin(), v.end());
	std::cout << "\nafter v:" << std::endl;
	std::for_each(v.begin(), v.end(), PrintFunc);
}

结果：

before v:
2 0 2 2 0 4 0 1
after v:
1 0 4 0 2 2 0 2

● 一些算法会根据迭代器类型的不同引入相应的优化：如 distance 算法

例子11：first 到 last 的路程

#include 
#include 
#include 

int main() {
	std::vector<int> v = { 2,0,2,2,0,4,0,1 };
	std::cout << "distance(first, last) = " 
		<<std::distance(v.begin(),v.end())
		<< std::endl;
}