# Benjamin

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

Stl的算法的不更改序列操作主要有以下12项：
count、count_if、mismatch、equal、search、search_n

1、 for_each:遍历某个区域内每个元素

Function for_each (InputIterator first, InputIterator last, Function f);

#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

InputIterator find ( InputIterator first, InputIterator last, const T& value );

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

InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred );

// 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:

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

#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:

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

#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;
}

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

#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:

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：

typename iterator_traits<InputIterator>::difference_type
count ( ForwardIterator first, ForwardIterator last, const T& value );

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

typename iterator_traits<InputIterator>::difference_type
count_if ( ForwardIterator first, ForwardIterator last, Predicate pred );

#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

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

#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

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

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

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

#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

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

return 0;
}

12、search_n

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

#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

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

return 0;
}

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