STL_算法_01_查找算法

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：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <string>
 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 // ZC: 自己编写的 相邻条件判断 的函数对象
 class TestAdjacent
 {
 public:
     bool operator()(int _i, int _j)
     {
         return _i == _j ? true : false;

         // ZC: 相邻条件判断:_i是_j的一半，只要满足这个条件adjacent_find()就会返回_i所对应的iterator
         //return return _i == (_j / 2) ? true : false;
     }
 };

 void main()
 {
     vector<int> v;
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();

     // ZC: 第1种 参数格式
     vector<int>::iterator it =  adjacent_find(v.begin(), v.end());
     printf("%d, 0x%08X\n", *it, *it);
     if (it == v.end())
     {
         printf("it == v.end()\n");
         printf("0x%08X, 0x%08X\n", it, v.end());
     }

     it =  adjacent_find(it, v.end());
     printf("%d, 0x%08X\n", *it, *it);

     it ++;
     it =  adjacent_find(it, v.end());
     printf("%d, 0x%08X\n", *it, *it);

     // ***
     printf("\n");

     // ZC: 第2种 参数格式
     it = adjacent_find(v.begin(), v.end(), TestAdjacent());
     if (it == v.end())
     {
         printf("it == v.end()\n");
         printf("0x%08X, 0x%08X\n", it, v.end());
     }
     else
         printf("%d, 0x%08X\n", *it, *it);
 }

控制台输出为：

 2, 0x00000002
 2, 0x00000002
 5, 0x00000005

 2, 0x00000002
 Press any key to continue

(2)、测试代码 - 2：

     vector<int> v;
     v.push_back();
     //v.push_back(2);
     v.push_back();
     v.push_back();
     v.push_back();
     v.push_back();
     //v.push_back(5);
     //v.push_back(5);
     v.push_back();
     v.push_back();

     vector<int>::iterator it =  adjacent_find(v.begin(), v.end());
     printf("%d, 0x%08X\n", *it, *it);
     if (it == v.end())
     {
         printf("it == v.end()\n");
         printf("0x%08X, 0x%08X\n", it, v.end());
     }

控制台输出：

 -842150451, 0xCDCDCDCD
 it == v.end()
 0x00272D9C, 0x00272D9C
 Press any key to continue

1.2、第6讲 PPT.17

◆ binary_search():   在有序序列中查找value,找到则返回true。注意：在无序序列中，不可使用。

　　ZC：两分查找

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

ZC: VC6 测试代码：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 // ZC: 两分查找所使用的 比较函数对象
 class CompareIntFunctor
 {
 public:
     bool operator () (const int _iLeft, const int _iRight)
     {
         // ZC: 这里是使用"<"还是">"，就要看 set<int> 中使用的是何种排序方式了。
         // ZC: 注意，貌似 使用"<="或者">=" 得不到想要的结果...
         return _iLeft < _iRight;
     }
 };

 // ZC: 两分查找所使用的 比较函数
 bool CompareInt (const int _iLeft, const int _iRight)
 {
     return _iLeft < _iRight;
 }

 void main()
 {
     set<int> setInt;
     setInt.insert();
     setInt.insert();
     setInt.insert();
     setInt.insert();
     setInt.insert();

     bool bFind = binary_search(setInt.begin(), setInt.end(), , CompareIntFunctor()); // 参数格式 - 1
     printf("bFind : %d\n", bFind);

     bFind = binary_search(setInt.begin(), setInt.end(), , CompareInt); // 参数格式 - 1
     printf("bFind : %d\n", bFind);

     bFind = binary_search(setInt.begin(), setInt.end(), ); // 参数格式 - 2
     printf("bFind : %d\n", bFind);

     bFind = binary_search(setInt.begin(), setInt.end(), ); // 参数格式 - 2
     printf("bFind : %d\n", bFind);
 }

ZC：控制台输出为：

 bFind : 1
 bFind : 1
 bFind : 1
 bFind : 0
 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 <vector>
 6 #include <set>
 7
 8 #include <algorithm>    // 算法
 9 #include <numeric>    // 算法
10 #include <functional>    // 算法
11
12 using namespace std;
13
14 void main()
15 {
16     // (1)、无序容器 且 未经过排序
17     vector<int> 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<vector<int>::iterator, vector<int>::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<int>::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<int> 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<multiset<int>::iterator, multiset<int>::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<int>::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 <vector>
 6 #include <set>
 7
 8 #include <algorithm>    // 算法
 9 #include <numeric>    // 算法
10 #include <functional>    // 算法
11
12 using namespace std;
13
14 class TStudent
15 {
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<TStudent, Compare> setStu; // ZC: 这里传 函数指针 是不行的，只能传 函数对象
46     set<TStudent, StuFunctor> 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<set<TStudent, StuFunctor>::iterator, set<TStudent, StuFunctor>::iterator> pair1 = equal_range(setStu.begin(), setStu.end(), 1, StuFunctor());
55     set<TStudent, StuFunctor>::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<set<TStudent, StuFunctor>::iterator, set<TStudent, StuFunctor>::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 == > 1001
2 *** *** *** *** ***
3 2 == > 1002
4 Press any key to continue

1.4、第6讲 PPT.18

◆ count() :     利用等于操作符，把标志范围内的元素与输入值比较，返回相等的个数。

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

ZC：VC6测试代码：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 void main()
 {
     vector<int> vecInt;
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();

     int iCount = count(vecInt.begin(), vecInt.end(), );    //iCount==3
     printf("iCount : %d\n", iCount);
 }

ZC: 控制台输出：

 iCount : 3
 Press any key to continue

1.5、第6讲 PPT.18

◆ count_if() :  利用输入的函数，对标志范围内的元素进行比较操作，返回结果为true的个数。

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

ZC: VC6测试代码：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 //先定义比较函数
 bool GreaterThree(int iNum)
 {
     if (iNum >= )
     {
         return true;
     }
     else
     {
         return false;
     }
 }

 void main()
 {
     vector<int> vecInt;
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();

     int iCount = count_if(vecInt.begin(), vecInt.end(), GreaterThree);// ZC: 注意这里传入的是比较函数的函数地址
     printf("iCount : %d\n", iCount);
 }

ZC：控制台输出：

 iCount : 2
 Press any key to continue

1.6、第6讲 PPT.22

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

ZC: VC6 测试代码：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 void main()
 {
     vector<int> vecInt;
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();

     vector<int>::iterator it = find(vecInt.begin(), vecInt.end(), );    //*it == 5
     printf("*it : %d\n", *it);
 }

ZC：控制台输出：

 *it : 5
 Press any key to continue

1.7、第6讲 PPT.23

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

ZC: VC6 测试代码：

 #ifdef WIN32
 #pragma warning (disable: 4786)
 #endif

 #include <vector>
 #include <set>

 #include <algorithm>    // 算法
 #include <numeric>    // 算法
 #include <functional>    // 算法

 using namespace std;

 bool GreaterThree(int iNum)
 {
     if (iNum >= )
     {
         return true;
     }
     else
     {
         return false;
     }
 }

 void main()
 {
     vector<int> vecInt;
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();
     vecInt.push_back();

     vector<int>::iterator it = find_if(vecInt.begin(), vecInt.end(), GreaterThree);
     printf("*it : %d\n", *it);
     printf("*(it+1) : %d\n", *(it+));
     printf("*(it+2) : %d\n", *(it+));
     printf("*(it+3) : %d\n", *(it+));
 }

ZC：控制台输出：

 *it : 3
 *(it+1) : 5
 *(it+2) : 7
 *(it+3) : 9
 Press any key to continue

?.?、第6讲 PPT.?

◆

ZC: VC6 测试代码：

ZC：控制台输出：

X