正如所有的容器都建立在一致的设计模式上一样，算法也具有共同的设计基础。理解标准算法库的设计基础有利于学习和使用算法。C++ 提供了超过一百个算法，了解它们的结构显然要比死记所有的算法更好。
算法最基本的性质是需要使用的迭代器种类。所有算法都指定了它的每个迭代器形参可使用的迭代器类型。如果形参必须为随机访问迭代器则可提供vector 或 deque 类型的迭代器，或者提供指向数组的指针。而其他容器的迭代器不能用在这类算法上。
另一种算法分类的方法，，根据对元素的操作将算法分为下面几种：
• 只读算法，不改变元素的值顺序。
• 给指定元素赋新值的算法。
• 将一个元素的值移给另一个元素的算法。
大多数算法采用下面四种形式之一：
alg (beg, end, other parms);
alg (beg, end, dest, other parms);
alg (beg, end, beg2, other parms);
alg (beg, end, beg2, end2, other parms)
其中，alg 是算法的名字，beg 和 end 指定算法操作的元素范围。我们通常将该范围称为算法的“输入范围”。尽管几乎所有算法都有输入范围，但算法是否使用其他形参取决于它所执行的操作。这里列出了比较常用的其他形参：
dest、beg2 和 end2，它们都是迭代器。这些迭代器在使用时，充当类似的角色。除了这些迭代器形参之外，有些算法还带有其他的菲迭代器形参，它们是这些算法特有的。
list 容器上的迭代器是双向的，而不是随机访问类型。由于 list 容器不支持随机访问，因此，在此容器上不能使用需要随机访问迭代器的算法。这些算法包括 sort 及其相关的算法。还有一些其他的泛型算法，如 merge、remove、reverse 和 unique，虽然可以用在 list 上，但却付出了性能上的代价。如果这些算法利用 list 容器实现的特点，则可以更高效地执行。
如果可以结合利用 list 容器的内部结构，则可能编写出更快的算法。与其他顺序容器所支持的操作相比，标准库为 list 容器定义了更精细的操作集合，使它不必只依赖于泛型操作。下表 列出了 list 容器特有的操作，其中不包括要求支持双向或更弱的迭代器类型的泛型算法，这类泛型算法无论是用在list 容器上，还是用在其他容器上，都具有相同的效果。
| 类型 | 定义 |
|---|---|
| lst.merge(lst2) lst.merge(lst2, comp) | 将 lst2 的元素合并到 lst 中。 这两个 list 容器对象都必须排序。lst2 中的元素将被删除。合并后，lst2 为空。返回 void 类型。第一个版本使用 < 操作符，而第二个版本则使用 comp 指定的比较运算 |
| lst.remove(val) lst.remove_if(unaryPred) | 调用 lst.erase 删除所有等于指定值或使指定的谓词函数返回非零值的元素。返回 void 类型 |
| lst.reverse() | 反向排列 lst 中的元素 |
| lst.sort | 对 lst 中的元素排序 |
| lst.splice(iter, lst2) | |
| lst.splice(iter, lst2, iter2) | |
| lst.splice(iter, beg, end) | 将 lst2 的元素移到 lst 中迭代器 iter 指向的元素前面。在 lst2 中删除移出的元素。第一个版本将 lst2 的所有元素移到 lst 中；合并后，lst2 为空。lst 和 lst2 不能是同一个 list 对象。第二个版本只移动 iter2 所指向的元素， 这个元素必须是 lst2 中的元素。 在这种情况中， lst 和lst2 可以是同一个 list 对象。也就是说，可在一个 list对象中使用 splice 运算移动一个元素。第三个版本移动迭代器 beg 和 end 标记的范围内的元素。 beg 和 end 照例必须指定一个有效的范围。这两个迭代器可标记任意 list 对象内的范围，包括 lst。当它们指定 lst 的一段范围时，如果 iter 也指向这个范围的一个元素，则该运算未定义。 |
| lst.unique() lst.unique(binaryPred) | 调用 erase 删除同一个值的团结副本。第一个版本使用 ==操作符判断元素是否相等；第二个版本则使用指定的谓词函数实现判断 |
对于 list 对象，应该优先使用 list 容器特有的成员版本，而不是泛型算法。
大多数 list 容器特有的算法类似于其泛型形式中已经见过的相应的算法，但并不相同：
l.remove(val); // removes all instances of val from l
l.remove_if(pred); // removes all instances for which pred is truefrom l
l.reverse(); // reverses the order of elements in l
l.sort(); // use element type < operator to compare elements
l.sort(comp); // use comp to compare elements
l.unique(); // uses element == to remove adjacent duplicates
l.unique(comp); // uses comp to remove duplicate adjacent copies
list 容器特有的算法与其泛型算法版本之间有两个至关重要的差别。其中一个差别是 remove 和 unique 的 list 版本修改了其关联的基础容器： 真正删除了指定的元素。例如，list::unique 将 list 中第二个和后续重复的元素删除出该容器。
另一个差别是 list 容器提供的 merge 和 splice 运算会破坏它们的实参。使用 merge 的泛型算法版本时，合并的序列将写入目标迭代器指向的对象，而它的两个输入序列保持不变。但是，使用 list 容器的 merge 成员函数时，则会破坏它的实参 list 对象——当实参对象的元素合并到调用 merge 函数的list 对象时，实参对象的元素被移出并删除。
·1，打印输出
#include <iostream>
#include <vector>
#include <algorithm>
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);
}
//output: 2 0 2 2 0 4 0 1
2，求和、求积
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
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;
}
/*
output:
9 8 7 6 5 4 3 2 1
sum:45
product:362880
*/
3，将vector的所有元素设为0
#include <iostream>
#include <vector>
#include <algorithm>
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);
}
//output:0 0 0 0 0 0 0 0 0
4，transform（），类似于函数映射：y=2x+1
#include <iostream>
#include <vector>
#include <algorithm>
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);
}
//output:19 17 15 13 11 9 7 5 3
5，排序sort（）
#include <iostream>
#include <vector>
#include <algorithm>
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);
std::cout<<std::endl;
std::for_each(v.begin(), v.end(), PrintFunc);
}
/*
output:
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
*/
6，去除重复值
#include <iostream>
#include <vector>
#include <algorithm>
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);// 打印结果
}
//output: 0 1 2 4
| 迭代器 | 支持 | 典型应用 |
|---|---|---|
| 输入迭代器 （InputIterator） | 可读，可递增 | find 算法 |
| 输出迭代器（OutputIterator） | 可写，可递增 | copy 算法 |
| 前向迭代器（ForwardIterator） | 可读写，可递增 | replace 算法 |
| 双向迭代器（BidirectionalIterator） | 可读写，可递增递减 | reverse 算法 |
| 随机访问迭代器（RandomAccess） | 可读写，可增减一个整数 | sort 算法 |
7，查找find（）
#include <iostream>
#include <vector>
#include <algorithm>
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;
}
}
//output: x does not contain
8，复制copy（）
#include <iostream>
#include <vector>
#include <algorithm>
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 <iostream>
#include <vector>
#include <algorithm>
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 <iostream>
#include <vector>
#include <algorithm>
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
*/
11，first 到 last 的路程
一些算法会根据迭代器类型的不同引入相应的优化：如 distance 算法。
#include <iostream>
#include <vector>
#include <algorithm>
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;
}
//output: distance(first, last) = 8
网友评论