STL学习笔记（非变动性算法）

辅助函数

本节跟以后几节将对所有STL算法逐一详细讨论。为了简化这些例子，我们使用了一些辅助函数，分别用于对容器进行输出跟插入操作。

 1 #ifndef ALGOSTUFF_HPP
 2 #define ALGOSTUFF_HPP
 3 #include <iostream>
 4 #include <vector>
 5 #include <deque>
 6 #include <list>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <algorithm>
11 #include <functional>
12 #include <numeric>
13 
14 template <class T>
15 inline void PRINT_ELEMENTS(const T& coll,const char* optcstr="")
16 {
17     typename T::const_iterator pos;
18     std::cout<<optcstr;
19     for(pos=coll.begin();pos!=coll.end();++pos)
20         std::cout<<*pos<<" ";
21     std::cout<<std::endl;
22 }
23 
24 template <class T>
25 inline void INSERT_ELEMENTS(T& coll,int first,int last)
26 {
27     for(int i=first;i<=last;++i)
28         coll.insert(coll.end(),i);
29 }
30 #endif
View Code

for_each()算法

for_each()算法非常灵活，它可以以不同的方式存取、处理、修改每一个元素

UnaryProc

for_each(InputIterator beg,InputIterator end,UnaryProc op);

1.对与区间[beg,end)中的每一个元素调用:op(elem)

2.返回op(已在算法内部被变动过)的一个副本

3.op的任何返回值都会被忽略

下面例子将print()传给for_each()，使得for_each()对每一个元素调用print()，从而打印所有元素：

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 void print(int elem)
 5 {
 6     cout<<elem<<' ';
 7 }
 8 
 9 int main()
10 {
11     vector<int> coll;
12     INSERT_ELEMENTS(coll,1,9);
13     for_each(coll.begin(),coll.end(),print);
14     cout<<endl;
15 }
View Code

下面例子展示如何利用for_each()的返回值，利用这个特性可以求出平均值：

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 class MeanValue
 5 {
 6 private:
 7     long num;
 8     long sum;
 9 public:
10     MeanValue():num(0),sum(0){}
11     void operator() (int elem)
12     {
13         num++;
14         sum+=elem;
15     }
16     operator double()
17     {
18         return static_cast<double>(sum)/static_cast<double>(num);
19     }
20 };
21 
22 int main()
23 {
24     vector<int> coll;
25     INSERT_ELEMENTS(coll,1,8);
26     double mv=for_each(coll.begin(),coll.end(),MeanValue());
27     cout<<"mean value: "<<mv<<endl;
28 }
View Code

 

1.元素计数

difference_type

count(InputIterator beg,InputIterator end,const T& value)

difference_type

count_if(InputIterator beg,InputIterator end,UnarPredicate op)

1.第一种形式会计算区间[beg,end)中元素值等于value的元素个数

2.第二种形式会计算区间[beg,end)中令以下一元判断式结果为true的元素个数:op(elem)

3.返回值型别difference_type是表现迭代器区间的型别

以下范例根据不同的准则对元素进行计数：

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 bool isEven(int elem)
 5 {
 6     return elem%2==0;
 7 }
 8 
 9 int main()
10 {
11     vector<int> coll;
12     int num;
13     INSERT_ELEMENTS(coll,1,9);
14     PRINT_ELEMENTS(coll,"coll: ");
15     num=count(coll.begin(),coll.end(),4);
16     cout<<"number of elements equal to 4: "<<num<<endl;
17     num=count_if(coll.begin(),coll.end(),isEven);
18     cout<<"number of elements with even value: "<<num<<endl;
19     num=count_if(coll.begin(),coll.end(),bind2nd(greater<int>(),4));
20     cout<<"number of elements greater than 4: "<<num<<endl;
21 }
View Code

2.最小值和最大值

InputIterator

min_element(InputIterator beg,InputIterator end)

InputIterator

min_element(InputIterator beg,InputIterator end,CompFunc op)

InputIterator

max_element(InputIterator beg,InputIterator end)

InputIterator

max_element(InputIterator beg,InputIterator end,CompFunc op)

1.所有这些算法都返回区间[beg,end)中最小或最大元素的位置。

2.上述无op参数的版本，以operator<进行元素比较

3.op用来比较两个元素：op(elem1,elem2)。如果第一个元素小于第二个元素，应当返回true。

4.如果存在多个最小值或最大值，上述算法返回找到的第一个最小或最大值。

以下程序打印coll之中的最小元素和最大元素，并通过absLess()打印绝对值最大跟最小的元素：

 1 #include <cstdlib>
 2 #include "algostuff.hpp"
 3 using namespace std;
 4 
 5 bool absLess(int elem1,int elem2)
 6 {
 7     return abs(elem1)<abs(elem2);
 8 }
 9 
10 int main()
11 {
12     deque<int> coll;
13     INSERT_ELEMENTS(coll,2,8);
14     INSERT_ELEMENTS(coll,-3,5);
15     PRINT_ELEMENTS(coll);
16     cout<<"minimum: "
17         <<*min_element(coll.begin(),coll.end())
18         <<endl;
19     cout<<"maximum: "
20         <<*max_element(coll.begin(),coll.end())
21         <<endl;
22     cout<<"minimum of absolute values: "
23         <<*min_element(coll.begin(),coll.end(),absLess)
24         <<endl;
25     cout<<"maximum of absolute values: "
26         <<*max_element(coll.begin(),coll.end(),absLess)
27         <<endl;
28 }
View Code

3.搜寻元素

搜索第一个元素

InputIterator

find(InputIterator beg,InputIterator end,const T& value)

InputIterator

find_if(InputIterator beg,InputIterator end,UnaryPredicate op)

1.第一形式返回区间[beg,end)中第一个“元素值等于value”的元素位置

2.第二形式返回区间[beg,end)中令以下一元判断式结果为true的第一个元素位置:op(elem)

3.如果没有找到匹配元素，两种形式都返回end。

下面这个例子展示如何运用find()搜寻一个子区间：以元素值为4的第一个元素开始，以元素值为4的第二个元素结束

 1 #include <iterator>
 2 #include "algostuff.hpp"
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     list<int> coll;
 8     INSERT_ELEMENTS(coll,1,9);
 9     INSERT_ELEMENTS(coll,1,9);
10     PRINT_ELEMENTS(coll,"coll: ");
11     list<int>::iterator pos1;
12     pos1=find(coll.begin(),coll.end(),4);
13     list<int>::iterator pos2;
14     if(pos1!=coll.end())
15         pos2=find(++pos1,coll.end(),4);
16     if(pos1!=coll.end()&&pos2!=coll.end())
17         copy(--pos1,++pos2,ostream_iterator<int>(cout," "));
18     cout<<endl;
19 }
View Code

下面这个程序展示find_if()的用法

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     vector<int> coll;
 7     vector<int>::iterator pos;
 8     INSERT_ELEMENTS(coll,1,9);
 9     PRINT_ELEMENTS(coll,"coll: ");
10     pos=find_if(coll.begin(),coll.end(),bind2nd(greater<int>(),3));
11     cout<<"the "
12         <<distance(coll.begin(),pos)+1
13         <<". element is the first greater than 3"<<endl;
14     pos=find_if(coll.begin(),coll.end(),not1(bind2nd(modulus<int>(),3)));
15     cout<<"the "
16         <<distance(coll.begin(),pos)+1
17         <<". element is the first divisible by 3"<<endl;
18 }
View Code

搜索前n个连续匹配值

InputIterator

search_n(InputIterator beg,InputIterator end,

              Size count,const T& value)

InputIterator

search_n(InputIterator beg,InputIterator end,

              Size count,const T& value,BinaryPredicate op)

1.第一形式返回区间[beg,end)中第一组“连续count个元素全等于value”的元素位置

2.第二形式返回区间[beg,end)中第一组“连续count个元素造成以下二元判断式结果为true”的元素位置：op(elem,value)

3.如果没有找到匹配元素，两种形式都返回end。

下面这个例子演示了这两个函数的用法

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     deque<int> coll;
 7     INSERT_ELEMENTS(coll,1,9);
 8     PRINT_ELEMENTS(coll);
 9     deque<int>::iterator pos;
10     pos=search_n(coll.begin(),coll.end(),4,3);
11     if(pos!=coll.end())
12         cout<<"four consecutive elements with value 3 "
13             <<"start with "<<distance(coll.begin(),pos)+1
14             <<". element"<<endl;
15     else
16         cout<<"no four consecutive elements with value 3 found"<<endl;
17     pos=search_n(coll.begin(),coll.end(),4,3,greater<int>());
18     if(pos!=coll.end())
19         cout<<"four consecutive elements with value > 3 "
20             <<"start with "<<distance(coll.begin(),pos)+1
21             <<". element"<<endl;
22     else
23         cout<<"no four consecutive elements with value > 3 found"<<endl;
24     
25 }
View Code

搜寻第一个子区间

ForwardIterator1

search(ForwardIterator1 beg,ForwardIterator1 end,

           ForwardIterator2 searchBeg,ForwardIterator2 searchEnd)

ForwardIterator1

search(ForwardIterator1 beg,ForwardIterator2 end,

           ForwardIterator2 searchBeg,ForwardIterator2 end,

           BinaryPredicate op)

1.两种形式都返回区间[beg,end)内和区间[searchBeg,searchEnd)完全吻合的第一个子区间的第一个元素位置

2.第一种形式中，子区间的元素必须完全等于[searchBeg,searchEnd)的元素

3.第二种形式中，子区间的元素和[searchBeg,searchEnd)的对应元素必须造成以下二元判断式的结果为true：op(elem,searchElem)

4.如果没有找到符合条件的子区间，两种形式都返回end

下面这个例子展示如何在另一个序列中搜寻一个子序列

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     deque<int> coll;
 7     list<int> subcoll;
 8     INSERT_ELEMENTS(coll,1,7);
 9     INSERT_ELEMENTS(coll,1,7);
10     INSERT_ELEMENTS(subcoll,3,6);
11     PRINT_ELEMENTS(coll,"coll: ");
12     PRINT_ELEMENTS(subcoll,"subcoll: ");
13     deque<int>::iterator pos;
14     pos=search(coll.begin(),coll.end(),subcoll.begin(),subcoll.end());
15     while(pos!=coll.end())
16     {
17         cout<<"subcoll found starting with element "
18             <<distance(coll.begin(),pos)+1
19             <<endl;
20         ++pos;
21         pos=search(pos,coll.end(),subcoll.begin(),subcoll.end());
22     }
23 }
View Code

下面这个例子展示了search的第二种形式的用法

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 bool checkEven(int elem,bool even)
 5 {
 6     if(even)
 7     {
 8         return elem%2==0;
 9     }
10     else
11     {
12         return elem%2==1;
13     }
14 }
15 
16 int main()
17 {
18     vector<int> coll;
19     INSERT_ELEMENTS(coll,1,9);
20     PRINT_ELEMENTS(coll,"coll: ");
21     bool checkEvenArgs[3]={true,false,true};
22     vector<int>::iterator pos;
23     pos=search(coll.begin(),coll.end(),checkEvenArgs,checkEvenArgs+3,checkEven);
24     while(pos!=coll.end())
25     {
26         cout<<"subrange found starting with element "
27             <<distance(coll.begin(),pos)+1
28             <<endl;
29         pos=search(++pos,coll.end(),checkEvenArgs,checkEvenArgs+3,checkEven);
30     }
31 }
View Code

搜寻最后一个子区间

ForwardIterator

find_end(ForwardIterator beg,ForwardIterator end,

             ForwardIterator searchBeg,ForwardIterator searchEnd)

ForwardIterator

find_end(ForwardIterator beg,ForwardIterator end,

             ForwardIterator searchBeg,ForwardIterator searchEnd,

             BinaryPredicate op)

find_end()与search()用法大同小异。下面例子展示如何在一个序列中搜寻“与某序列相等”的最后一个子序列

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     deque<int> coll;
 7     list<int> subcoll;
 8     INSERT_ELEMENTS(coll,1,7);
 9     INSERT_ELEMENTS(coll,1,7);
10     INSERT_ELEMENTS(subcoll,3,6);
11     PRINT_ELEMENTS(coll,"coll: ");
12     PRINT_ELEMENTS(subcoll,"subcoll: ");
13     deque<int>::iterator pos;
14     pos=find_end(coll.begin(),coll.end(),subcoll.begin(),subcoll.end());
15     deque<int>::iterator end(coll.end());
16     while(pos!=end)
17     {
18         cout<<"subcoll found starting with element "
19             <<distance(coll.begin(),pos)+1
20             <<endl;
21         end=pos;
22         pos=find_end(coll.begin(),end,subcoll.begin(),subcoll.end());
23     }
24 }
View Code

搜寻某些元素的第一次出现地点

FordwardIterator

find_first_of(ForwardIterator1 beg,ForwardIterator1 end,

                     ForwardIterator 2 searchBeg,ForwardIterator2 searchEnd)

FordwardIterator

find_first_of(ForwardIterator1 beg,ForwardIterator1 end,

                     ForwardIterator 2 searchBeg,ForwardIterator2 searchEnd,

                     BinaryPredicate op)

1.第一形式返回第一个“既在区间[beg,end)中出现，也在区间[searchBeg,searchEnd)中出现”的元素的位置

2.第二形式返回区间[beg,end)中第一个这样的元素：它和区间[searchBeg,searchEnd)内某一个元素进行以下动作的结果是true: op(elem,searchElem)

3.如果没有找到吻合元素，两种形式都返回end

下面这个例子展示find_first_of()的用法：

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     vector<int> coll;
 7     list<int> searchcoll;
 8     INSERT_ELEMENTS(coll,1,11);
 9     INSERT_ELEMENTS(searchcoll,3,5);
10     PRINT_ELEMENTS(coll,"coll: ");
11     PRINT_ELEMENTS(searchcoll,"searchcoll: ");
12     vector<int>::iterator pos;
13     pos=find_first_of(coll.begin(),coll.end(),searchcoll.begin(),searchcoll.end());
14     cout<<"first elements of searchcoll in coll is element "<<distance(coll.begin(),pos)+1<<endl;
15     vector<int>::reverse_iterator rpos;
16     rpos=find_first_of(coll.rbegin(),coll.rend(),searchcoll.rbegin(),searchcoll.rend());
17     cout<<"last element of searchcoll in coll is element "<<distance(coll.begin(),rpos.base())<<endl;
18 }
View Code

搜寻两个连续且相等的元素

InputIterator

adjacent_find(InputIteator beg,InputIterator end)

InputIterator

adjacent_find(InputIteator beg,InputIterator end,

                      BinaryPredicate op)

1.第一形式返回区间[beg,end)中第一对“连续两个相等元素”之中第一个元素位置

2.第二形式返回区间[beg,end)中第一对“连续两个元素均使以下二元判断式的结果为true”的其中第一元素位置：op(elem,nextelem)

3.如果没有找到吻合元素，两者都返回end

下面展示adjacent_find()两种形式的用法：

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 bool doubled(int elem1,int elem2)
 5 {
 6     return elem1*2==elem2;
 7 }
 8 
 9 int main()
10 {
11     vector<int> coll;
12     coll.push_back(1);
13     coll.push_back(3);
14     coll.push_back(2);
15     coll.push_back(4);
16     coll.push_back(5);
17     coll.push_back(5);
18     coll.push_back(0);
19     PRINT_ELEMENTS(coll,"coll: ");
20     vector<int>::iterator pos;
21     pos=adjacent_find(coll.begin(),coll.end());
22     if(pos!=coll.end())
23         cout<<"first two elements with equal value have position "
24             <<distance(coll.begin(),pos)+1
25             <<endl;
26     pos=adjacent_find(coll.begin(),coll.end(),doubled);
27     if(pos!=coll.end())
28         cout<<"first two elements with second value twice the first have pos. "
29             <<distance(coll.begin(),pos)+1
30             <<endl;
31 }
View Code

区间的比较

检验相等性

bool

equal(InputIterator1 beg,InputIterator1 end,

          InputIterator2 cmpBeg)

bool

equal(InputIterator1 beg,InputIterator1 end,

          InputIterator2 cmpBeg,BinaryPredicate op)

1.第一形式判断区间[beg,end)内的元素是否都和“以cmpBeg开头的区间”内的元素相等

2.第二形式判断区间[beg,end)内的元素和“以cmpBeg开头的区间内的对应元素“是否都能使以下二元判断式为true： op(elem,cmpElem)

3.调用者必须确保”以cmpBeg开头的区间“内含足够元素

下面是equal()两种形式的用法

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 bool bothEvenOrOdd(int elem1,int elem2)
 5 {
 6     return elem1%2==elem2%2;
 7 }
 8 
 9 int main()
10 {
11     vector<int> coll1;
12     list<int> coll2;
13     INSERT_ELEMENTS(coll1,1,7);
14     INSERT_ELEMENTS(coll2,3,9);
15     PRINT_ELEMENTS(coll1,"coll1: ");
16     PRINT_ELEMENTS(coll2,"coll2: ");
17     if(equal(coll1.begin(),coll1.end(),coll2.begin()))
18         cout<<"coll1==coll2"<<endl;
19     else
20         cout<<"coll1!=coll2"<<endl;
21     if(equal(coll1.begin(),coll1.end(),coll2.begin(),bothEvenOrOdd))
22         cout<<"even and odd elements correspond"<<endl;
23     else
24         cout<<"even and odd elements do not correspond"<<endl;
25 }
View Code

搜寻第一处不同点

pair<InputIterator1,InputIterator2>

mismatch(InputIterator1 beg,InputIterator1 end,

                InputIterator2 cmpBeg)

pair<InputIterator1,InputIterator2>

mismatch(InputIterator1 beg,InputIterator1 end,

                InputIterator2 cmpBeg,

                BinaryPredicate op)

1.第一形式返回区间[beg,end)和”以cmpBeg开头的区间“之中第一组两两相异的对应元素

2.第二形式返回区间[beg,end)和”以cmpBeg开头的区间“之中第一组”使以下二元判断式获得false“的对应元素: op(elem,cmpElem)

3.如果没有找到相异点，就返回一个pair，以end和第二序列的对应元素组成。

下面例子展示mismatch()两种形式的用法

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     vector<int> coll1;
 7     list<int> coll2;
 8     INSERT_ELEMENTS(coll1,1,6);
 9     for(int i=1;i<=16;i*=2)
10         coll2.push_back(i);
11     coll2.push_back(3);
12     PRINT_ELEMENTS(coll1,"coll1: ");
13     PRINT_ELEMENTS(coll2,"coll2: ");
14     pair<vector<int>::iterator,list<int>::iterator> values;
15     values=mismatch(coll1.begin(),coll1.end(),coll2.begin());
16     if(values.first==coll1.end())
17         cout<<"no mismatch"<<endl;
18     else
19         cout<<"first mismatch: "
20             <<*values.first<<" and "
21             <<*values.second<<endl;
22     values=mismatch(coll1.begin(),coll1.end(),coll2.begin(),less_equal<int>());
23     if(values.first==coll1.end())
24         cout<<"always less-or-equal"<<endl;
25     else
26         cout<<"not less-or-euqal: "
27             <<*values.first<<" and "
28             <<*values.second<<endl;
29     
30 }
View Code

检验”小于“

bool

lexicographical_compare(InputIterator1 beg1,InputIterator1 end1,

                                        InputIterator2 beg2,InputIterator2 end2)

bool

lexicographical_compare(InputIterator1 beg1,InputIterator1 end1,

                                        InputIterator2 beg2,InputIterator2 end2,

                                        CompFunc op)

1.两种形式都用来判断区间[beg1,end1)的元素是否小于区间[beg2,end2)的元素

2.第一形式以operator<来比较元素

3.第二形式以二元判断式op(elem1,elem2)比较元素。如果elem1<elem2，则判断式应当返回true

下面这个例子展示如何利用这个算法对群集完成”字典次序“的排序

 1 #include "algostuff.hpp"
 2 using namespace std;
 3 
 4 void printCollection(const list<int>& l)
 5 {
 6     PRINT_ELEMENTS(l);
 7 }
 8 
 9 bool lessForCollection(const list<int>& l1,const list<int>& l2)
10 {
11     return lexicographical_compare(l1.begin(),l1.end(),l2.begin(),l2.end());
12 }
13 
14 int main()
15 {
16     list<int> c1,c2,c3,c4;
17     INSERT_ELEMENTS(c1,1,5);
18     c4=c3=c2=c1;
19     c1.push_back(7);
20     c3.push_back(2);
21     c3.push_back(0);
22     c4.push_back(2);
23     vector<list<int> > cc;
24     cc.push_back(c1);
25     cc.push_back(c2);
26     cc.push_back(c3);
27     cc.push_back(c4);
28     cc.push_back(c3);
29     cc.push_back(c1);
30     cc.push_back(c4);
31     cc.push_back(c2);
32     for_each(cc.begin(),cc.end(),printCollection);
33     cout<<endl;
34     sort(cc.begin(),cc.end(),lessForCollection);
35     for_each(cc.begin(),cc.end(),printCollection);
36 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/runnyu/p/4843200.html