这几天对到底选用哪个容器，用哪种形式的find函数有一些迷惑的地方。
工作之后，花些时间对这些常用的东西做一个总结，方便以后翻阅所用。

1.通用std::find 函数

例子1：

// find example
#include <iostream>
#include <algorithm>
#include <vector>
usingnamespacestd;
 
intmain () {
  intmyints[] = { 10, 20, 30 ,40 };
  int* p;
 
  // pointer to array element:
  p = find(myints,myints+4,30);
  ++p;
  cout << "The element following 30 is " << *p << endl;
 
  vector<int> myvector (myints,myints+4);
  vector<int>::iterator it;
 
  // iterator to vector element:
  it = find (myvector.begin(), myvector.end(), 30);
  ++it;
  cout << "The element following 30 is " << *it << endl;
 
  return0;
}

std::find函数的确有很好的通用性，但是也有很大的缺点，就是算法的效率不高，算法的复杂度为O(n)。无码无真相，让我们看一下 std::find 算法 SGI实现版本：

template
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}

我们可以看到如果找不到，最后find将会返回 last，切记这里的last而非容器的最后一个元素，而是容器的最后。如果想深入了解，请参照《STL源码分析》或者《C++标准程序库》。
（*PS，如果仅仅查找一个元素是否存在，用find_if会更明了一些，虽然find和find_if的算法复杂度是相当的。）

2.特定容器的find算法。
当数据量是百万或者千万级的时候，std::find的O(n)算法就让程序或者客户感到销魂了。
这时候我们可以考虑使用map或者set的算法。是的，这里的find，是map和set的一个成员函数，一个研究ACM的朋友，告诉我map和set中的find算法是用红黑树来实现的。拿起之前的算法的资料，了解到黑红输有良好的最坏情况运行时间，算法复杂度为O(logn)。
这样，百万或者千万级的查找就不再话下了。

// set::find
#include <iostream>
#include <set>
usingnamespacestd;
 
intmain ()
{
  set<int> myset;
  set<int>::iterator it;
 
  // set some initial values:
  for(inti=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50
 
  it=myset.find(20);
  myset.erase (it);
  myset.erase (myset.find(40));
 
  cout << "myset contains:";
  for(it=myset.begin(); it!=myset.end(); it++)
    cout << " " << *it;
  cout << endl;
 
  return0;
}

// map::find
#include <iostream>
#include <map>
usingnamespacestd;
 
intmain ()
{
  map<char,int> mymap;
  map<char,int>::iterator it;
 
  mymap['a']=50;
  mymap['b']=100;
  mymap['c']=150;
  mymap['d']=200;
 
  it=mymap.find('b');
  mymap.erase (it);
  mymap.erase (mymap.find('d'));
 
  // print content:
  cout << "elements in mymap:" << endl;
  cout << "a => " << mymap.find('a')->second << endl;
  cout << "c => " << mymap.find('c')->second << endl;
 
  return0;
}

3.最后有必要说一下就是multimap 和 multiset 的find 。因为这两个容器都可以存放相同键值的数据。所以说find一个键值本可以返回多个结果，但是你这样想就错了。 multiset 和multimap只会返回第一个结果 。如果要得到相同的键值的所有结果可以用以下的方式,还要需要注意的一点set,map是重载了[]操作符的，所以可以像数组或者vector那样直接访问，但是multiset和multimap是没有的，所以必须要用find一类的方法。（multiset同理此处略去）

方式一：
    typedefstd::multimap<int,int> Pairs;
    multimap<int,int>::iterator iter;
    Pairs pairs;
    pairs.insert(make_pair(1, 1));
    pairs.insert(make_pair(1,2));
    pairs.insert(make_pair(1,3));
    pairs.insert(make_pair(2, 4));
    pairs.insert(make_pair(2,5));
    pairs.insert(make_pair(3,2));
    intkey = 1;
    Pairs::iterator position = pairs.lower_bound(key);
    while(position != pairs.upper_bound(key))
    {
        cout << position->first << "\t"<< position->second;
        ++position;
    }
方式二：
    typedefstd::multimap<int,int> Pairs;
    multimap<int,int>::iterator iter;
    Pairs pairs;
    pairs.insert(make_pair(1, 1));
    pairs.insert(make_pair(1,2));
    pairs.insert(make_pair(1,3));
    pairs.insert(make_pair(2, 4));
    pairs.insert(make_pair(2,5));
    pairs.insert(make_pair(3,2));
 
    iter = pairs.find(1);    //find返回的是第一个找到的元素的位置
    if(iter == pairs.end()) cout << "can not find 2\n";  //注意判断没有找到的办法
    elsecout << iter->second << endl;
 
    pair<Pairs::iterator, Pairs::iterator> range; //前面说了find只能返回第一个位置
    range = pairs.equal_range(1);             //要是想得到全部，只能这样啦
    for(iter = range.first; iter != range.second; iter++)
            cout << iter->first << " " << iter->second << endl;

3. boost bimap和 boost unordered_map的find方法。

因为此处重点对STL的说明，关于bimap和unordered_map的find方法，请参看本博客下一篇博文。