woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

STL 查找算法

要给出所有我们在本条款中所考虑到的,我们的从哪儿着手?下面的表格道出了一切。

你想知道的 使用的算法 使用的成员函数
在无序区间 在已序区间 在set或map上 在multiset或multimap上
期望值是否存在? find binary_search count find
期望值是否存在?如果有,第一个等于这个值的对象在哪里? find equal_range find find or lower_bound(see article)
第一个不等于期望值的对象在哪里? find_if lower_bound lower_bound lower_bound
第一个等于期望值的对象在哪里? find_if upper_bound upper_bound upper_bound
有多少对象等于期望值? count equal_range count count
等于期望值的所有对象在哪里? find(迭代) equal_range equal_range equal_range
===============================================================================
Example
// equal_range example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mygreater (int i,int j) { return (i>j); }

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  pair<vector<int>::iterator,vector<int>::iterator> bounds;

  // using default comparison:
  sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=equal_range (v.begin(), v.end(), 20);            //          ^        ^

  // using "mygreater" as comp:
  sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=equal_range (v.begin(), v.end(), 20, mygreater); //       ^        ^

  cout << "bounds at positions " << int(bounds.first - v.begin());
  cout << " and " << int(bounds.second - v.begin()) << endl;

  return 0;
}

Output:

bounds ar positions 2 and 5
=================================================================

equal_range()
template< class ForwardIterator, class Type >
pair< ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,                 ForwardIterator last, const Type &value );
//返回pair ,若容器中存在搜索值,第一个返回by lower_bound(); 第二个 by upper_bound(); 
               若容器中不存在搜索值,两个都返回by upper_bound();            template< class ForwardIterator, class Type, class Compare >
pair< ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,                 ForwardIterator last, const Type &value,                 Compare comp );

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include<functional>
using namespace std;
/* generates:
      array element sequence after sort:
      12 15 17 19 20 22 23 26 29 35 40 51
      equal_range result of search for value 23:
              *ia_iter.first: 23         *ia_iter.second: 26
      equal_range result of search for absent value 21:
              *ia_iter.first: 22         *ia_iter.second: 22
      vector element sequence after sort:
      51 40 35 29 26 23 22 20 19 17 15 12
      equal_range result of search for value 26:
              *ivec_iter.first: 26       *ivec_iter.second: 23
      equal_range result of search for absent value 21:
              *ivec_iter.first: 20       *ivec_iter.second: 20
      */

int main()
{
      int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
      vector< int > ivec( ia, ia+12 );
      ostream_iterator< int >     ofile( cout, " " );
      sort( &ia[0], &ia[12] );
      cout << "array element sequence after sort:\n";
      copy( ia, ia+12, ofile ); cout << "\n\n";
      pair< int*,int* > ia_iter;
      ia_iter = equal_range( &ia[0], &ia[12], 23 );
      cout << "equal_range result of search for value 23:\n\t"
           << "*ia_iter.first: "     << *ia_iter.first << "\t"
           << "*ia_iter.second: " << *ia_iter.second << "\n\n";
      ia_iter = equal_range( &ia[0], &ia[12], 21 );
      cout << "equal_range result of search for "
           << "absent value 21:\n\t"
           << "*ia_iter.first: "     << *ia_iter.first << "\t"
           << "*ia_iter.second: " << *ia_iter.second << "\n\n";
      sort( ivec.begin(), ivec.end(), greater<int>() );
      cout << "vector element sequence after sort:\n";
      copy( ivec.begin(), ivec.end(), ofile ); cout << "\n\n";
      typedef vector< int>::iterator iter_ivec;
      pair< iter_ivec, iter_ivec > ivec_iter;
      ivec_iter = equal_range( ivec.begin(), ivec.end(), 26,
                  greater<int>() );
      cout << "equal_range result of search for value 26:\n\t"
           << "*ivec_iter.first: "     << *ivec_iter.first << "\t"
           << "*ivec_iter.second: " << *ivec_iter.second
         ;
      ivec_iter = equal_range( ivec.begin(), ivec.end(), 21,
                  greater<int>() );
      cout << "equal_range result of search for "
           << "absent value 21:\n\t"
           << "*ivec_iter.first: "     << *ivec_iter.first << "\t"
           << "*ivec_iter.second: " << *ivec_iter.second
           ;
}

posted on 2008-07-04 13:36 肥仔 阅读(1182) 评论(0)  编辑 收藏 引用 所属分类: Boost & STL


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理