Benjamin

静以修身,俭以养德,非澹薄无以明志,非宁静无以致远。
随笔 - 279, 文章 - 0, 评论 - 196, 引用 - 0
数据加载中……

stl的算法(一):对序列进行只读操作(查找、搜索等)

Stl的算法的不更改序列操作主要有以下12项:
for_each、find、find_if、find_end、find_first_of、adjacent_find
count、count_if、mismatch、equal、search、search_n

1、 for_each:遍历某个区域内每个元素
原型:template <class InputIterator, class Function>
   Function for_each (InputIterator first, InputIterator last, Function f);
形参:first、last确定那个一个区域;f是函数指针,必须重载()
例子:// for_each example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
void myfunction (int i) {
 cout << " " << i;
}
 
struct myclass {
 void operator() (int i) {cout << " " << i;}
} myobject;
 
int main () {
 vector<int> myvector;
 myvector.push_back(10);
 myvector.push_back(20);
 myvector.push_back(30);
 
 cout << "myvector contains:";
 for_each (myvector.begin(), myvector.end(), myfunction);
 
 // or:
 cout << "\nmyvector contains:";
 for_each (myvector.begin(), myvector.end(), myobject);
 
 cout << endl;
 
 return 0;
}
 

2、 find:返回在迭代器指定的范围内第一个匹配的值,如果没有找到返回last
原型:template <class InputIterator, class T>
         InputIterator find ( InputIterator first, InputIterator last, const T& value );
形参:见for_each

例子:
// find example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main () {
 int myints[] = { 10, 20, 30 ,40 };
 int * p;
 
 // pointer to array element:
 p = find(myints,myints+4,30);
 ++p;
 cout << "The element following 30 is " << *p << endl;
 
 vector<int> myvector (myints,myints+4);
 vector<int>::iterator it;
 
 // iterator to vector element:
 it = find (myvector.begin(), myvector.end(), 30);
 ++it;
 cout << "The element following 30 is " << *it << endl;
 
 return 0;
}
 

3、 find_if
原型:template <class InputIterator, class Predicate>
   InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred );
形参:同上
功能:变量first和end间的区域,如果调用pred都返回false,则函数返回end;如果返回true,
则直接break,返回当前iterator。这里查找的是一个element
例子:
// find_if example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
bool IsOdd (int i) {
 return ((i%2)==1);
}
 
int main () {
 vector<int> myvector;
 vector<int>::iterator it;
 
 myvector.push_back(10);
 myvector.push_back(25);
 myvector.push_back(40);
 myvector.push_back(55);
 
 it = find_if (myvector.begin(), myvector.end(), IsOdd);
 cout << "The first odd value is " << *it << endl;
 
 return 0;
}
 
4、 find_end:
原型:template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
                               ForwardIterator2 first2, ForwardIterator2 last2 );

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
                               ForwardIterator2 first2, ForwardIterator2 last2,
                               BinaryPredicate pred );

功能:搜索first2,last2在first1,last1中最后一次匹配的位置
形参: first1、end1和first2、end2确定一个序列,pred的含义和上面的函数雷同
例子:// find_end example
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

 

bool myfunction (int i, int j) {
 return (i==j);
}

 

int main () {
 int myints[] = {1,2,3,4,5,1,2,3,4,5};
 vector<int> myvector (myints,myints+10);
 vector<int>::iterator it;
 
 int match1[] = {1,2,3};

 

 // using default comparison:
 it = find_end (myvector.begin(), myvector.end(), match1, match1+3);

 

 if (it!=myvector.end())
    cout << "match1 last found at position " << int(it-myvector.begin()) << endl;

 int match2[] = {4,5,1};

 

 // using predicate comparison:
 it = find_end (myvector.begin(), myvector.end(), match2, match2+3, myfunction);

 if (it!=myvector.end())
    cout << "match2 last found at position " << int(it-myvector.begin()) << endl;

 return 0;
}

5、 find_first_of:
原型:template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_first_of ( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2 );

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 find_first_of ( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2,
                                    BinaryPredicate pred );

功能:搜索first2,last2在first1,last1中第一次匹配的位置
例子:// find_first_of example
#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;
 
bool comp_case_insensitive (char c1, char c2) {
 return (tolower(c1)==tolower(c2));
}
 
int main () {
 int mychars[] = {'a','b','c','A','B','C'};
 vector<char> myvector (mychars,mychars+6);
 vector<char>::iterator it;
 
 int match[] = {'A','B','C'};
 
 // using default comparison:
 it = find_first_of (myvector.begin(), myvector.end(), match, match+3);
 
 if (it!=myvector.end())
    cout << "first match is: " << *it << endl;
 
 // using predicate comparison:
 it = find_first_of (myvector.begin(), myvector.end(),
                      match, match+3, comp_case_insensitive);
 
 if (it!=myvector.end())
    cout << "first match is: " << *it << endl;
 
  return 0;
}
6、 adjacent_find:
原型:template <class ForwardIterator>
   ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last );
template <class ForwardIterator, class BinaryPredicate>
   ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last,
                                   BinaryPredicate pred );

功能:查找连续重复的元素
形参:见find
例子:// adjacent_find example
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool myfunction (int i, int j) {
 return (i==j);
}

 

int main () {
 int myints[] = {10,20,30,30,20,10,10,20};
 vector<int> myvector (myints,myints+8);
 vector<int>::iterator it;

 // using default comparison:
 it = adjacent_find (myvector.begin(), myvector.end());

 if (it!=myvector.end())
    cout << "the first consecutive repeated elements are: " << *it << endl;

 //using predicate comparison:
 it = adjacent_find (++it, myvector.end(), myfunction);

 if (it!=myvector.end())
    cout << "the second consecutive repeated elements are: " << *it << endl;

 return 0;
}

Output :the first consecutive repeated elements are: 30
the second consecutive repeated elements are: 10
 

7、 count:
原型:template <class InputIterator, class T>
 typename iterator_traits<InputIterator>::difference_type
count ( ForwardIterator first, ForwardIterator last, const T& value );
功能:统计value在first、end间出现的次数
例子:

// count algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main () {
 int mycount;

 // counting elements in array:
 int myints[] = {10,20,30,30,20,10,10,20};   // 8 elements
 mycount = (int) count (myints, myints+8, 10);
 cout << "10 appears " << mycount << " times.\n";

 

 // counting elements in container:
 vector<int> myvector (myints, myints+8);

 mycount = (int) count (myvector.begin(), myvector.end(), 20);
 cout << "20 appears " << mycount << " times.\n";

 return 0;
}

8、 count_if
原型:template <class InputIterator, class Predicate>
 typename iterator_traits<InputIterator>::difference_type
count_if ( ForwardIterator first, ForwardIterator last, Predicate pred );
功能:返回满足pred条件的元素个数
例子:// count_if example

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool IsOdd (int i) { return ((i%2)==1); }

int main () {
 int mycount;

 vector<int> myvector;

 for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9

 

 mycount = (int) count_if (myvector.begin(), myvector.end(), IsOdd);
 cout << "myvector contains " << mycount << " odd values.\n";

 return 0;
}

9、 mismatch
原型:template <class InputIterator1, class InputIterator2>
 pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2 );
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 pair<InputIterator1, InputIterator2>
 mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, BinaryPredicate pred );
功能:返回first2和end2在first1和end1内不匹配的位置
例子:// mismatch algorithm example

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool mypredicate (int i, int j) {
 return (i==j);
}

int main () {
 vector<int> myvector;

 for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50

 int myints[] = {10,20,80,320,1024};                //   myints: 10 20 80 320 1024

 pair<vector<int>::iterator,int*> mypair;

 
 // using default comparison:
 mypair = mismatch (myvector.begin(), myvector.end(), myints);

 cout << "First mismatching elements: " << *mypair.first;
 cout << " and " << *mypair.second << endl;;

 mypair.first++; mypair.second++;


 // using predicate comparison:
 mypair = mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);

 cout << "Second mismatching elements: " << *mypair.first;
 cout << " and " << *mypair.second << endl;;

 return 0;
}
Output:First mismatching elements: 30 and 80
Second mismatching elements: 40 and 320

10、equal
原型:template <class InputIterator1, class InputIterator2>
 bool equal ( InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2 );
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 bool equal ( InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, BinaryPredicate pred );

功能:比较从first2开始的一个序列是否和first1、end1的序列相等
例子:
// equal algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
 return (i==j);
}

int main () {

 int myints[] = {20,40,60,80,100};          //   myints: 20 40 60 80 100
 vector<int>myvector (myints,myints+5);     // myvector: 20 40 60 80 100

 // using default comparison:
 if (equal (myvector.begin(), myvector.end(), myints))
    cout << "The contents of both sequences are equal." << endl;
 else
    cout << "The contents of both sequences differ." << endl;

 myvector[3]=81;                            // myvector: 20 40 60 81 100

 // using predicate comparison:
 if (equal (myvector.begin(), myvector.end(), myints, mypredicate))
    cout << "The contents of both sequences are equal." << endl;
 else
    cout << "The contents of both sequences differ." << endl;

 return 0;
}

11、search
原型:template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2 );
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2.
                             BinaryPredicate pred );
功能:和find_end类似,但不是end,而是first
例子:#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
 return (i==j);
}

int main () {
 vector<int> myvector;
 vector<int>::iterator it;

 // set some values:        myvector: 10 20 30 40 50 60 70 80 90
 for (int i=1; i<10; i++) myvector.push_back(i*10);

 // using default comparison:
 int match1[] = {40,50,60,70};
 
 it = search (myvector.begin(), myvector.end(), match1, match1+4);

 if (it!=myvector.end())
    cout << "match1 found at position " << int(it-myvector.begin()) << endl;
 else
    cout << "match1 not found" << endl;

 // using predicate comparison:
 int match2[] = {20,30,50};

 it = search (myvector.begin(), myvector.end(), match2, match2+3, mypredicate);

 if (it!=myvector.end())
    cout << "match2 found at position " << int(it-myvector.begin()) << endl;
 else
    cout << "match2 not found" << endl;

 return 0;
}

12、search_n
原型:template <class ForwardIterator, class Size, class T>
   ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                              Size count, const T& value );
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
   ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                              Size count, const T& value, BinaryPredicate pred );
功能:在某个范围内搜索值;如果没找到返回end
例子:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool mypredicate (int i, int j) {
 return (i==j);
}

int main () {
 int myints[]={10,20,30,30,20,10,10,20};
 
 vector<int> myvector (myints,myints+8);
 vector<int>::iterator it;

 // using default comparison:
 it = search_n (myvector.begin(), myvector.end(), 2, 30);

 if (it!=myvector.end())
    cout << "two 30s found at position " << int(it-myvector.begin()) << endl;
 else
    cout << "match not found" << endl;

 // using predicate comparison:
 it = search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);

 if (it!=myvector.end())
    cout << "two 10s found at position " << int(it-myvector.begin()) << endl;
 else
    cout << "match not found" << endl;

 return 0;
}

 

 

 

 

posted on 2011-12-27 13:41 Benjamin 阅读(433) 评论(0)  编辑 收藏 引用 所属分类: 泛型编程


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理