本篇接着前面stl变易算法（一）和stl变易算法（二）继续讲述变易算法。

这里将介绍完余下的变易算法，主要有：填充fill、n次填充fill_n、随机生成元素generate、随机生成n个元素generate_n、移除复制remove_copy、条件移除复制remove_copy_if、移除remove、条件移除remove_if、不连续反复元素复制unique_copy、剔除连续反复元素unique、元素反向reverse、反向复制reverse_copy及旋转rotate 。给出算法实现及实例。

填充fill

fill算法将同一个值填充到容器的一个或多个元素处，使用原型例如以下。将元素区间[first,last)上的元素所有填充为value值。

//fill算法函数的代码

template <class ForwardIterator, class T>

  void fill (ForwardIterator first, ForwardIterator last, const T& val)

{

  while (first != last) {

    *first = val;

    ++first;

  }

}
#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v(5);

    fill(v.begin(), v.end(), 30);

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

n次填充fill_n

相似于fill算法。fill_n算法可指定填充的元素个数。它的使用原型例如以下。将迭代器区间[first,first+n)个元素的值填充为value新值。

//fill_n函数的代码

template <class OutputIterator, class Size, class T>

  OutputIterator fill_n (OutputIterator first, Size n, const T& val)

{

  while (n>0) {

    *first = val;

    ++first; --n;

  }

  return first;     // since C++11

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v(8);

    fill(v.begin(), v.end(), 1);

    //前5个元素填充为2

    fill_n(v.begin(), 5, 2);

    for_each(v.begin(), v.end(), print);

    cout << endl;

    //所有填充为3

    fill_n(v.begin(), v.size(), 3);

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

随机生成元素generate

generate算法为容器生成新元素。使用原型例如以下，将gen发生器生成的一系列元素存入迭代器区间[first,last)的元素区域处。

//generate算法函数代码

template <class ForwardIterator, class Generator>

  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )

{

  while (first != last) {

    *first = gen();

    ++first;

  }

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

//等差数列an+1=an + 3

class sequence{

public:

    int a;

    sequence(){a=0;}

    inline int operator()(){

        a=a + 3;

        return a;

    }

};

void print(int x){

    cout << x << endl;

}

int main(void){

    vector<int> v(10);

    sequence an;

    generate(v.begin(), v.end(), an);

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

随机生成n个元素generate_n

与generate算法相似，但generate_n算法限定了可填入容器的数值个数。它的使用原型例如以下，将迭代器区间[first,first+n）位置处的n个元素，填入由发生器gen生成的数值。

//generate_n算法函数代码

template <class OutputIterator, class Size, class Generator>

  void generate_n ( OutputIterator first, Size n, Generator gen )

{

  while (n>0) {

    *first = gen();

    ++first; --n;

  }

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

int main(void){

    using namespace std;

    vector<int> v(10);

    //生成3个伪随机数

    generate_n(v.begin(), 3, rand);

    for(unsigned int i=0; i<v.size(); i++)

        cout << v[i] << ' ';

    cout << endl;

    return 0;

}

移除复制remove_copy

remove_copy算法实质上是一个条件复制，将容器中不等于某个给定值的元素拷贝到新容器。使用原型例如以下，将迭代器区间[first,last)上不取value的所有元素拷贝到迭代器区间[result,result+n)，n为实际复制的元素个数。

//remove_copy函数的代码

template <class InputIterator, class OutputIterator, class T>

  OutputIterator remove_copy (InputIterator first, InputIterator last,

                              OutputIterator result, const T& val)

{

  while (first!=last) {

    if (!(*first == val)) {

      *result = *first;

      ++result;

    }

    ++first;

  }

  return result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

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

    v.push_back(4);

    v.push_back(8);

    //

    int iArray[6]={0, 0, 0, 0, 0, 0};

    //v不变

    remove_copy(v.begin(), v.end(), iArray, 4);

    for_each(v.begin(), v.end(), print);

    cout << endl;

    //打印iArray

    for_each(iArray, iArray+6, print);

    cout << endl;

    return 0;

}

条件移除复制remove_copy_if

remove_copy_if实际上是remove_copy函数的一个带谓词推断的版本号，使用原型例如以下，将迭代器区间[first,last)上不满足谓词推断条件pred的元素，拷贝到有迭代器result为起始位置的迭代器区间中。

//remove_copy_if算法函数的代码

template <class InputIterator, class OutputIterator, class UnaryPredicate>

  OutputIterator remove_copy_if (InputIterator first, InputIterator last,

                                 OutputIterator result, UnaryPredicate pred)

{

  while (first!=last) {

    if (!pred(*first)) {

      *result = *first;

      ++result;

    }

    ++first;

  }

  return result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << "  ";

}

bool even(int x){  //偶数

    return x % 2 ?

0:1;

}

int main(void){

    //初始化向量v

    vector<int> v;

    v.push_back(7);

    v.push_back(2);

    v.push_back(5);

    v.push_back(4);

    v.push_back(1);

    //初始化数组iArray

    int iArray[6]={0, 0, 0, 0, 0, 0};

    //移除v中偶数,剩余元素拷贝到iArray

    remove_copy_if(v.begin(), v.end(), iArray, even);

    //打印v,v没有改变

    for_each(v.begin(), v.end(), print);

    cout << endl;

    //打印iArray

    for_each(iArray, iArray+6, print);

    cout << endl;

    return 0;

}

移除remove

remove算法是将容器中等于某个给定值的元素所有除去。

使用原型例如以下，将迭代器区间将迭代器区间[first,last)上不等于value的元素，复制回迭代器区间[first,result)，当中result是算法函数返回的迭代器。

迭代器区间[result,last)的元素仍然保持不变。

//remove算法函数的代码

template <class ForwardIterator, class T>

  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)

{

  ForwardIterator result = first;

  while (first!=last) {

    if (!(*first == val)) {

      *result = *first;

      ++result;

    }

    ++first;

  }

  return result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << "  ";

}

int main(void){

    //初始化向量v

    vector<int> v;

    v.push_back(2);

    v.push_back(4);

    v.push_back(3);

    v.push_back(4);

    v.push_back(8);

    //移除4

    vector<int>::iterator result=remove(v.begin(), v.end(), 4);

    //打印2 3 8

    for_each(v.begin(), result, print);

    cout << endl;

    //打印2 3 8 4 8

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

条件移除remove_if

remove_if是remove函数的一个带谓词推断的版本号，使用原型例如以下，将迭代器区间[first,last)上不满足谓词推断条件pred的元素，复制回迭代器区间[first,result)，result是算法返回值。[result,last)上元素保持不变。

//remove_if算法函数的代码

template <class ForwardIterator, class UnaryPredicate>

  ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,

                             UnaryPredicate pred)

{

  ForwardIterator result = first;

  while (first!=last) {

    if (!pred(*first)) {

      *result = *first;

      ++result;

    }

    ++first;

  }

  return result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << "  ";

}

bool even(int x){  //偶数

    return x % 2 ?

0:1;

}

int main(void){

    //初始化向量v

    vector<int> v;

    v.push_back(7);

    v.push_back(2);

    v.push_back(5);

    v.push_back(4);

    v.push_back(1);

    //移除偶数

    vector<int>::iterator result=remove_if(v.begin(), v.end(), even);

    //打印7 5 1

    for_each(v.begin(), result, print);

    cout << endl;

    //打印7 5 1 4 1

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

不连续反复元素复制unique_copy

unique_copy用于复制不连续的反复元素。它有例如以下两个使用原型，将迭代器区间[first,last)中邻近相异的元素，拷贝到以result为起点的迭代器区间。

//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);

template <class InputIterator, class OutputIterator>

  OutputIterator unique_copy (InputIterator first, InputIterator last,

                              OutputIterator result)

{

  if (first==last) return result;

  *result = *first;

  while (++first != last) {

    typename iterator_traits<InputIterator>::value_type val = *first;

    if (!(*result == val))   // or: if (!pred(*result,val)) for version (2)

      *(++result)=val;

  }

  return ++result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v;

    v.push_back(2);

    v.push_back(5);

    v.push_back(5);

    v.push_back(5);

    v.push_back(6);

    v.push_back(5);

    v.push_back(2);

    //

    int iArray[6]={0, 0, 0, 0, 0, 0};

    //

    unique_copy(v.begin(), v.end(), iArray);

    //打印2 5 6 5 2 0

    for_each(iArray, iArray+6, print);

    cout << endl;

    return 0;

}

剔除连续反复元素unique

unique算法用于剔除容器中连续反复元素，使用原型例如以下，将迭代器区间[first,last)中不连续反复的元素或不满足谓词推断条件的元素。复制回迭代区间[first,result)，result为算法返回值。[result,last)区间的元素。依旧维持不变。

template <class ForwardIterator>

  ForwardIterator unique (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>

  ForwardIterator unique (ForwardIterator first, ForwardIterator last,

                          BinaryPredicate pred);

template <class ForwardIterator>

  ForwardIterator unique (ForwardIterator first, ForwardIterator last)

{

  if (first==last) return last;

  ForwardIterator result = first;

  while (++first != last)

  {

    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)

      *(++result)=*first;

  }

  return ++result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v;

    v.push_back(2);

    v.push_back(6);

    v.push_back(6);

    v.push_back(6);

    v.push_back(9);

    v.push_back(6);

    v.push_back(3);

    //

    vector<int>::iterator result=unique(v.begin(), v.end());

    //打印2 6 9 6 3

    for_each(v.begin(), result, print);

    cout << endl;

    //打印2 6 9 6 3 6 3

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

元素反向reverse

reverse算法用于容器元素的反向排列，使用原型例如以下，将迭代区间[first,last)的元素反向排列。

template <class BidirectionalIterator>

  void reverse (BidirectionalIterator first, BidirectionalIterator last)

{

  while ((first!=last)&&(first!=--last)) {

    std::iter_swap (first,last);

    ++first;

  }

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v(10);

    for(unsigned int i=0; i<v.size(); i++)

        v[i]=i;

    for_each(v.begin(), v.end(), print);

    cout << endl;

    //

    reverse(v.begin(), v.end());

    for_each(v.begin(), v.end(), print);

    cout << endl;

    return 0;

}

反向复制reverse_copy

reverse_copy算法用于反向复制容器元素。使用原型例如以下，将迭代器区间[first,last)中的元素，以反向顺序拷贝到迭代器区间[result,result+(last-first))。

template <class BidirectionalIterator, class OutputIterator>

  OutputIterator reverse_copy (BidirectionalIterator first,

                               BidirectionalIterator last, OutputIterator result)

{

  while (first!=last) {

    --last;

    *result = *last;

    ++result;

  }

  return result;

}
//測试用例

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

void print(int x){

    cout << x << ' ';

}

int main(void){

    vector<int> v(10);

    for(unsigned int i=0; i<v.size(); i++)

        v[i]=i;

    //

    int iArray[10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    //

    reverse_copy(v.begin(), v.end(), iArray);

    for_each(iArray, iArray+10, print);

    cout << endl;

    return 0;

}

旋转rotate

rotate算法用于旋转某个迭代器区间的元素。使用原型例如以下。将迭代器区间[first,last)中元素以middle为支点。左旋转[first,middle)元素到[middle,last)的一側。

//rotate算法函数的代码

template <class ForwardIterator>

  void rotate (ForwardIterator first, ForwardIterator middle,

               ForwardIterator last)

{

  ForwardIterator next = middle;

  while (first!=next)

  {

    swap (*first++,*next++);

    if (next==last) next=middle;

    else if (first==middle) middle=next;

  }

}
//測试用例

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main () {

    vector<int> myvector;

    for (int i=1; i<10; ++i)

        myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

    rotate(myvector.begin(),myvector.begin()+3,myvector.end());

    // 4 5 6 7 8 9 1 2 3

    for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)

        cout << ' ' << *it;

    cout << '\n';

    return 0;

}

完结。

转载请注明出处：http://blog.csdn.net/lsh_2013/article/details/46894197

最新文章

  1. Elasticsearch5.0.1索引压测结果
  2. Mecanim分析
  3. GBPR: Group Preference Based Bayesian Personalized Ranking for One-Class Collaborative Filtering-IJACA 2013_20160421
  4. Python中带参装饰器理解
  5. [CareerCup] 17.9 Word Frequency in a Book 书中单词频率
  6. 基础笔记4（包装类，时间date. calendar
  7. OpenStack Swift集群与Keystone的整合使用说明
  8. Vmware为Ubuntu安装VmTools
  9. 搭建SpringMVC+MyBatis开发框架六
  10. adb怎么判断是否有root权限，并更改system/app内容
  11. js中with、this的用法
  12. hdu1020
  13. 算法系列001---dfs|多叉|解空间树理解
  14. Configuration Extensions - 简化配置，让你配置支持变量
  15. goldengate同源一目标+多表和同源多目标+多表
  16. elasticsearch常用命令
  17. 机器学习三剑客之matplotlib 数据绘图展示
  18. dataTransfer对象
  19. TYpeScript接口的使用
  20. [转] iOS开发工具——网络封包分析工具Charles

热门文章

  1. javascript 获取时间
  2. .net C# 格式化时间
  3. ACM_二维数组的查找
  4. C#学习-程序集和反射
  5. iOS device is locked/unlocked (判断手机屏幕是否锁屏)
  6. inner join / left join / right join
  7. html中设置浏览器解码方式
  8. 如何在eclipse中设置断点并调试程序
  9. day10-函数基础知识
  10. 解决 The file will have its original line endings in your working directory