C++: Generic Algorithm Examples
整理自：Thinking in C++, Volume 2
1. copy(a.begin, a.end, b.begin) / equal(a.begin, a.end, b.begin) / back_inserter(vector)
#include <algorithm>
#include <cassert>
#include <cstddef> // For size_t
using namespace std;
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
int b[SIZE];
copy(a, a + SIZE, b);
for(size_t i = 0; i < SIZE; ++i)
assert(a[i] == b[i]);
// assert(equal(a, a + SIZE, b)); // equivalent
}
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>
using namespace std;
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
vector<int> v1(a, a + SIZE);
vector<int> v2(SIZE);
copy(v1.begin(), v1.end(), v2.begin());
assert(equal(v1.begin(), v1.end(), v2.begin()));
}
As with the example earlier, it’s important that v2 have enough space to receive a copy of the contents of v1. For convenience, a special library function, back_inserter(v2), which returns a special type of iterator that inserts elements to v2, may be used to expand memory as needed.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <vector>
using namespace std;
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
vector<int> v1(a, a + SIZE);
vector<int> v2; // v2 is empty here
copy(v1.begin(), v1.end(), back_inserter(v2));
assert(equal(v1.begin(), v1.end(), v2.begin()));
}
The implementation of copy() looks like the following code:
template<typename Iterator>
void copy(Iterator begin, Iterator end, Iterator dest) {
while(begin != end)
*begin++ = *dest++;
}
Whichever argument type you use in the call, copy() assumes it properly implements operator* and operator++. If it doesn’t, you’ll get a compile-time error.
2. remove_copy_if(a.begin, a.end, b.begin, predicateA) / remove_copy_if(a.begin, a.end, b.begin, predicateA, replacement) / replace_if(a.begin, a.end, predicateA, replacement)
先来个例子看下什么叫 predicate。注意这里 predicate 是 noun，读作 /’predɪkət/，意思是谓语，(grammar) The part of the sentence (or clause) which states something about the subject or the object of the sentence.
#include <algorithm>
#include <cstddef>
#include <iostream>
using namespace std;
// You supply this predicate
bool gt15(int x) {
return x > 15;
}
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
int b[SIZE];
int* bEnd = remove_copy_if(a, a+SIZE, b, gt15);
int* bBegin = b;
while(bBegin != bEnd)
cout << *bBegin++ << endl; // output: 10
}
predicate 简单说就是一个返回 true/false 的函数，用来检测集合中单个元素是否满足某个条件。
The remove_copy_if() algorithm applies gt15() to each element of a and ignores those elements where the predicate yields true when copying to b. 这个用法很有点像 R 的 apply family，又有点 a[a>15] 的意味。
接下来这两个例子应该就好懂了：
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
using namespace std;
// The predicate
bool contains_e(const string& s) {
return s.find('e') != string::npos;
}
int main() {
string a[] = {"read", "my", "lips"};
const size_t SIZE = sizeof a / sizeof a[0];
string b[SIZE];
string* bEnd = replace_copy_if(a, a + SIZE, b,
contains_e, string("kiss"));
string* bBegin = b;
while(bBegin != bEnd)
cout << *bBegin++ << endl;
}
// output:
/*
kiss
my
lips
*/
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
using namespace std;
bool contains_e(const string& s) {
return s.find('e') != string::npos;
}
int main() {
string a[] = {"read", "my", "lips"};
const size_t SIZE = sizeof a / sizeof a[0];
replace_if(a, a + SIZE, contains_e, string("kiss"));
string* p = a;
while(p != a + SIZE)
cout << *p++ << endl;
}
// output:
/*
kiss
my
lips
*/
3. count_if(a.begin, a.end, predicateA) / find(a.begin, a.end, target)
count_if(a.begin, a.end, predicateA) 返回容器 a 内满足条件 predicateA 的元素的个数：
#include <algorithm>
#include <cstddef>
#include <iostream>
using namespace std;
bool gt15(int x) {
return x > 15;
}
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
int aNumGt15 = count_if(a, a+SIZE, gt15);
cout << aNumGt15 << endl;
// output: 2
}
find(a.begin, a.end, target) 返回容器 a 内值为 target 的元素的指针，找到第一个时立刻返回；如果没有找到，返回 a.end：
#include <algorithm>
#include <cstddef>
#include <iostream>
using namespace std;
bool gt15(int x) {
return x > 15;
}
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
int* p = find(a, a + SIZE, 20);
cout << *p << endl;
// output: 20
}
4. ostream_iterator<T>(ostream, delimiter) / istream_iterator<T>(istream)
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
using namespace std;
bool gt15(int x) {
return x > 15;
}
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
remove_copy_if(a, a + SIZE,
ostream_iterator<int>(cout, "\n"), gt15);
// output: 10
}
Every time remove_copy_if() assigns an integer from the sequence a to cout through this iterator, the iterator writes the integer to cout and also automatically writes an delimiter (its second argument), which in this case “\n”.
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
using namespace std;
bool gt15(int x) {
return x > 15;
}
int main() {
ofstream ints("someInts.dat");
ints << "1 3 47 5 84 9";
ints.close();
ifstream inf("someInts.dat");
remove_copy_if(istream_iterator<int>(inf),
istream_iterator<int>(),
ostream_iterator<int>(cout, "\n"), gt15);
}
// output:
/*
1
3
5
9
*/
The first argument istream_iterator<int>(inf) attaches an istream_iterator object to the input file stream inf. The second argument istream_iterator<int>() uses the default constructor which builds a special istream_iterator that indicates EOF, so that when the first iterator finally encounters the end of the physical file, the algorithm is terminated correctly.
5. for_each(a.begin, a.end, func)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void print(int x) {
cout << x << endl;
}
int main() {
vector<int> intVector;
intVector.push_back(1);
intVector.push_back(2);
intVector.push_back(3);
for_each(intVector.begin(), intVector.end(), print);
// for_each(intVector.begin(), intVector.end(), ptr_fun<int, void>(print)); // equivalent
}
// output:
/*
1
2
3
*/
对，这就是 R 里面的 apply！
6. transform(a.begin, a.end, b.begin, func)
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void print(string x) {
cout << x << endl;
}
string addZero(int x) {
return to_string(x) + "0"; // MinGW 下 to_string 会有 bug
}
int main() {
vector<int> intVector;
intVector.push_back(1);
intVector.push_back(2);
intVector.push_back(3);
vector<string> strVector;
strVector.resize(intVector.size());
transform(intVector.begin(), intVector.end(), strVector.begin(), addZero);
for_each(strVector.begin(), strVector.end(), print);
}
// output:
/*
10
20
30
*/
transform(a.begin, a.end, b.begin, func) 的逻辑就是 “把从 a.begin 到 a.end 的每一个元素 a.i 传给 func，将 func(a.i) 依次存入 b”。
还有个复杂的版本是 transform(a.begin, a.end, b.begin, c.begin, func)，它的逻辑是 “把从 a.begin 到 a.end 的每一个元素 a.i，与 b.i 配对传给 func，将 func(a.i, bi) 依次存入 c”。
Comments