STL_算法_01_查找算法-白红宇

STL_算法_01_查找算法

阅读量：4452 次

发布时间：2019-06-07

本文共 12571 字，大约阅读时间需要 41 分钟。

1、

来自教程：第6讲 PPT.15

◆ 常用的查找算法：

1.1、按条件查找N个相邻的元素

（ adjacent 是邻近的意思）

iterator = adjacent_find(iteratorBegin, iteratorEnd); // 默认的相邻关系的判断依据 : 相等（是值相等吗?）

iterator = adjacent_find(iteratorBegin, iteratorEnd, functor判断相邻条件); // 自定义判断相邻关系的函数对象

1.2、二分查找

bool = binary_search(iteratorBegin, iteratorEnd, value);

bool = binary_search(iteratorBegin, iteratorEnd, value, functor二分查找遍历条件);

1.3、等值范围

pair<iterator, iterator> = equal_range(iteratorBegin, iteratorEnd, value);

pair<iterator, iterator> = equal_range(iteratorBegin, iteratorEnd, value, functor遍历条件);

1.4、

_Iter::difference_type = count(iteratorBegin, iteratorEnd, value);

1.5、

_Iter::difference_type = count_if(iteratorBegin, iteratorEnd, functor满足条件);

1.6、

iterator = find(iteratorBegin, iteratorEnd, value);

1.7、

iterator = find_if(iteratorBegin, iteratorEnd, functor满足条件);

1.1、第6讲 PPT.16

◆

adjacent_find(): 在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。

　　ZC: 上面的"past-the-end"，应该是指返回的迭代器和 vecInt.end() 比较。

ZC: 有两种参数格式，返回值都是 iterator。

ZC: 我的 VC6测试代码：

(1)、测试代码 - 1：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7 #include 
       
         8  9 #include 
        
             // 算法10 #include 
         
              // 算法11 #include 
          
            // 算法12 13 using namespace std;14 15 // ZC: 自己编写的 相邻条件判断 的函数对象16 class TestAdjacent17 {18 public:19 bool operator()(int _i, int _j)20 {21 return _i == _j ? true : false;22 23 // ZC: 相邻条件判断:_i是_j的一半，只要满足这个条件adjacent_find()就会返回_i所对应的iterator24 //return return _i == (_j / 2) ? true : false;25 }26 };27 28 void main()29 {30 vector
           
             v;31 v.push_back(1);32 v.push_back(2);33 v.push_back(2);34 v.push_back(3);35 v.push_back(4);36 v.push_back(5);37 v.push_back(5);38 v.push_back(5);39 v.push_back(6);40 v.push_back(7);41 42 // ZC: 第1种 参数格式43 vector
            
             ::iterator it = adjacent_find(v.begin(), v.end());44 printf("%d, 0x%08X\n", *it, *it);45 if (it == v.end())46 {47 printf("it == v.end()\n");48 printf("0x%08X, 0x%08X\n", it, v.end());49 }50 51 it = adjacent_find(it, v.end());52 printf("%d, 0x%08X\n", *it, *it);53 54 it ++;55 it = adjacent_find(it, v.end());56 printf("%d, 0x%08X\n", *it, *it);57 58 59 // ***60 printf("\n");61 62 // ZC: 第2种 参数格式63 it = adjacent_find(v.begin(), v.end(), TestAdjacent());64 if (it == v.end())65 {66 printf("it == v.end()\n");67 printf("0x%08X, 0x%08X\n", it, v.end());68 }69 else70 printf("%d, 0x%08X\n", *it, *it);71 }

控制台输出为：

1 2, 0x000000022 2, 0x000000023 5, 0x000000054 5 2, 0x000000026 Press any key to continue

(2)、测试代码 - 2：

1     vector
     
       v; 2     v.push_back(1); 3     //v.push_back(2); 4     v.push_back(2); 5     v.push_back(3); 6     v.push_back(4); 7     v.push_back(5); 8     //v.push_back(5); 9     //v.push_back(5);10     v.push_back(6);11     v.push_back(7);12 13     vector
      
       ::iterator it =  adjacent_find(v.begin(), v.end());14     printf("%d, 0x%08X\n", *it, *it);15     if (it == v.end())16     {17         printf("it == v.end()\n");18         printf("0x%08X, 0x%08X\n", it, v.end());19     }

控制台输出：

1 -842150451, 0xCDCDCDCD2 it == v.end()3 0x00272D9C, 0x00272D9C4 Press any key to continue

1.2、第6讲 PPT.17

◆

binary_search(): 在

有序序列中查找value,找到则返回true。注意：

在无序序列中，不可使用。

　　ZC：两分查找

ZC: 有两种参数格式，返回值都是 bool 。

ZC: VC6 测试代码：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 // ZC: 两分查找所使用的 比较函数对象15 class CompareIntFunctor16 {17 public:18     bool operator () (const int _iLeft, const int _iRight)19     {20         // ZC: 这里是使用"<"还是">"，就要看 set
          
            中使用的是何种排序方式了。21 // ZC: 注意，貌似 使用"<="或者">=" 得不到想要的结果...22 return _iLeft < _iRight;23 }24 };25 26 // ZC: 两分查找所使用的 比较函数27 bool CompareInt (const int _iLeft, const int _iRight)28 {29 return _iLeft < _iRight;30 }31 32 void main()33 {34 set
           
             setInt;35 setInt.insert(3);36 setInt.insert(1);37 setInt.insert(7);38 setInt.insert(5);39 setInt.insert(9);40 41 bool bFind = binary_search(setInt.begin(), setInt.end(), 7, CompareIntFunctor()); // 参数格式 - 142 printf("bFind : %d\n", bFind);43 44 bFind = binary_search(setInt.begin(), setInt.end(), 7, CompareInt); // 参数格式 - 145 printf("bFind : %d\n", bFind);46 47 bFind = binary_search(setInt.begin(), setInt.end(), 7); // 参数格式 - 248 printf("bFind : %d\n", bFind);49 50 bFind = binary_search(setInt.begin(), setInt.end(), 8); // 参数格式 - 251 printf("bFind : %d\n", bFind);52 }

ZC：控制台输出为：

1 bFind : 12 bFind : 13 bFind : 14 bFind : 05 Press any key to continue

ZC: VC6中出现警告："identifier was truncated to '255' characters in the debug information" ：

“

　　可以无视。说的是调试信息中的标示符被截断了。

问题是因为VC6对STL的一些不完全支持造成，手工屏蔽就可以。

方法为在源文件头部加入一下预编译代码

#ifdef WIN32

#pragma warning (disable: 4514 4786)

#endif

”

1.3、第6讲 PPT.21

◆ equal_range() : 返回一对iterator，第一个表示lower_bound,第二个表示upper_bound。

ZC：VC6中可以用于无序序列(可能是检查的不严格)；在vs2010中若用于无序序列编译不报错 Debug版exe运行时会被assert中断 Release版运行时结果和VC6相同。(注意这里说的是"无序序列"，不是"无序容器"。"无序容器"中的元素经过排序后，vs2010的Debug版的exe也不会被assert中断。)

ZC: VC6 测试代码 - 1（参数格式 - 1）：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 void main()15 {16     // (1)、无序容器 且 未经过排序17     vector
          
            vecInt;18 vecInt.push_back(1); 19 vecInt.push_back(2); 20 vecInt.push_back(2); 21 vecInt.push_back(4); 22 vecInt.push_back(2); 23 vecInt.push_back(5); 24 25 pair
           
            
             ::iterator, vector
             
              ::iterator> pairRstVec = equal_range(vecInt.begin(), vecInt.end(), 2); 26 printf("*pairRstVec.first : %d\n", *pairRstVec.first); 27 printf("*pairRstVec.second : %d\n", *pairRstVec.second); 28 29 vector
              
               ::iterator itVec = NULL; 30 int iIdx = 0; 31 for (itVec = pairRstVec.first; itVec != pairRstVec.second; itVec++, iIdx++) 32 printf("[%02d] ==> *itVec : %d\n", iIdx, *itVec); 33 //iIdx ++; 34 35 printf("\n"); 36 37 // (2)、有序容器 38 multiset
               
                 msetInt; 39 msetInt.insert(3); 40 msetInt.insert(1); 41 msetInt.insert(7); 42 msetInt.insert(3); 43 msetInt.insert(5); 44 msetInt.insert(3); 45 msetInt.insert(9); 46 msetInt.insert(3); 47 msetInt.insert(3); 48 49 pair
                
                 
                  ::iterator, multiset
                  
                   ::iterator> pairRstSet = equal_range(msetInt.begin(), msetInt.end(), 3); 50 printf("*pairRstSet.first : %d\n", *pairRstSet.first); 51 printf("*pairRstSet.second : %d\n", *pairRstSet.second); 52 53 multiset
                   
                    ::iterator itSet = NULL; 54 iIdx = 0; 55 for (itSet = pairRstSet.first; itSet != pairRstSet.second; itSet++, iIdx++) 56 printf("[%02d] ==> *itSet : %d\n", iIdx, *itSet); 57 }

ZC：控制台输出 - 1：

1 *pairRstVec.first : 2 2 *pairRstVec.second : 4 3 [00] ==> *itVec : 2 4 [01] ==> *itVec : 2 5  6 *pairRstSet.first : 3 7 *pairRstSet.second : 5 8 [00] ==> *itSet : 3 9 [01] ==> *itSet : 3 10 [02] ==> *itSet : 3 11 [03] ==> *itSet : 3 12 [04] ==> *itSet : 3 13 Press any key to continue

ZC: VC6 测试代码 - 2（参数格式 - 2）：

　　ZC: 注意，排序和检索时应该使用相同的方式(排序时使用升序，则检索时也应该使用升序，反之亦然)

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 class TStudent15 {16 public:17     TStudent(int _iAge) 18  { 19 FiAge = _iAge; 20 FiID = _iAge + 1000; 21  }; 22 23 int FiID; 24 int FiAge; 25 }; 26 27 bool Compare(const TStudent& left, const TStudent& right) 28 { 29 return left.FiAge < right.FiAge; 30 //return left.FiAge > right.FiAge; 31 } 32 33 struct StuFunctor 34 { 35 public: 36 bool operator() (const TStudent& stuLeft, const TStudent& stuRight) 37  { 38 return (stuLeft.FiAge < stuRight.FiAge); 39  } 40 }; 41 42 43 void main() 44 { 45 //set
          
            setStu; // ZC: 这里传 函数指针 是不行的，只能传 函数对象 46 set
           
             setStu; 47 setStu.insert(TStudent(3)); 48 setStu.insert(TStudent(1)); 49 setStu.insert(TStudent(5)); 50 TStudent stu2(2); 51 setStu.insert(stu2); 52 53 // ZC: 下面，第3个 参数直接传的是一个 int值，居然也是OK的... 54 pair
            
             
              ::iterator, set
              
               ::iterator> pair1 = equal_range(setStu.begin(), setStu.end(), 1, StuFunctor()); 55 set
               
                ::iterator it = pair1.first; 56 while (it != pair1.second) 57 { 58 printf("%d == > %d\n", it->FiAge, it->FiID); 59 it ++; 60 } 61 62 printf("*** *** *** *** ***\n"); 63 64 pair
                
                 
                  ::iterator, set
                  
                   ::iterator> pair2 = equal_range(setStu.begin(), setStu.end(), stu2, Compare); 65 it = pair2.first; 66 while (it != pair2.second) 67 { 68 printf("%d == > %d\n", it->FiAge, it->FiID); 69 it ++; 70 } 71 }

ZC：控制台输出 - 2：

1 1 == > 10012 *** *** *** *** ***3 2 == > 10024 Press any key to continue

1.4、第6讲 PPT.18

◆

count() : 利用

等于操作符，把标志范围内的元素与输入值比较，返回相等的

个数。

ZC: 只有一种参数格式，返回值是 _Iter::difference_type 。

ZC：VC6测试代码：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
      
        6 #include 
       
         7  8 #include 
        
             // 算法 9 #include 
         
              // 算法10 #include 
          
               // 算法11 12 using namespace std;13 14 void main()15 {16     vector
           
             vecInt;17 vecInt.push_back(1);18 vecInt.push_back(2);19 vecInt.push_back(2);20 vecInt.push_back(4);21 vecInt.push_back(2);22 vecInt.push_back(5);23 24 int iCount = count(vecInt.begin(), vecInt.end(), 2); //iCount==325 printf("iCount : %d\n", iCount);26 }

ZC: 控制台输出：

1 iCount : 32 Press any key to continue

1.5、第6讲 PPT.18

◆

count_if() : 利用

输入的函数，对标志范围内的元素进行比较操作，返回结果为true的

个数。

ZC: 只有一种参数格式，返回值是 _Iter::difference_type 。

ZC: VC6测试代码：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 //先定义比较函数15 bool GreaterThree(int iNum)16 {17     if (iNum >= 3)18     {19         return true;20     }21     else22     {23         return false;24     }25 }26 27 void main()28 {29     vector
          
            vecInt;30 vecInt.push_back(1);31 vecInt.push_back(2);32 vecInt.push_back(2);33 vecInt.push_back(4);34 vecInt.push_back(2);35 vecInt.push_back(5);36 37 int iCount = count_if(vecInt.begin(), vecInt.end(), GreaterThree);// ZC: 注意这里传入的是比较函数的函数地址38 printf("iCount : %d\n", iCount);39 }

ZC：控制台输出：

1 iCount : 22 Press any key to continue

1.6、第6讲 PPT.22

◆ find() : 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器。(ZC: 应该是找到后，立即返回)

ZC: VC6 测试代码：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 void main()15 {16     vector
          
            vecInt;17 vecInt.push_back(1);18 vecInt.push_back(3);19 vecInt.push_back(5);20 vecInt.push_back(7);21 vecInt.push_back(9);22 23 vector
           
            ::iterator it = find(vecInt.begin(), vecInt.end(), 5); //*it == 524 printf("*it : %d\n", *it);25 }

ZC：控制台输出：

1 *it : 52 Press any key to continue

1.7、第6讲 PPT.23

◆ find_if() : 使用输入的函数代替等于操作符执行find。返回被找到的元素的迭代器。

ZC: VC6 测试代码：

1 #ifdef WIN32 2 #pragma warning (disable: 4786) 3 #endif 4  5 #include 
     
       6 #include 
      
        7  8 #include 
       
            // 算法 9 #include 
        
             // 算法10 #include 
         
              // 算法11 12 using namespace std;13 14 bool GreaterThree(int iNum)15 {16     if (iNum >= 3)17     {18         return true;19     }20     else21     {22         return false;23     }24 }25 26 void main()27 {28     vector
          
            vecInt;29 vecInt.push_back(1);30 vecInt.push_back(3);31 vecInt.push_back(5);32 vecInt.push_back(7);33 vecInt.push_back(9);34 35 vector
           
            ::iterator it = find_if(vecInt.begin(), vecInt.end(), GreaterThree);36 printf("*it : %d\n", *it);37 printf("*(it+1) : %d\n", *(it+1));38 printf("*(it+2) : %d\n", *(it+2));39 printf("*(it+3) : %d\n", *(it+3));40 }

ZC：控制台输出：

1 *it : 32 *(it+1) : 53 *(it+2) : 74 *(it+3) : 95 Press any key to continue

?.?、第6讲 PPT.?

◆

ZC: VC6 测试代码：

ZC：控制台输出：

转载于:https://www.cnblogs.com/cppskill/p/5238911.html

你可能感兴趣的文章

mcrypt.h not found. Please reinstall libmcrypt”的解决方法

查看>>

管理 Oracle Cluster Registry(OCR)

查看>>

在阿里云ECS（CentOS6.5）上安装mysql

查看>>

Exception Management Architecture Guide

Jenkins+Postman+Newman之API全自动化测试流程

【洛谷P1281 书的复制】二分+动态规划

查看>>

洛谷.3809.[模板]后缀排序(后缀数组倍增) & 学习笔记

在scrapy框架下爬虫中如何实现翻页请求

查看>>

SP1716 GSS3 - Can you answer these queries III(区间最大子段和+单点修改)

查看>>

FastReport(一)

查看>>