# C++: Generic Algorithm Examples

Yao Yao on April 21, 2015
• Published in category
• C++

## 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)

#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(ostream, delimiter) & istream_iterator(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
*/


## 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;
}

}

int main() {
vector<int> intVector;
intVector.push_back(1);
intVector.push_back(2);
intVector.push_back(3);

vector<string> strVector;
strVector.resize(intVector.size());

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”。