STL非变易算法 - STL算法(一)

原创：STL非变易算法 - STL算法

作者：MilkCu（http://blog.csdn.net/milkcu）

本文地址：http://blog.csdn.net/milkcu/article/details/21114613

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

引言

C++ STL的非变易算法（Non-mutating algorithms）是一组不破坏函数数据的模板函数，用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配，基本上可用于各种容器。下面的叙述中迭代器区间默认为[first, last)，迭代器具有“++”迭代和“*”访问操作。

逐个处理算法

for_each函数

该函数对迭代器区间的每个元素，执行单参数函数对象定义的操作。

下面的实例程序，将打印容器vector中的每个元素。

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

结果输出为：

0 2 4 6 8 10 12 14 16 18

元素查找算法

find函数

该函数用于查找等于某值的元素。如果迭代器i所指的元素满足*i == value，则返回迭代器i。未找到满足条件的元素，返回last。只要找到第一个满足条件的元素就返回迭代器位置，不再继续查找。

下面的示例程序查找容器vector中，第一个值为6的元素，打印元素位置及其前一元素。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int main(void) { vector
     
       v; for(int i = 0; i < 10; i++) { v.push_back(i * 2); } vector
      
       ::iterator iv = find(v.begin(), v.end(), 6); if(iv == v.end()) { cout << "Find nothing." << endl; } else { cout << "The postion of " << *iv << " is " << iv - v.begin() << endl; cout << "The previous element of it is " << *(--iv) << endl; } return 0; }
      
     
    
   
  

结果输出为：

The postion of 6 is 3
The previous element of it is 4

find_if函数

该函数是find的一个谓词判断版本，查找满足谓词判断函数的元素。

下面的实例程序将寻找容器vector中第一个能被3整除的元素。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int divBy3(int x) { return x % 3   0 : 1; } int main(void) { vector
     
       v; for(int i = 1; i < 10; i++) { v.push_back(i * 2); } vector
      
       ::iterator iv = find_if(v.begin(), v.end(), divBy3); if(iv == v.end()) { cout << "None could be divided by 3 with no remaineder." << endl; } else { cout << *iv << " could be divided by 3 with no remainder." << endl; } return 0; }
      
     
    
   
  

结果输出为：

6 could be divided by 3 with no remainder.

adjacent_find函数

该函数用于查找相等或满足条件的邻近元素对。它有两个使用原型，一个用于查找相等的两个连续元素，另一个使用二元谓词判断，查找满足条件的邻近元素对。

下面的实例程序用于寻找容器中相等的元素和奇偶性相同的元素。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int parity_equal(int x, int y) { return (x - y) % 2 == 0   1 : 0; } int main(void) { vector
     
       v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(5); v.push_back(5); v.push_back(7); vector
      
       ::iterator iv = adjacent_find(v.begin(), v.end()); if(iv != v.end()) { cout << "There are two equal elements." << endl; cout << "It is " << *iv << endl; } iv = adjacent_find(v.begin(), v.end(), parity_equal); if(iv != v.end()) { cout << "There are two parity euqal elements." << endl; cout << "They are " << *iv << " and "; iv++; cout << *iv << endl; } return 0; }
      
     
    
   
  

输出结果为：

There are two equal elements.
It is 5
There are two parity euqal elements.
They are 3 and 5

find_first_of函数

该函数用于查找某个范围之内的元素。它有两个使用原型，一个是相等，另一个是二元谓词判断。元素找到则返回迭代器，否则返回末位置。

下面的实例程序用于计算容器v2中元素在容器v中重合出现的首位置。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int main(void) { vector
     
       v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(5); v.push_back(5); v.push_back(7); vector
      
        v2; v2.push_back(3); v2.push_back(3); v2.push_back(5); vector
       
        ::iterator iv = find_first_of(v.begin(), v.end(), v2.begin(), v2.end()); cout << "The position of the first equal element is " << iv - v.begin() << endl; return 0; }
       
      
     
    
   
  

输出结果为：

The position of the first equal element is 3

元素统计算法

count函数

该函数用于计算容器中某个给定值的出现次数。它有两个使用原型，区别在于计数是直接返回还是引用返回。

下面的实例程序计算了容器中5的出现次数，结果直接返回。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int main(void) { vector
     
       v; for(int i = 0; i < 17; i++) { v.push_back(i % 6); } int num = count(v.begin(), v.end(), 5); cout << "The number of 5 is " << num << endl; return 0; }
     
    
   
  

输出结果为：

The number of 5 is 2

count_if函数

该函数使用谓词判断函数，统计迭代器区间上满足条件的元素个数。它有两个使用原型，区别在与计数是直接返回还是引用返回。

下面的实例程序统计了容器中大于10的数字的出现次数，结果直接返回。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int greaterThan10(int x) { return x > 10   1 : 0; } int main(void) { vector
     
       v; for(int i = 0; i < 17; i++) { v.push_back(i); } int num = count_if(v.begin(), v.end(), greaterThan10); cout << "The number of the figure that greater than 10 is " << num << endl; return 0; } 
     
    
   
  

输出结果为：

The number of the figure that greater than 10 is 6

序列匹配算法

mismatch函数

该函数用于比较两个序列，找出首个不匹配元素的位置。它有两个使用原型，分别为不相等和不满足二元谓词条件。

该函数还涉及到pair的使用。

下面的实例程序比较两个整型容器，并找出不匹配的数字。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int main(void) { vector
     
       v1, v2; v1.push_back(3); v1.push_back(5); v1.push_back(5); v2.push_back(3); v2.push_back(5); v2.push_back(7); pair
      
       ::iterator, vector
       
        ::iterator> result = mismat