經常使用的STL查找算法。本站提示廣大學習愛好者:(經常使用的STL查找算法)文章只能為提供參考,不一定能成為您想要的結果。以下是經常使用的STL查找算法正文
《effective STL》中有句忠言,盡可能用算法替換手寫輪回;查找少不了輪回遍歷,在這裡總結下經常使用的STL查找算法;
查找有三種,即點線面:
點就是查找目的為單個元素;
線就是查找目的為區間;
面就是查找目的為聚集;
針對每一個種別的查找,默許的比擬函數是相等,為了知足更豐碩的需求,算法也都供給了自界說比擬函數的版本;
單個元素查找
find() 比擬前提為相等的查找
find()從給定區間中查找單個元素,界說:
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
示例,從myvector中查找30:
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() 自界說比擬函數
std::find_if():從給定區間中找出知足比擬函數的第一個元素;
示例,從myvector中查找可以或許被30整除的第一個元素:
bool cmpFunction (int i) {
return ((i%30)==0);
}
it = std::find_if (myvector.begin(), myvector.end(), cmpFunction);
std::cout << "first:" << *it <<std::endl;
count() 統計元素湧現次數
std::count():統計區間中某個元素湧現的次數;
std:count_if():count()的自界說比擬函數版本
search_n() 查詢單個元素反復湧現的地位
search_n(): find用來查詢單個元素,search_n則用來查找區間中反復湧現n次的元素;
示例:查詢myvector中30持續湧現2次的地位:
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() 支撐自界說比擬函數;
adjacent_find() 查詢區間中反復元素湧現的地位
adjacent_find() 查詢區間中反復元素湧現的地位,該算法支撐自界說比擬函數;
lower_bound() 有序區間中查詢元素界限
lower_bound()用來在一個排序的區間中查找第一個不小於給定元素的值:
示例:查找容器v中不小於20的下界:
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(),查找有序區間中第一個年夜於給定元素的值;
還有equal_range(),查找有序區間的高低界限;(一次前往lower_bound()和upper_bound());
binary_search() 有序區間的二分查找
binary_search() 用來在一個有序區間中應用二分法查找元素能否在這個區間中,注,這個算法的前往值為bool,
不是下標地位,其外部的算法邏輯和lower_bound()類似,行動表示為:
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));
}
示例:從有序區間v中找3能否存在:
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() 在給定區間中查找出最小值;
int myints[] = {3,7,2,5,6,4,9};
std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';
相似算法有:max_element() 查找最年夜值;
區間查找 search()
search() 查找子區間初次湧現的地位
find()用來查找單個元素,search()則用來查找一個子區間;
示例:從myvector中查找湧現子區間[20,30]的地位:
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支撐自界說比擬函數;
示例:查詢給定區間中每一個元素比目的區間小1的子區間;
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() 查找子區間最初一次湧現的地位
search() 用來查找子區間第一次湧現的地位,而find_end()用來查找子區間最初一次湧現的地位:
find_end()支撐自界說比擬函數;
equal() 斷定兩個區間能否相等
equal()用來斷定兩個區間能否相等,該算法支撐自界說比擬函數;
mismatch() 查詢兩個區間初次湧現分歧的地位;
mismatch() 查詢兩個區間起首湧現分歧的地位,這個算法也支撐自界說比擬函數;
聚集查找
find_first_of 查找聚集中的隨意率性一個元素
find_first_of()用來查找給定聚集中的隨意率性一個元素:
示例:從haystack中查找A,B,C湧現的地位:
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支撐自界說比擬函數;
以上所述就是本文的全體內容了,願望年夜家可以或許愛好。