当前位置: 首页 > 编程语言 > C++ > 正文

走近STL(6)

时间:2009-01-27 vckbase 陶汉军

变序型队列算法(mutating algorithms):

又叫可修改的序列算法。这类算法有复制(copy)算法、交换(swap)算法、替代(replace)算法、删除(remove)算法,移动(transfer)算法、翻转(reverse)算法等等。这些算法可以改变容器中的数据(数据值和值在容器中的位置)。下面介绍2个比较常用的算法reverse()和copy()。

//stl_cpp_14.cpp
#include <iostream>
#include <algorithm>
#include <iterator>//下面用到了输出迭代器ostream_iterator
using namespace std;
int main(void)
{
  int arr[6]={1,12,3,2,1215,90};
   int arr1[7];
  int arr2[6]={2,5,6,9,0,-56};
  copy(arr,(arr+6),arr1);//将数组aar复制到arr1
  cout<<"arr[6] copy to arr1[7],now arr1: "<<endl;
  for(int i=0;i<7;i++)
    cout<<" "<<arr1[i];
  reverse(arr,arr+6);//将排好序的arr翻转
  cout<<''\n ''<<"arr reversed ,now arr:"<<endl;
  copy(arr,arr+6,ostream_iterator<int>(cout, " "));//复制到输出迭代器
swap_ranges(arr,arr+6,arr2);//交换arr和arr2序列
  cout<<''\n ''<<"arr swaped to arr2,now arr:"<<endl;
  copy(arr,arr+6,ostream_iterator<int>(cout, " "));
  cout<<''\n ''<<"arr2:"<<endl;
  copy(arr2,arr2+6,ostream_iterator<int>(cout, " "));
  cin.get();
  return 0;
}
revese()的功能是将一个容器内的数据顺序翻转过来,它的原型是:

template<class Bidirectional >

void reverse(Bidirectional first, Bidirectional last);

将first和last之间的元素翻转过来,上例中你也可以只将arr中的一部分进行翻转:

reverse(arr+3,arr+6);这也是有效的。First和last需要指定一个操作区间。

Copy()是要将一个容器内的数据复制到另一个容器内,它的原型是:
  Template<class InputIterator ,class OutputIterator>
 OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
  它把[first,last-1]内的队列成员复制到区间[result,result+(last-first)-1]中。泛型交换算法:Swap()操作的是单值交换,它的原型是:
template<class T>
void swap(T& a,T& b);
swap_ranges()操作的是两个相等大小区间中的值,它的原型是:
 template<class ForwardIterator1, class ForwardIterator2>
 ForwardIterator2 swap_ranges(ForwardIterator1 first1,ForwardIterator1 last1,\
ForwardIterator1 first2);
  交换区间[first1,last1-1]和[first2, first2+(last1-first1)-1]之间的值,并假设这两个区间是不重叠的。
  非变序型队列算法(Non-mutating algorithm):

又叫不可修改的序列算法。这一类算法操作不影响其操作的容器的内容,包括搜索队列成员算法,等价性检查算法,计算队列成员个数的算法。我将用下面的例子介绍其中的find(),search(),count():
//stl_cpp_15.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
  int a[10]={12,31,5,2,23,121,0,89,34,66};
  vector<int> v1(a,a+10);
  vector<int>::iterator result1,result2;//result1和result2是随机访问迭代器
  result1=find(v1.begin(),v1.end(),2);
  //在v1中找到2,result1指向v1中的2
  result2=find(v1.begin(),v1.end(),8);
  //在v1中没有找到8,result2指向的是v1.end()
  cout<<result1-v1.begin()<<endl; //3-0=3或4-1=3,屏幕结果是3
  cout<<result2-v1.end()<<endl;  
  int b[9]={5,2,23,54,5,5,5,2,2};
  vector<int> v2(a+2,a+8);
  vector<int> v3(b,b+4);
  result1=search(v1.begin(),v1.end(),v2.begin(),v2.end());
  cout<<*result1<<endl;
  //在v1中找到了序列v2,result1指向v2在v1中开始的位置
   result1=search(v1.begin(),v1.end(),v3.begin(),v3.end());
   cout<<*(result1-1)<<endl;
  //在v1中没有找到序列v3,result指向v1.end(),屏幕打印出v1的最后一个元素66  
   vector<int> v4(b,b+9);
   int i=count(v4.begin(),v4.end(),5);
   int j=count(v4.begin(),v4.end(),2);
   cout<<"there are "<<i<<" members in v4 equel to 5"<<endl;
   cout<<"there are "<<j<<" members in v4 equel to 2"<<endl;
   //计算v4中有多少个成员等于 5,2
  cin.get();
  return 0;    
}
find()的原型是:
template<class InputIterator,class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last,\
          const EqualityComparable& value);

其功能是在序列[first,last-1]中查找value值,如果找到,就返回一个指向value在序列中第一次出现的迭代,如果没有找到,就返回一个指向last的迭代(last并不属于序列)。 search()的原型是:

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
            ForwardIterator2 first2, ForwardIterator2 last2);

其功能是在源序列[first1,last1-1]查找目标序列[first2,last2-1]如果查找成功,就返回一个指向源序列中目标序列出现的首位置的迭代。查找失败则返回一个指向last的迭代。 Count()的原型是:

template <class InputIterator, class EqualityComparable>
iterator_traits<InputIterator>::difference_type count(InputIterator first,\
InputIterator last, const EqualityComparable& value);
  其功能是在序列[first,last-1]中查找出等于value的成员,返回等于value得成员的个数。

排序算法(sort algorithm):

这一类算法很多,功能强大同时也相对复杂一些。这些算法依赖的是关系运算。在这里我只介绍其中比较简单的几种排序算法:sort(),merge(),includes()
//stl_cpp_16.cpp
 #include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
  int a[10]={12,0,5,3,6,8,9,34,32,18};
  int b[5]={5,3,6,8,9};
  int d[15];
  sort(a,a+10);
  for(int i=0;i<10;i++)
   cout<<" "<<a[i];
  sort(b,b+5);
  if(includes(a,a+10,b,b+5))
    cout<<''\n ''<<"sorted b members are included in a."<<endl;
  else
    cout<<"sorted a dosn`t contain sorted b!";
   merge(a,a+10,b,b+5,d);
  for(int j=0;j<15;j++)
    cout<<" "<<d[j];
  cin.get();
  return 0;
}
sort()的原型是:

template <class RandomAccessIterator>

void sort(RandomAccessIterator first, RandomAccessIterator last);

功能是对[first,last-1]区间内的元素进行排序操作。与之类似的操作还有:partial_sort(), stable_sort(),partial_sort_copy()等等。 merge()的原型是:

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,\

InputIterator2 first2, InputIterator2 last2,OutputIterator result);

将有序区间[first1,last1-1]和[first2,last2-1]合并到[result, result + (last1 - first1) + (last2 - first2)-1]区间内。

Includes()的原型是:

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,\
         InputIterator2 first2, InputIterator2 last2);

其功能是检查有序区间[first2,last2-1]内元素是否都在[first1,last1-1]区间内,返回一个bool值。