常用的STL查找算法

更新時間：2015年07月01日 09:53:54 投稿：hebedich

這篇文章主要介紹了常用的STL查找算法的相關(guān)資料，十分的詳細(xì),需要的朋友可以參考下

《effective STL》中有句忠告，盡量用算法替代手寫循環(huán)；查找少不了循環(huán)遍歷，在這里總結(jié)下常用的STL查找算法；

查找有三種，即點(diǎn)線面：
點(diǎn)就是查找目標(biāo)為單個元素；
線就是查找目標(biāo)為區(qū)間；
面就是查找目標(biāo)為集合；

針對每個類別的查找，默認(rèn)的比較函數(shù)是相等，為了滿足更豐富的需求，算法也都提供了自定義比較函數(shù)的版本；

單個元素查找

find() 比較條件為相等的查找

find()從給定區(qū)間中查找單個元素,定義：

復(fù)制代碼代碼如下:

template <class InputIterator, class T>

InputIterator find (InputIterator first, InputIterator last, const T& val);

示例，從myvector中查找30：

復(fù)制代碼代碼如下:

int myints[] = { 10, 20, 30, 40 };

std::vector<int> myvector (myints,myints+4);

it = find (myvector.begin(), myvector.end(), 30);

if (it != myvector.end())

    std::cout << "Element found in myvector: " << *it << '\n';

else

    std::cout << "Element not found in myvector\n";

find_if() 自定義比較函數(shù)

std::find_if():從給定區(qū)間中找出滿足比較函數(shù)的第一個元素；
示例,從myvector中查找能夠被30整除的第一個元素：

復(fù)制代碼代碼如下:

bool cmpFunction (int i) {

  return ((i%30)==0);

}

it = std::find_if (myvector.begin(), myvector.end(), cmpFunction);

std::cout << "first:" <<  *it <<std::endl;

count() 統(tǒng)計(jì)元素出現(xiàn)次數(shù)

std::count()：統(tǒng)計(jì)區(qū)間中某個元素出現(xiàn)的次數(shù)；
std:count_if()：count()的自定義比較函數(shù)版本

search_n() 查詢單個元素重復(fù)出現(xiàn)的位置

search_n(): find用來查詢單個元素，search_n則用來查找區(qū)間中重復(fù)出現(xiàn)n次的元素；

示例：查詢myvector中30連續(xù)出現(xiàn)2次的位置：

復(fù)制代碼代碼如下:

int myints[]={10,20,30,30,20,10,10,20};

std::vector<int> myvector (myints,myints+8);

it = std::search_n (myvector.begin(), myvector.end(), 2, 30);

search_n() 支持自定義比較函數(shù)；

adjacent_find() 查詢區(qū)間中重復(fù)元素出現(xiàn)的位置

adjacent_find() 查詢區(qū)間中重復(fù)元素出現(xiàn)的位置，該算法支持自定義比較函數(shù)；

lower_bound() 有序區(qū)間中查詢元素邊界

lower_bound()用來在一個排序的區(qū)間中查找第一個不小于給定元素的值：
示例：查找容器v中不小于20的下界：

復(fù)制代碼代碼如下:

int myints[] = {10,20,30,30,20,10,10,20};

std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

std::vector<int>::iterator low,up;

low=std::lower_bound (v.begin(), v.end(), 20); 

std::cout << "lower_bound at position " << (low- v.begin()) << '\n';

類似算法有upper_bound(),查找有序區(qū)間中第一個大于給定元素的值；
還有equal_range(),查找有序區(qū)間的上下邊界；（一次返回lower_bound()和upper_bound());

binary_search() 有序區(qū)間的二分查找

binary_search() 用來在一個有序區(qū)間中使用二分法查找元素是否在這個區(qū)間中，注，這個算法的返回值為bool，
不是下標(biāo)位置，其內(nèi)部的算法邏輯和lower_bound（）相似，行為表現(xiàn)為：

復(fù)制代碼代碼如下:

template <class ForwardIterator, class T>

  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)

{

  first = std::lower_bound(first,last,val);

  return (first!=last && !(val<*first));

}

示例：從有序區(qū)間v中找3是否存在：

復(fù)制代碼代碼如下:

int myints[] = {1,2,3,4,5,4,3,2,1};

std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

std::sort (v.begin(), v.end());

if (std::binary_search (v.begin(), v.end(), 3))

    std::cout << "found!\n"; else std::cout << "not found.\n";

min_element() 查找最小元素

min_element() 在給定區(qū)間中查找出最小值;

復(fù)制代碼代碼如下:

int myints[] = {3,7,2,5,6,4,9};

std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';

類似算法有：max_element() 查找最大值；

區(qū)間查找 search()

search() 查找子區(qū)間首次出現(xiàn)的位置

find()用來查找單個元素，search()則用來查找一個子區(qū)間；
示例：從myvector中查找出現(xiàn)子區(qū)間[20，30]的位置:

復(fù)制代碼代碼如下:

  int needle1[] = {20,30};

  it = std::search (myvector.begin(), myvector.end(), needle1, needle1+2);

  if (it!=myvector.end())

    std::cout << "needle1 found at position " << (it-myvector.begin()) << '\n';

search支持自定義比較函數(shù)；
示例：查詢給定區(qū)間中每個元素比目標(biāo)區(qū)間小1的子區(qū)間；

復(fù)制代碼代碼如下:

bool cmpFunction (int i, int j) {

  return (i-j==1);

}

int myints[] = {1,2,3,4,5,1,2,3,4,5};

std::vector<int> haystack (myints,myints+10);

int needle2[] = {1,2,3};

// using predicate comparison:

it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, cmpFunction);

find_end() 查找子區(qū)間最后一次出現(xiàn)的位置

search() 用來查找子區(qū)間第一次出現(xiàn)的位置，而find_end()用來查找子區(qū)間最后一次出現(xiàn)的位置：
find_end()支持自定義比較函數(shù)；

equal() 判斷兩個區(qū)間是否相等

equal（）用來判斷兩個區(qū)間是否相等，該算法支持自定義比較函數(shù)；

mismatch() 查詢兩個區(qū)間首次出現(xiàn)不同的位置；

mismatch() 查詢兩個區(qū)間首先出現(xiàn)不同的位置，這個算法也支持自定義比較函數(shù)；

集合查找

find_first_of 查找集合中的任意一個元素

find_first_of()用來查找給定集合中的任意一個元素:
示例：從haystack中查找A,B,C出現(xiàn)的位置：

復(fù)制代碼代碼如下:

  int mychars[] = {'a','b','c','A','B','C'};

  std::vector<char> haystack (mychars,mychars+6);

  int needle[] = {'C','B','A'};

  // using default comparison:

  it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3);

find_first_of支持自定義比較函數(shù)；

以上所述就是本文的全部內(nèi)容了，希望大家能夠喜歡。

您可能感興趣的文章: