最近评论
正在载入评论列表...
7.4 算法
STL算法库包含下列4类算法：
?排序算法；
?不可变序算法；
?变序性算法；
?数值算法。
这些算法通常使用迭代器访问由给定类型进行实例化的容器。在效率方面，这些算法可以与一些专用代码相媲美。
7.4.1 排序算法
排序算法包括通用排序、归并、按字典顺序比较、排序、二分查找以及一些类似的操作。这些算法使用了operator<()对象或Compare对象，并且通常需要使用随机访问迭代器。
下面的程序使用了STL的algorithm库中的快速排序函数sort()，对[d,e)区间的元素
排序。
文件 stl_sort1.cpp
// Using sort() from STL
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5;
int main()
{
int d[N], i, *e = d + N;
for (i = 0; i < N; ++i)
d[i] = rand();
sort(d, e);
for (i = 0; i < N; ++i)
cout << d[i] << '\t';
cout << endl;
}
这是对算法库中sort算法的最直接的应用，它作用于内置类型的数组d[]上，并使用普通的指针值作为迭代器。表7-13至表7-17中列出了一些排序算法。
表7-13 STL 与排序相关的库函数
sort(b,e) 对[b,e)区间的元素快速排序
sort(b,e,comp) 使用comp作为排序条件，对[b,e)区间的元素快速排序
stable_sort(b,e) 对[b,e)区间的元素稳定排序。在稳定排序中，相等的元素仍然保持原来的相对顺序
partial_sort(b,m,e) 对[b,e)区间的元素局部排序，使[b,m)区间的元素保持有序
partial_sort_copy 对[b,e)区间的元素局部排序。从输入迭代器区间取出要排序的元
(b,e,result_b,result_e) 素，并将其复制到随机访问迭代器区间和输入迭代器区间中较小的区间
nth_element(b,n,e) 按照第n个位置的元素对[b,e)区间的全部元素排序，将[b,e)划分为两个区间。例如，如果选定了第5个位置，则4个最小的元素位于它的左边，剩下的元素位于它的右边，并且它们都大于或等于这个元素
merge(b1,e1,b2,e2,result_b) 合并[b1,e1)区间和[b2,e2)区间内的元素，起始位置为result_b
inplace_merge(b,m,e) 合并[b,m)区间和[m,e)区间内的元素，起始位置为b
表7-14 更多STL与 排序相关的库函数
binary_search(b, e, t) [b,e)区间包含t则返回true
lower_bound(b, e, t) 在保持原有区间顺序的同时，返回能插入t的第一个位置
upper_bound(b, e, t) 在保持原有区间顺序的同时，返回能插入t的最后一个位置
equal_range(b, e, t) 在保持原有区间顺序的同时，返回与t相等的值的区间的迭代器对
next_permutation(b, e) 按照排列组合中的下一个排列顺序，重新排列[b,e)区间的元素
prev_permutation(b, e) 按照排列组合中的上一个排列顺序，重新排列[b,e)区间的元素
lexicographical_compare 按照字典顺序比较两个序列，如果序列1小于序列2则返回true
(b1, e1, b2, e2)
表7-15 STL与排序相关的堆函数
push_heap(b, e) 将位置e的元素放入已存在的堆中
pop_heap(b, e) 交换位置e的元素和位置b的元素并且重建堆
sort_heap(b, e) 对堆进行排序
make_heap(b, e) 创建一个堆
表7-16 STL与排序相关的最大/最小函数
min(t1,t2) 返回引用调用参数t1和t2中的最小值
max(t1,t2) 返回t1和t2中的最大值
min_element(b,e) 返回最小值的位置
max_element(b.e) 返回最大值的位置
表7-17 STL与排序相关的集合函数
set_union (b1, e1, b2, e2, r) 使用输出迭代器r返回两个集合的并集
set_intersection (b1, e1, b2, e2, r) 使用输出迭代器r返回两个集合的交集
set_difference (b1, e1, b2, e2, r) 使用输出迭代器r返回两个集合的差
set_symmetric_difference(b1, e1, b2, e2, r) 使用输出迭代器r返回两个集合的对称差
这些算法都使用Compare对象代替了operator<()，如下所示：
template<class RandAcc, class Compare>
void sort(RandAcc b, RandAcc e, Compare comp);
下面是另外一个排序的例子：
文件 stl_sort2.cpp
#include <iostream>
#include <algorithm>
using namespace std;
// Using sort() from STL
// Class MyLess works for any class T that has
// operator<() defined
template<class T>
class MyLess {
public:
bool operator()(const T& obj1, const T& obj2)
{ return obj1 < obj2; }
};
// Function MyGreater works for any class T with
// operator>() defined
template<class T>
bool MyGreater (const T& obj1, const T& obj2)
{ return obj1 > obj2; }
const int N = 5;
int main()
{
int i, d[N], *e = d + N;
MyLess<int> MyLessObj;
for (i = 0; i < N; ++i)
d[i] = rand()%100;
sort(d, e, MyLess<int>()); // use comparison class
for (i = 0; i < N; ++i)
cout << d[i] << '\t';
cout << endl;
sort(d, e, MyGreater<int>); // use comparison func
for (i = 0; i < N; ++i)
cout << d[i] << '\t';
cout << endl;
sort(d, e, MyLessObj); // use comparison method
for (i = 0; i < N; ++i)
cout << d[i] << '\t';
cout << endl;
}
7.4.2 不可变序算法
不可变序算法不修改它们所操作的容器的内容，一种典型的不可变序操作是在容器内查找一个特殊的元素并返回该元素的位置。
下面的程序使用了algorithm库中的不可变序函数find()查找元素t的位置。
文件 stl_find.cpp
// Use of the find function
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
string words[5] = { "my", "hop", "mop", "hope","cope"};
string* where;
where = find(words, words + 5, "hop");
cout << *++where << endl; // mop
sort(words, words + 5);
where = find(words, words + 5, "hop");
cout << *++where << endl; // hope
}
stl_find 程序解析
■ #include <algorithm>
algorithm头文件中声明了许多STL标准泛型算法。
■ string words[5] = { "my", "hop", "mop", "hope","cope"};
string* where;
通常，基本数组可以和STL算法一起使用，并且可将其看作随机访问容器。
■ where = find(words, words + 5, "hop");
这段程序使用find()查找单词hop的位置。
■ cout << *++where << endl; // mop
在给定的数组中hop之后的单词是mop。
■ sort(words, words + 5);
where = find(words, words + 5, "hop");
cout << *++where << endl; // hope
在对数组words[]进行排序后，hop之后的单词是hope。
表7-18列出了一些上述算法中使用的库函数。algorithm库中的其他算法及其功能如表
7-19所示。
表7-18 STL不可变序库函数
find(b, e, t) 在[b,e)区间查找t的位置
find(b, e, p) 在[b,e)区间查找使谓词p为真的第一个元素的位置；若未找到则返回e的位置
表7-19 STL中其他不可变序库函数
count(b, e, t, n) 返回[b,e)区间与t相等的元素的个数n
count_if(b, e, p, n) 返回[b,e)区间使谓词p为真的元素的个数n
adjacent_find(b, e) 返回与邻近元素值相等的第一个元素的位置；否则返回e
adjacent_find(b, e, bp) 返回与邻近元素值满足二元谓词bp的第一个元素的位置；否则返回e
mismatch(b1, e1, b2) 返回指示从b1和b2开始的两个序列中第一对不匹配元素的位置的迭代器对
mismatch (b1, e1,b2, bp) 同上，使用二元谓词关系bp代替相等关系
equal(b1, e1, b2) 如果从b1和b2开始的两个序列中的元素相等则返回ture；否则返回false
equal (b1, e1, b2, bp) 同上，使用二元谓词关系bp代替相等关系
search(b1, e1, b2, e2) 第二个序列包含在第一个序列中时，返回当前迭代器；否则返回e1
search(b1, e1, b2, e2, bp) 同上，使用二元谓词关系bp代替相等关系
7.4.3 变序性算法
变序性算法可以修改它们所操作的容器的内容，一种典型的变序操作是将容器的内容全部反序。
下面的程序使用了变序性函数reverse()和copy()，程序中要使用vector和algorithm库。
文件 stl_reverse.cpp
// Use of mutating copy and reverse
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
string first_names[5] = {"laura", "ira",
"buzz", "debra", "twinkle"};
string last_names[5] = {"pohl", "pohl",
"dolsberry", "dolsberry", "star"};
vector<string> names(first_names, first_names+5);
vector<string> names2(10);
vector<string>::iterator p;
copy(last_names, last_names + 5, names2.begin());
copy(names.begin(), names.end(), names2.begin()+5);
reverse(names2.begin(), names2.end());
for (p = names2.begin(); p != names2.end(); ++p)
cout << *p <<'\t';
cout << endl;
}
第一次调用变序函数copy()将last_names放入容器vector names2中；第二次调用copy()将first_name复制给names2（vector names的构造函数使用了first_names）。函数reserse()将所有的元素反序并打印输出。
表7-20列出了一些变序性算法的库函数。
表7-20 STL变序库函数
copy(b1,e1,b2) 将[b1,e1)区间内的元素复制到从b2开始的目标区间，返回目标区间最后一个被复制元素的下一位置
copy_backward(b1,e1,b2) 将[b1,e1)区间内的元素复制到从b2开始的目标区间，复制时由e1和b2开始反序进行，返回目标区间最后一个被复制元素的下一位置，即b2-(e1-b1)
for_each(b, e, f) 将函数f作用于[b,e)区间的每个元素
reverse(b, e) 将[b,e)区间的全部元素反序放置
reverse_copy(b1,e1, b2) 将[b1,e1)区间的元素反序复制到以b2开始的目标区间，返回目标区间最后一个被复制元素的下一位置，即b2+(e1-b1)
unique(b, e) 移除[b,e)区间内相邻的重复元素，函数返回最后一个未被移除的元素的下一位置
其他库函数在表7-21中进行了简单描述。
表 7-21 STL 变序库函数
unique(b, e, bp); 移除[b,e)区间内满足二元谓词关系bp的相邻的重复元素，函数返回最后一个未被移除的元素的下一位置。
unique_copy(b1, e1,b2) 将[b1,e1)区间内的元素复制到以b2开始的区间，并移除重复元素
unique_copy(b1, e1,b2, bp) 将[b1,e1)区间内的元素复制到以b2开始的区间，并移除满足二元谓词关系bp的重复元素
next_permutation(b, e) 按照排列组合中的下一个排列顺序，重新排列[b,e)之间的元素
prev_permutation(b, e) 按照排列组合中的上一个排列顺序，重新排列[b,e)之间的元素
swap(t1, t2) 交换t1和t2
iter_swap(b1, b2) 交换迭代器指向的位置
;;swap_range(b1, e1, b2) 交换[b1,e1)区间内的元素和从b2开始的区间的元素，返回b2 + (e1 - b1)
transform(b1, e1, b2, op) 对[b1,e1)区间的每一个元素调用一元运算符op，结果放置在b2开始的目标区间，返回目标区间最后一个被转换的元素的下一位置
transform(b1, e1, b2,b3, bop) 将二元运算符bop作用于[b1,e1)区间和从b2开始的区间的对应元素上，结果放置在b3开始的目标区间，返回目标区间最后一个被转换的元素的下一位置
replace(b, e, t1, t2) 将[b,e)区间内值为t1的元素的值替换为t2
replace_if(b, e, p, t2) 将[b,e)区间内满足谓词p的元素的值替换为t2
replace_copy(b1, e1, b2, t1, t2) 将[b1,e1)区间内的元素复制到从b2开始的区间，并将值为t1的元素的值替换为t2
replace_copy_if(b1, e1, b2, p, t2) 将[b1,e1)区间内的元素复制到从b2开始的区间，并将满足谓词p的元素的值替换为t2
remove(b, e, t) 删除[b,e)区间内值为t的元素
remove_if(), 除了要删除的值不同外，其他功能与remove()一致
remove_copy(),
remove_copy_if()
fill(b, e, t) 将t赋值给[b,e)区间的每一个元素
fill_n(b, n, t) 将t赋值给从b开始的n个元素
generate (b, e, gen) 使用生成器gen产生新值，并将其赋值给[b,e)区间的每一个元素
generate_n (b, n, gen) 使用生成器gen产生新值，并将其赋值给从b开始的n个元素
rotate(b, m, e) 将[b,e)区间的元素向左侧旋转，位置i上的元素旋转至(i+n-m)%n，其中n是区间的大小，m是中间位置，b是起始位置
rotate_copy(b1, m, e1, b2) 同上，但将结果复制到b2开始的区间
random_shuffle(b, e) 打乱元素顺序
random_shuffle(b, e, rand) 使用随机数生成器rand提供的随机数打乱元素顺序
partition (b, e, p) 将[b,e)区间的元素分区，令满足谓词p的元素全部位于不满足谓词p的元素之前
stable_partition(b, e, p) 同上，但是保留相对次序
7.4.4 数值算法
数值算法包括求和、计算内积和临差。下面的程序中，numeric库函数accmulate()执行向量求和操作，inner_product()执行向量内积操作。
文件 stl_numeric.cpp
// Vector accumulation and inner product
#include <iostream>
#include <numeric>
using namespace std;
int main()
{
double v1[3] = { 1.0, 2.5, 4.6 },
v2[3] = { 1.0, 2.0, -3.5 };
double sum, inner_p;
sum = accumulate(v1, v1 + 3, 0.0);
inner_p = inner_product(v1, v1 + 3, v2, 0.0);
cout << "sum = " << sum << ", product = "
<< inner_p << endl;
}
程序的输出如下：
str_numeric 程序解析
■ #include <numeric>
这是STL泛型数值算法的头文件。
■ sum = accumulate(v1, v1 + 3, 0.0);
这里实现了预期的数值操作+。accumulate算法的前两个参数提供求和计算的起始位置和末尾位置，第三个参数提供求和的初始值（一般为0.0）。本例中在double型数组v1[]中添加了三个初始元素。
■ inner_p = inner_product(v1, v1 + 3, v2, 0.0);
这个函数实现了预期的数值操作+和*。inner_product算法的前两个参数提供第一个序列的起始位置和末尾位置，第三个参数提供第二个序列的起始位置，第四个参数通常为0.0并且是内积运算的起始值。两个序列中的每个对应位置相乘求和以产生内积。本例使用下式计算：
v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]
表7-22中列出了一些数值算法库函数。
表7-22 STL数值算法库函数
accumulate(b, e, t) 计算[b,e)区间中的所有元素的总和，并与t累加
accumulate(b, e, t, bop) 对[b,e)区间中的所有元素进行累加操作bop(sum, element)，并将结果与t累加
inner_product(b1, e1, b2, t) 返回从b1和b2开始的两个区间的内积，t表示内积结果，初值通常为0
inner_product (b1,e1,b2,t, bop1, bop2) 使用bop1求和，bop2进行乘法运算，返回两个区间的内积
partial_sum(b1, e1, b2) 为[b1,e1)区间中的每个元素依次计算从b1开始到当前元素的累加和，并将结果写入从b2开始的目标区间
partial_sum(b1, e1, b2, bop) 同上，使用bop实现累积
adjacent_difference(b1, e1, b2) 计算[b1,e1)区间中两个相邻元素的差，并将结果写入从b2开始的目标区间
adjacent_difference(b1, e1, b2, bop) 同上，使用bop计算相邻元素的差
图书导读
