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

辅助函数

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

 #ifndef ALGOSTUFF_HPP

 #define ALGOSTUFF_HPP

 #include <iostream>

 #include <vector>

 #include <deque>

 #include <list>

 #include <set>

 #include <map>

 #include <string>

 #include <algorithm>

 #include <functional>

 #include <numeric>

 template <class T>

 inline void PRINT_ELEMENTS(const T& coll,const char* optcstr="")

 {

     typename T::const_iterator pos;

     std::cout<<optcstr;

     for(pos=coll.begin();pos!=coll.end();++pos)

         std::cout<<*pos<<" ";

     std::cout<<std::endl;

 }

 template <class T>

 inline void INSERT_ELEMENTS(T& coll,int first,int last)

 {

     for(int i=first;i<=last;++i)

         coll.insert(coll.end(),i);

 }

 #endif

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()，从而打印所有元素：

 #include "algostuff.hpp"

 using namespace std;

 void print(int elem)

 {

     cout<<elem<<' ';

 }

 int main()

 {

     vector<int> coll;

     INSERT_ELEMENTS(coll,,);

     for_each(coll.begin(),coll.end(),print);

     cout<<endl;

 }

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

 #include "algostuff.hpp"

 using namespace std;

 class MeanValue

 {

 private:

     long num;

     long sum;

 public:

     MeanValue():num(),sum(){}

     void operator() (int elem)

     {

         num++;

         sum+=elem;

     }

     operator double()

     {

         return static_cast<double>(sum)/static_cast<double>(num);

     }

 };

 int main()

 {

     vector<int> coll;

     INSERT_ELEMENTS(coll,,);

     double mv=for_each(coll.begin(),coll.end(),MeanValue());

     cout<<"mean value: "<<mv<<endl;

 }

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是表现迭代器区间的型别

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

 #include "algostuff.hpp"

 using namespace std;

 bool isEven(int elem)

 {

     return elem%==;

 }

 int main()

 {

     vector<int> coll;

     int num;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     num=count(coll.begin(),coll.end(),);

     cout<<"number of elements equal to 4: "<<num<<endl;

     num=count_if(coll.begin(),coll.end(),isEven);

     cout<<"number of elements with even value: "<<num<<endl;

     num=count_if(coll.begin(),coll.end(),bind2nd(greater<int>(),));

     cout<<"number of elements greater than 4: "<<num<<endl;

 }

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()打印绝对值最大跟最小的元素：

 #include <cstdlib>

 #include "algostuff.hpp"

 using namespace std;

 bool absLess(int elem1,int elem2)

 {

     return abs(elem1)<abs(elem2);

 }

 int main()

 {

     deque<int> coll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(coll,-,);

     PRINT_ELEMENTS(coll);

     cout<<"minimum: "

         <<*min_element(coll.begin(),coll.end())

         <<endl;

     cout<<"maximum: "

         <<*max_element(coll.begin(),coll.end())

         <<endl;

     cout<<"minimum of absolute values: "

         <<*min_element(coll.begin(),coll.end(),absLess)

         <<endl;

     cout<<"maximum of absolute values: "

         <<*max_element(coll.begin(),coll.end(),absLess)

         <<endl;

 }

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的第二个元素结束

 #include <iterator>

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     list<int> coll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     list<int>::iterator pos1;

     pos1=find(coll.begin(),coll.end(),);

     list<int>::iterator pos2;

     if(pos1!=coll.end())

         pos2=find(++pos1,coll.end(),);

     if(pos1!=coll.end()&&pos2!=coll.end())

         copy(--pos1,++pos2,ostream_iterator<int>(cout," "));

     cout<<endl;

 }

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

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     vector<int> coll;

     vector<int>::iterator pos;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     pos=find_if(coll.begin(),coll.end(),bind2nd(greater<int>(),));

     cout<<"the "

         <<distance(coll.begin(),pos)+

         <<". element is the first greater than 3"<<endl;

     pos=find_if(coll.begin(),coll.end(),not1(bind2nd(modulus<int>(),)));

     cout<<"the "

         <<distance(coll.begin(),pos)+

         <<". element is the first divisible by 3"<<endl;

 }

搜索前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。

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

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     deque<int> coll;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll);

     deque<int>::iterator pos;

     pos=search_n(coll.begin(),coll.end(),,);

     if(pos!=coll.end())

         cout<<"four consecutive elements with value 3 "

             <<"start with "<<distance(coll.begin(),pos)+

             <<". element"<<endl;

     else

         cout<<"no four consecutive elements with value 3 found"<<endl;

     pos=search_n(coll.begin(),coll.end(),,,greater<int>());

     if(pos!=coll.end())

         cout<<"four consecutive elements with value > 3 "

             <<"start with "<<distance(coll.begin(),pos)+

             <<". element"<<endl;

     else

         cout<<"no four consecutive elements with value > 3 found"<<endl;

 }

搜寻第一个子区间

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

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

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     deque<int> coll;

     list<int> subcoll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(subcoll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     PRINT_ELEMENTS(subcoll,"subcoll: ");

     deque<int>::iterator pos;

     pos=search(coll.begin(),coll.end(),subcoll.begin(),subcoll.end());

     while(pos!=coll.end())

     {

         cout<<"subcoll found starting with element "

             <<distance(coll.begin(),pos)+

             <<endl;

         ++pos;

         pos=search(pos,coll.end(),subcoll.begin(),subcoll.end());

     }

 }

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

 #include "algostuff.hpp"

 using namespace std;

 bool checkEven(int elem,bool even)

 {

     if(even)

     {

         return elem%==;

     }

     else

     {

         return elem%==;

     }

 }

 int main()

 {

     vector<int> coll;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     bool checkEvenArgs[]={true,false,true};

     vector<int>::iterator pos;

     pos=search(coll.begin(),coll.end(),checkEvenArgs,checkEvenArgs+,checkEven);

     while(pos!=coll.end())

     {

         cout<<"subrange found starting with element "

             <<distance(coll.begin(),pos)+

             <<endl;

         pos=search(++pos,coll.end(),checkEvenArgs,checkEvenArgs+,checkEven);

     }

 }

搜寻最后一个子区间

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()用法大同小异。下面例子展示如何在一个序列中搜寻“与某序列相等”的最后一个子序列

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     deque<int> coll;

     list<int> subcoll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(subcoll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     PRINT_ELEMENTS(subcoll,"subcoll: ");

     deque<int>::iterator pos;

     pos=find_end(coll.begin(),coll.end(),subcoll.begin(),subcoll.end());

     deque<int>::iterator end(coll.end());

     while(pos!=end)

     {

         cout<<"subcoll found starting with element "

             <<distance(coll.begin(),pos)+

             <<endl;

         end=pos;

         pos=find_end(coll.begin(),end,subcoll.begin(),subcoll.end());

     }

 }

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

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()的用法：

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     vector<int> coll;

     list<int> searchcoll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(searchcoll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     PRINT_ELEMENTS(searchcoll,"searchcoll: ");

     vector<int>::iterator pos;

     pos=find_first_of(coll.begin(),coll.end(),searchcoll.begin(),searchcoll.end());

     cout<<"first elements of searchcoll in coll is element "<<distance(coll.begin(),pos)+<<endl;

     vector<int>::reverse_iterator rpos;

     rpos=find_first_of(coll.rbegin(),coll.rend(),searchcoll.rbegin(),searchcoll.rend());

     cout<<"last element of searchcoll in coll is element "<<distance(coll.begin(),rpos.base())<<endl;

 }

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

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()两种形式的用法：

 #include "algostuff.hpp"

 using namespace std;

 bool doubled(int elem1,int elem2)

 {

     return elem1*==elem2;

 }

 int main()

 {

     vector<int> coll;

     coll.push_back();

     coll.push_back();

     coll.push_back();

     coll.push_back();

     coll.push_back();

     coll.push_back();

     coll.push_back();

     PRINT_ELEMENTS(coll,"coll: ");

     vector<int>::iterator pos;

     pos=adjacent_find(coll.begin(),coll.end());

     if(pos!=coll.end())

         cout<<"first two elements with equal value have position "

             <<distance(coll.begin(),pos)+

             <<endl;

     pos=adjacent_find(coll.begin(),coll.end(),doubled);

     if(pos!=coll.end())

         cout<<"first two elements with second value twice the first have pos. "

             <<distance(coll.begin(),pos)+

             <<endl;

 }

区间的比较

检验相等性

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()两种形式的用法

 #include "algostuff.hpp"

 using namespace std;

 bool bothEvenOrOdd(int elem1,int elem2)

 {

     return elem1%==elem2%;

 }

 int main()

 {

     vector<int> coll1;

     list<int> coll2;

     INSERT_ELEMENTS(coll1,,);

     INSERT_ELEMENTS(coll2,,);

     PRINT_ELEMENTS(coll1,"coll1: ");

     PRINT_ELEMENTS(coll2,"coll2: ");

     if(equal(coll1.begin(),coll1.end(),coll2.begin()))

         cout<<"coll1==coll2"<<endl;

     else

         cout<<"coll1!=coll2"<<endl;

     if(equal(coll1.begin(),coll1.end(),coll2.begin(),bothEvenOrOdd))

         cout<<"even and odd elements correspond"<<endl;

     else

         cout<<"even and odd elements do not correspond"<<endl;

 }

搜寻第一处不同点

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()两种形式的用法

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     vector<int> coll1;

     list<int> coll2;

     INSERT_ELEMENTS(coll1,,);

     for(int i=;i<=;i*=)

         coll2.push_back(i);

     coll2.push_back();

     PRINT_ELEMENTS(coll1,"coll1: ");

     PRINT_ELEMENTS(coll2,"coll2: ");

     pair<vector<int>::iterator,list<int>::iterator> values;

     values=mismatch(coll1.begin(),coll1.end(),coll2.begin());

     if(values.first==coll1.end())

         cout<<"no mismatch"<<endl;

     else

         cout<<"first mismatch: "

             <<*values.first<<" and "

             <<*values.second<<endl;

     values=mismatch(coll1.begin(),coll1.end(),coll2.begin(),less_equal<int>());

     if(values.first==coll1.end())

         cout<<"always less-or-equal"<<endl;

     else

         cout<<"not less-or-euqal: "

             <<*values.first<<" and "

             <<*values.second<<endl;

 }

检验”小于“

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

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

 #include "algostuff.hpp"

 using namespace std;

 void printCollection(const list<int>& l)

 {

     PRINT_ELEMENTS(l);

 }

 bool lessForCollection(const list<int>& l1,const list<int>& l2)

 {

     return lexicographical_compare(l1.begin(),l1.end(),l2.begin(),l2.end());

 }

 int main()

 {

     list<int> c1,c2,c3,c4;

     INSERT_ELEMENTS(c1,,);

     c4=c3=c2=c1;

     c1.push_back();

     c3.push_back();

     c3.push_back();

     c4.push_back();

     vector<list<int> > cc;

     cc.push_back(c1);

     cc.push_back(c2);

     cc.push_back(c3);

     cc.push_back(c4);

     cc.push_back(c3);

     cc.push_back(c1);

     cc.push_back(c4);

     cc.push_back(c2);

     for_each(cc.begin(),cc.end(),printCollection);

     cout<<endl;

     sort(cc.begin(),cc.end(),lessForCollection);

     for_each(cc.begin(),cc.end(),printCollection);

 }

巴特西

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

最新文章

热门文章