VC语言
本类阅读TOP10
·VC++下使用ADO编写数据库程序
·VC++ 学习笔记(二)
·Windows消息大全
·每个开发人员现在应该下载的十种必备工具
·在2000和xp下，隐藏进程，VC6.0测试通过!!!
·用Visual C++打造IE浏览器(1)
·Netmsg 局域网聊天程序
·教你用VC6做QQ对对碰外挂程序
·VC++学习笔记(四)
·VC++中经常使用的函数！~~
→ 分类导航
软件工程.NET开发
CUJ：标准库：标准库中的搜索算法
作者：未知 来源：月光软件站 加入时间：2005-2-28 月光软件站
The Standard Librarian: Searching in the Standard Library
Matthew Austern
http://www.cuj.com/experts/1911/austern.htm?topic=experts
The genius as well as the oversights in the design of the Standard C++ library surface in a simple discussion of its linear and binary search algorithms.
--------------------------------------------------------------------------------
如果你储存着一系列的元素，或许原因理由之一是因此你能够在它里面找到些对象。在一个集合中找到一个特别的条目是个很重要的问题；所有的书都会写到它。不奇怪，标准C++运行库提供了许多不同的搜索技术。
在 C++运行库中，指明一个集合的常用方法是通过iterator指示出区间。区间可以被写为[first, last)，此处，*first是区间内的第一个元素而last则指向最后一个元素的下一个。本文展示了我们如何考虑一个通用问题：给定一个区间和一个准则，找到指向第一个满足准则的元素的iterator。因为我们将区间表示为不对称的形式，于是避开了一个特殊情况：搜索失败可以返回last，没有任何元素的区间可以写为[i, i)。
线性搜索和它的变种最简单的搜索是线性搜索，或，如Knuth所称呼的，顺序搜索：依次查看每个元素，检查它是否为我们正在搜索的那个。如果区间中有N个元素，最坏的情况就需要N次比较。
标准运行库提供了线性搜索的一些版本；两个最重要的版本是find() (它接受一个区间和值x，并查找等价于x的元素)和find_if()(接受一个区间和判决条件p，并查找满足p的元素)。线性搜索的其它版本是find_first_of()(接受两个区间，[first1,last1)和[first2,last2) ，并在[first1, last1)中查找第一个等价于[first2, last2)中任何一个元素的元素]和adjacent_find()(接受单一区间，并查找第一个等价于其后继元素的元素)。
举例来说，假如，v是一个int的vector。你能用下面的代码查找第一个0：
vector<int>::iterator i =
find(v.begin(), v.end(), 0);
你也能这样查找第一个非0值：
vector<int>::iterator i =
find_if(v.begin(), v.end(),
not1(bind2nd(equal_to<int>(),
0)));
你能这样查找第一个小质数：
A[4] = { 2, 3, 5, 7 };
vector<int>::iterator i =
find_first_of(v.begin(), v.end(),
A+0, A+4);
你能这样找到第一个重复对：
vector<int>::iterator i =
adjacent_find(v.begin(), v.end());
没有任何独立版本以对区间进行逆向搜索，因为你不需要：你能用一个简单的iterator adaptor来达到相同的效果。比如，在v中找到最后一个0，可以这么写：
vector<int>::reverse_iterator i =
find(v.rbegin(), v.rend(), 0);
线性搜索是一个简单的算法，它的实现看起来没什么可讨论的。许多书(包括我的)展示了std::find()的一个简单的实现：
template <class InIter, class T>
InIter find(InIter first, InIter last,
const T& val)
{
while (first != last && !
(*first == val))
