变易算法 - STL算法

欢迎访问我的新博客:http://www.milkcu.com/blog/

原文地址:http://www.milkcu.com/blog/archives/mutating-algorithms.html

原创:变易算法 - STL算法

作者:MilkCu

摘要:C++ STL标准模板库在数据结构和算法的实践领域发挥着重要作用,极大的提高了开发效率。STL的三大组成部分为容器、迭代器、算法,本文主要讲解STL算法中的变易算法。本文从实践的角度简单介绍了一下函数原型和相关函数的使用。

引言

C++ STL的变易算法(Mutating Algorithms)是一组能修改容器元素数据的模板函数,可进行序列数据的复制、交换、替换、填充、移除、旋转、随机抖动、分割。这些算法函数对迭代器有较高要求,在应用时,先要检查容器的迭代器是否符合要求,防止产生编译错误。

元素复制算法

copy函数

该函数用于容器间元素拷贝,将迭代器区间[first, last)的元素复制到由复制目标迭代器result给定的区间[result, result + (last - first))。

函数原型如下:

template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)

注意:目标容器的容量要比待复制的内容大。

下面的示例程序将容器v中的内容复制到容器v2,并打印容器v2的元素。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(4);
v.push_back(3);
vector<int> v2(4);
v2.push_back(8);
copy(v.begin(), v.end(), v2.begin());
for_each(v2.begin(), v2.end(), print);
return 0;
}

结果输出为:

2 4 3 0 8

copy_backward函数

将一个迭代器区间的内容复制到另一迭代器区间,与copy()相似,不同的是复制过程从最后的元素开始。

函数原型如下:

template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result )

下面的示例程序将容器v的内容复制到容器v2中,从后往前复制。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(4);
v.push_back(3);
vector<int> v2(4);
v2.push_back(8);
copy_backward(v.begin(), v.end(), v2.end());
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

0 0 2 4 3

元素交换算法

swap函数

该函数的功能是实现两个元素的交换。虽然大多数容器内部都提供了swap函数,这里提供了更一般的迭代器形式。

函数原型如下:

template <class T> void swap ( T& a, T& b )

下面的示例程序用于交换两个整数并打印。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
int a = 2;
int b = 3;
swap(a, b);
cout << a << ", " << b << endl;
return 0;
}

输出结果为:

3, 2

iter_swap函数

iter_swap函数是swap函数的迭代器形式,使交换算法更易用于一般的容器。这个函数和上面的swap()有什么不同呢?

函数原型如下:

template <class ForwardIterator1, class ForwardIterator2>
void iter_swap (ForwardIterator1 a, ForwardIterator2 b)

下面的示例程序用于交换两个容器,并打印容器元素。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
vector<int> v2;
v.push_back(2);
v.push_back(3);
v2.push_back(7);
v2.push_back(8);
v2.push_back(9);
swap(v, v2);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

7 8 9

swap_ranges函数

该函数用于两个迭代器区间元素的交换。

函数原型如下:

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2)

下面的示例程序用于容器v与容器v2的前两个元素交换,并打印交换结果。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
vector<int> v2;
v.push_back(2);
v.push_back(3);
v2.push_back(7);
v2.push_back(8);
v2.push_back(9);
swap_ranges(v2.begin(), v2.end() - 1, v.begin());
for_each(v.begin(), v.end(), print);
cout << endl;
for_each(v2.begin(), v2.end(), print);
cout << endl;
return 0;
}

输出结果为:

7 82 3 9

transform函数

该函数用于容器元素的变换操作。有两个使用原型,分别用于一元函数对象和二元函数操作。

函数原型如下:

template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperation op) template <class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op)

下面的示例程序将容器v中的元素加倍,并输出元素的值。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int twice(int x) {
return 2 * x;
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(4);
vector<int> v2(v.size());
transform(v.begin(), v.end(), v2.begin(), twice);
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

4 8

元素替换算法

replace函数

该函数用于将指定函数值替换为新值。

函数原型如下:

template <class ForwardIterator, class T>
void replace (ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value)

下面的示例程序将容器v中值为5的元素的值替换为6。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(5);
v.push_back(8);
replace(v.begin(), v.end(), 5, 6);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

3 6 8

replace_if函数

该函数是replace函数的谓词判断版本,将满足谓词条件的元素替换为新值。

函数原型如下:

template <class ForwardIterator, class UnaryPredicate, class T>
void replace_if (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred, const T& new_value )

下面的示例程序将容器v中值为偶数的元素的值替换为2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int odd(int x) {
return !(x % 2);
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(5);
v.push_back(8);
replace_if(v.begin(), v.end(), odd, 2);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

3 5 2

replace_copy函数

该函数先进行元素替换,再将元素复制到新容器。

函数原型如下:

template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy (InputIterator first, InputIterator last,
OutputIterator result, const T& val)

下面的示例程序将容器v中值为5的元素的值替换为6,并复制到容器v2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(5);
v.push_back(8);
vector<int> v2(v.size());
replace_copy(v.begin(), v.end(), v2.begin(), 5, 6);
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

3 6 8

replace_copy_if函数

该函数是replace_copy的一元谓词判断版本,用法相似。

函数原型如下:

template <class InputIterator, class OutputIterator, class UnaryPredicate, class T>
OutputIterator replace_copy_if (InputIterator first, InputIterator last,
OutputIterator result, UnaryPredicate pred,
const T& new_value)

下面的示例程序将容器v中值为偶数的元素的值替换为2,并复制到容器v2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int odd(int x) {
return !(x % 2);
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(5);
v.push_back(8);
vector<int> v2(v.size());
replace_copy_if(v.begin(), v.end(), v2.begin(), odd, 2);
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

3 5 2

元素填充算法

fill函数

该函数将同一个值填充到迭代器区间内。

函数原型如下:

template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val)

下面的示例程序将拥有5个元素的容器v全填充为9。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v(5);
fill(v.begin(), v.end(), 9);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

9 9 9 9 9

fill_n函数

与fill函数相似,但可指定填充的元素的个数。

函数原型如下:

template <class OutputIterator, class Size, class T>
void fill_n (OutputIterator first, Size n, const T& val)

下面的示例程序将容器v的前3个元素填充为9。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v(5);
fill_n(v.begin(), 3, 9);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

9 9 9 0 0

generate函数

该函数用于随机生成函数,将迭代器区间内的元素填充为生成的元素。

函数原型如下:

template <class ForwardIterator, class Generator>
void generate (ForwardIterator first, ForwardIterator last, Generator gen)

下面的程序将生成公比为3的等比数列。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int next(int x) {
return 2;
}
class Seq {
public:
int a;
Seq() {
a = 1;
}
inline int operator()() {
a *= 3;
return a;
}
};
int main(void) {
vector<int> v(5);
Seq seq;
generate(v.begin(), v.end(), seq);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

3 9 27 81 243

generate_n函数

该函数与generate相似,只是限定了填入容器的数值个数。

函数原型如下:

template <class OutputIterator, class Size, class Generator>
void generate_n (OutputIterator first, Size n, Generator gen)

下面的示例程序将容器v的前3个元素填充为伪随机数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
void print(int x) {
cout << x << " ";
}
int getRand(void) {
return (rand() % 100);
}
int main(void) {
vector<int> v(6);
srand(unsigned(time(0)));
generate_n(v.begin(), 3, getRand);
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

48 19 84 0 0 0

元素移除算法

remove函数

该函数用于将容器中等于某个给定值的元素全部移除掉,并返回表示容器结束位置的迭代器。

函数原型如下:

template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)

下面的示例程序将容器v中值为3的元素移除掉了,并把剩余元素打印出来。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(5);
vector<int> v2(4);
vector<int>::iterator result = remove(v.begin(), v.end(), 3);
for_each(v.begin(), result, print);
return 0;
}

输出结果为:

2 5

remove_if函数

该函数是remove函数的一个带谓词判断的版本,将满足一元谓词判断条件的元素移除掉。

函数原型如下:

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred)

下面的示例程序将容器v中值为偶数的元素移除掉了。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int isOdd(int x) {
return !(x % 2);
}
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(7);
v.push_back(8);
vector<int>::iterator result = remove_if(v.begin(), v.end(), isOdd);
for_each(v.begin(), result, print);
return 0;
}

输出结果为:

3 7

remove_copy函数

该函数先进行元素移除,再将元素复制到新容器,实质上是一个条件复制。

函数原型如下:

template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy (InputIterator first, InputIterator last,
OutputIterator result, const T& val)

下面的示例程序将容器v中值不为3的元素复制到新容器v2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(5);
vector<int> v2(4);
remove_copy(v.begin(), v.end(), v2.begin(), 3);
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

2 5 0 0

remove_copy_if函数

该函数是remove_copy的一个带谓词判断版本,将不满足一元谓词判断条件的元素复制到新容器。

函数原型如下:

template <class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator remove_copy_if (InputIterator first, InputIterator last,
OutputIterator result, UnaryPredicate pred)

下面的示例程序将容器v中值不是偶数的元素复制到新容器v2中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int isOdd(int x) {
return !(x % 2);
}
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(7);
v.push_back(8);
vector<int> v2(5);
remove_copy_if(v.begin(), v.end(), v2.begin(), isOdd);
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

3 7 0 0 0

unique函数

该函数用于剔除容器中连续重复的元素,只保留一个。有两个使用原型,可以使连续重复的原型,或不连续但满足二元谓词判断条件的元素。

函数原型如下:

template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first, ForwardIterator last) template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique (ForwardIterator first, ForwardIterator last,
BinaryPredicate pred)

下面的示例程序将容器v中连续重复元素剔除。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(5);
vector<int>::iterator result = unique(v.begin(), v.end());
for_each(v.begin(), result, print);
return 0;
}

输出结果为:

2 3 5

unique_copy函数

该函数用于复制不连续重复的元素。同样有两个使用原型。

函数原型如下:

template <class InputIterator, class OutputIterator>
OutputIterator unique_copy (InputIterator first, InputIterator last,
OutputIterator result) template <class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy (InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred)

下面的示例程序将容器v中连续重复元素剔除,并复制到新容器v2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(3);
v.push_back(5);
vector<int> v2(4);
unique_copy(v.begin(), v.end(), v2.begin());
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

2 3 5 0

元素旋转算法

reverse函数

该函数用于容器元素的反向排列。

函数原型如下:

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last)

下面的示例程序将容器v中的元素反向排列并打印。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(5);
reverse(v.begin(), v.end());
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

5 3 2

reverse_copy函数

该函数用于反向复制容器元素。

函数原型如下:

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy (BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result)

下面的实例程序将容器v中的元素反向复制到新容器v2中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(5);
vector<int> v2(v.size());
reverse_copy(v.begin(), v.end(), v2.begin());
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

5 3 2

rotate函数

该函数用于旋转某个迭代器区间的元素。

假设区间元素为{a0, a1, ..., ak, ..., an},ak为middle位置,则旋转复制后,新区间元素为{ak, ak+1, ..., an, a0, a1, ..., ak-1}。

函数原型如下:

template <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last)

下面的示例程序将容器v以值为7的元素为支点旋转。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i + 1);
}
rotate(v.begin(), find(v.begin(), v.end(), 7), v.end());
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

7 8 9 10 1 2 3 4 5 6

rotate_copy函数

该函数通过复制的方法实现旋转,比rotate函数更简单高效,但需要占用较多的内存空间。

函数原型如下:

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result)

下面的示例程序将以容器v中值为7的元素为支点旋转,将结果存储在容器v2中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i + 1);
}
vector<int> v2(v.size());
rotate_copy(v.begin(), find(v.begin(), v.end(), 7), v.end(), v2.begin());
for_each(v2.begin(), v2.end(), print);
return 0;
}

输出结果为:

7 8 9 10 1 2 3 4 5 6

随机抖动算法

random_shuffle函数

该函数用于对容器元素进行随机的排列,有两个使用原型,使用C标准的伪随机函数rand或自定义的随机数发生器函数对象。

函数原型如下:

template <class RandomAccessIterator>
void random_shuffle (RandomAccessIterator first, RandomAccessIterator last) template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& gen)

下面的示例程序将容器v中元素随机抖动2次并打印,其实这是一个伪随机抖动的过程。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i);
}
random_shuffle(v.begin(), v.end());
for_each(v.begin(), v.end(), print);
cout << endl;
random_shuffle(v.begin(), v.end());
for_each(v.begin(), v.end(), print);
return 0;
}

输出结果为:

8 1 9 2 0 5 7 3 4 6

7 0 6 3 2 8 1 4 5 9

容器分割算法

partition函数

该函数用于重新分割排列容器的元素,按照医院谓词判断条件,分割成满足和不满足条件的两部分,返回的迭代器指向首个不满足条件的元素。

函数原型如下:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred)

下面的示例程序将容器v中的元素分为小于5和大于等于5的两部分,并分别将元素打印出来。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int less5(int x) {
if(x < 5) {
return 1;
} else {
return 0;
}
}
int main(void) {
vector<int> v;
for(int i = 10; i > 0; i--) {
v.push_back(i);
}
vector<int>::iterator iv = partition(v.begin(), v.end(), less5);
cout << "less than 5: ";
for_each(v.begin(), iv, print);
cout << endl;
cout << "no less than 5: ";
for_each(iv, v.end(), print);
return 0;
}

输出结果为:

less than 5: 1 2 3 4

no less than 5: 6 5 7 8 9 10

stable_partition函数

该函数与parition类似,重新分割排列容器的元素,但可以保持原有元素的先后顺序。

函数原型如下:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred)

下面的示例程序也是将容器v中的元素分为小于5和大于等于5的两部分,但保持元素的稳定性。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int x) {
cout << x << " ";
}
int less5(int x) {
if(x < 5) {
return 1;
} else {
return 0;
}
}
int main(void) {
vector<int> v;
for(int i = 10; i > 0; i--) {
v.push_back(i);
}
vector<int>::iterator iv = stable_partition(v.begin(), v.end(), less5);
cout << "less than 5: ";
for_each(v.begin(), iv, print);
cout << endl;
cout << "no less than 5: ";
for_each(iv, v.end(), print);
return 0;
}

输出结果为:

less than 5: 4 3 2 1

no less than 5: 10 9 8 7 6 5

小结

本文主要介绍了STL算法库中的变易算法(Mutating Algorithms),是一些会使操作数据发生改变的算法,包括:

  • 元素复制算法:copy, copy_backward
  • 元素交换算法:swap, iter_swap, swap_ranges, transform
  • 元素替换算法:replace, replace_if, replace_copy, replace_copy_if
  • 元素填充算法:fill, fill_n, generate, generate_n
  • 元素移除算法:remove, remove_if, remove_copy, remove_copy_if, unique_copy, unique
  • 元素旋转算法:reverse, reverse_copy, rotate, rotate_copy
  • 随机抖动算法:random_shuffle
  • 容器分割算法:partition, stable_partition

这些函数均包含于头文件,本文给出的所有代码在VS2010中编译运行通过。

参考

[1] http://www.cplusplus.com/reference/algorithm/, - C++ Reference;

[2] C++ STL开发技术导引, 叶志军, 人民邮电出版社.

(全文完)

本文地址:http://www.milkcu.com/blog/archives/mutating-algorithms.html

http://blog.csdn.net/milkcu/article/details/23511631

推荐阅读:非变易算法 - STL算法 - MilkCu博客

STL非变易算法 - STL算法 - MilkCu的专栏

上一篇:[LintCode] Sort Integers II 整数排序之二


下一篇:JAVA随笔----浅谈lombok注解