STL学习笔记（已序区间算法）

针对已序区间执行的算法，执行前提是源区间必须在某个排序准则下已序。

搜寻元素(Searching)

1.检查某个元素是否存在

bool

binary_search(ForwardIterator beg,ForwardIterator end,

const T& value)

bool

binary_search(ForwardIterator beg,ForwardIterator end,

const T& value,

BinaryPredicate op)

以下示范binary_search()的用法

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     list<int> coll;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll);

     if(binary_search(coll.begin(),coll.end(),))

         cout<<"5 is present"<<endl;

     else

         cout<<"5 is not present"<<endl;

     if(binary_search(coll.begin(),coll.end(),))

         cout<<"42 is present"<<endl;

     else

         cout<<"42 is not present"<<endl;

 }

2.检查若干值是否存在

bool

includes(InputIterator beg,

InputIterator end,

InputIterator searchBeg,

InputIterator searchEnd)

bool

includes(InputIterator beg,

InputIterator end,

InputIterator searchBeg,

InputIterator searchEnd,

BinaryPredicate op)

两种形式都用来判断已序区间[beg,end)是否包含另一已序区间[searchBeg,searchEnd)的全部元素

以下程序示范inlcudes()的用法

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     list<int> coll;

     vector<int> search;

     INSERT_ELEMENTS(coll,,);

     PRINT_ELEMENTS(coll,"coll: ");

     search.push_back();

     search.push_back();

     search.push_back();

     PRINT_ELEMENTS(search,"search: ");

     if(includes(coll.begin(),coll.end(),search.begin(),search.end()))

         cout<<"all elements of search are also in coll"<<endl;

     else

         cout<<"not all elements of search are also in coll"<<endl;

 }

3.搜寻第一个或最后一个可能位置

ForwardIterator

lower_bound(ForwardIterator beg,ForwardIterator end,const T& value)

ForwardIterator

lower_bound(ForwardIterator beg,ForwardIterator end,const T& value,

BinaryPredicate op)

ForwardIterator

upper_bound(ForwardIterator beg,ForwardIterator end,const T& value)

ForwardIterator

upper_bound(ForwardIterator beg,ForwardIterator end,const T& value,

BinaryPredicate op)

1.lower_bound()返回第一个“大于等于value”的元素位置。

2.upper_bound()返回第一个“大于value”元素的位置

以下程序示范lower_bound()和upper_bound()的用法

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     list<int> coll;

     INSERT_ELEMENTS(coll,,);

     INSERT_ELEMENTS(coll,,);

     coll.sort();

     PRINT_ELEMENTS(coll);

     list<int>::iterator pos1,pos2;

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

     pos2=upper_bound(coll.begin(),coll.end(),);

     cout<<"5 could get position "

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

         <<" up to "

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

         <<" without breaking the sorting"<<endl;

     coll.insert(lower_bound(coll.begin(),coll.end(),),);

     coll.insert(upper_bound(coll.begin(),coll.end(),),);

     PRINT_ELEMENTS(coll);

 }

3.搜寻第一个和最后一个可能位置

pair<ForwardIterator,ForwardIterator>

equal_range(ForwardIterator beg,ForwardIterator end,const T& value)

pair<ForwardIterator,ForwardIterator>

equal_range(ForwardIterator beg,ForwardIterator end,const T& value,

BinaryPredicate op)

返回值与下式等效: make_pair(lower_bound(...),upper_bound(...))

以下程序展示equal_range()的用法

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

 }

合并元素(Merging)

1.两个已序集合的总和

OutputIterator

merge(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg)

OutputIterator

merge(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg,BinaryPredicate op)

1.两者都是将两个源区间的元素合并，使得“以destBeg起始的目标区间”内含两个源区间所有元素。

2.目标区间内的所有元素都将按顺序排序

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

 #include <iterator>

 #include "algostuff.hpp"

 using namespace std;

 int main()

 {

     list<int> coll1;

     set<int> coll2;

     INSERT_ELEMENTS(coll1,,);

     INSERT_ELEMENTS(coll2,,);

     PRINT_ELEMENTS(coll1,"coll1: ");

     PRINT_ELEMENTS(coll2,"coll2: ");

     cout<<"merged: ";

     merge(coll1.begin(),coll1.end(),coll2.begin(),coll2.end(),ostream_iterator<int>(cout," "));

     cout<<endl;

 }

2.两个已序集合的并集

OutputIterator

set_union(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg)

OutputIterator

set_union(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg,BinaryPredicate op)

与merge不一样的是，目标区间的元素要不来自第一源区间，要不就来自第二源区间，或是同时来自两个源区间。例如：

source1:1 2 2 4 6 7 7 9

source2:2 2 2 3 6 6 8 9

dest:1 2 2 2 3 4 6 6 7 7 8 9

3.两个已序集合的交集

OutputIterator

set_intersection(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg)

OutputIterator

set_intersection(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg,BinaryPredicate op)

4.两个已序集合的差集

OutputIterator

set_difference(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg)

OutputIterator

set_difference(InputIterator source1Beg,InputIterator source1End,

InputIterator source2Beg,InputIterator source2End,

OutputIterator destBeg,BinaryPredicate op)

目标区间的元素只存在于第一源区间，不存在与第二源区间。

巴特西

STL学习笔记（已序区间算法）

最新文章

热门文章