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+));
}