STL algorithm 查找函数 find find_if count count_if search search_n

清疚 2021-06-24 15:58 364阅读 0赞

## **元素查找** ##

**find：**  
从给定区间中查找单个元素

it = find (myvector.begin(), myvector.end(), 30);
    if (it != myvector.end()){}

**find\_if和find\_if\_not :**  
从给定区间中找出满足比较函数的第一个元素.

bool IsOdd (int i) { return ((i%2)==1); }
    it = find (myvector.begin(), myvector.end(), 30);
    if (it != myvector.end()){}

从给定区间中找出不满足比较函数的第一个元素.

array<int,5> foo = {
       1,2,3,4,5};
    array<int,5>::iterator it =
    find_if_not (foo.begin(), foo.end(), [](int i){
       return i%2;} ); //2%2=0返回false，不满足要求,位置1，值2

**count:**  
统计区间中某个元素出现的次数.

mycount = count (myvector.begin(), myvector.end(), 20);

**count\_if:**  
统计区间中满足比较函数的元素出现的次数.

bool IsOdd (int i) { return ((i%2)==1); }
    int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);

**search\_n：**  
来查找区间中重复出现n次的元素。

it = search_n (myvector.begin(), myvector.end(), 2, 30);   //查找元素30第二次出现的位置
    
    bool mypredicate (int i, int j) {
      return (i==j);
    }
    it = search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);   //支持自定义函数

**adjacent\_find：**  
查询区间中元素重复出现的位置。

bool myfunction (int i, int j) {
      return (i==j);
    }
    int main () {
      int myints[] = {
       5,20,5,30,30,20,10,10,20};
      std::vector<int> myvector (myints,myints+8);
      std::vector<int>::iterator it;
      it = std::adjacent_find (myvector.begin(), myvector.end());  //30重复出现了
      it = std::adjacent_find (++it, myvector.end(), myfunction);   //10重复出现了
    
    }

**lower\_bound和upper\_bound：**  
lower\_bound()在一个**排序**的区间中查找第一个不小于给定元素的值。  
upper\_bound()在一个**排序**的区间中查找第一个大于给定元素的值。

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); // 3 位置20，第一个不小于20 
    up= std::upper_bound (v.begin(), v.end(), 20); // 6 位置30，第一个大于20

**equal\_range：**  
查找**有序**区间的上下边界

sort (v.begin(), v.end());  // 10 10 10 20 20 20 30 30
    bounds=equal_range(v.begin(), v.end(), 20); //  位置 3 6
    sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10
    bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //     位置 2 5
    cout << "bounds at positions " << (bounds.first - v.begin());
    cout << " and " << (bounds.second - v.begin());

**binary\_search：**  
**有序**区间中使用二分法查找元素是否在这个区间中。

if(binary_search (v.begin(), v.end(), 3)) //返回bool值

**min\_element和max\_element：**  
min\_element() 在给定区间中查找出最小值;max\_element() 查找最大值。返回位置

bool myfn(int i, int j) { return i<j; }
    
    struct myclass {
      bool operator() (int i,int j) { return i<j; }
    } myobj;
    
    int main () {
      int myints[] = {
       3,7,2,5,6,4,9};
    
    cout <<*min_element(myints,myints+7) << '\n'; //2
    cout <<*max_element(myints,myints+7) << '\n'; //9
    
    // using function myfn as comp:
    cout <<*min_element(myints,myints+7,myfn) << '\n';  //2
    cout <<*max_element(myints,myints+7,myfn) << '\n';  //9
    
      // using object myobj as comp:
    cout <<*min_element(myints,myints+7,myobj) << '\n';  //2
    cout <<*max_element(myints,myints+7,myobj) << '\n'; //9
    
    return 0;
    }

**max和min：**  
两个元素比较，求最大值和最小值，返回值

min(1,2)==1
    min(2,1)==1
    max('a','z')==z
    max(3.14,2.73)==3.14

**minmax和minmax\_element：**  
求最小和最大，注意二者返回值区别。

auto result = std::minmax({1,2,3,4,5});
    cout << result.first << ' ' << result.second;  //1 5

int main () {
    array<int,7> foo {
       3,7,2,9,5,8,6};
    auto result = std::minmax_element (foo.begin(),foo.end());
    cout << "min is " << *result.first; //2
    cout << ", at position " << (result.first-foo.begin()) << '\n';  //2
    cout << "max is " << *result.second; //9
    cout << ", at position " << (result.second-foo.begin()) << '\n';  //3
      return 0;
    }

## **区间查找** ##

**search：**  
查找子区间第一次出现的位置

// haystack: 10 20 30 40 50 60 70 80 90
    for (int i=1; i<10; i++) haystack.push_back(i*10);
    int needle1[] = {
       40,50,60,70};
    vector<int>::iterator it;
    it = search (haystack.begin(), haystack.end(), needle1, needle1+4); //查找needle是否在haystack中，返回位置3
    
    // 自定义比较函数
    bool mypredicate (int i, int j) {
      return (i<j);
    }
    int needle2[] = {
       30,40,50};
    it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate); //10<30,20<40,30<50，返回位置0,
    if (it!=haystack.end())

**find\_end：**  
查找子区间最后一次出现的位置

int myints[] = {
       1,2,3,4,5,1,2,3,4,5};
    vector<int> haystack (myints,myints+10);
    int needle1[] = {
       1,2,3};
    vector<int>::iterator it;
    it = std::find_end (haystack.begin(), haystack.end(), needle1, needle1+3); //位置5,支持自定义函数

**equal：**  
equal() 判断两个区间是否相等

equal (myvector.begin(), myvector.end(), myints, mypredicate) )  //返回bool

**mismatch：**  
查询两个区间首次出现不同的位置

bool mypredicate (int i, int j) {
      return (i==j);
    }
    
    int main () {
    vector<int> myvector;
    for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50
    
    int myints[] = {
       10,20,80,320,1024};                // myints: 10 20 80 320 1024
    
    pair<vector<int>::iterator,int*> mypair;
    
      // using default comparison:
    mypair = mismatch (myvector.begin(), myvector.end(), myints);
    cout << "First mismatching elements: " << *mypair.first;
    cout << " and " << *mypair.second << '\n';
    
    ++mypair.first; ++mypair.second;
    
    // using predicate comparison:
    mypair = mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);
    cout << "Second mismatching elements: " << *mypair.first;
    cout << " and " << *mypair.second << '\n';
      return 0;
    }
    
    First mismatching elements: 30 and 80
    Second mismatching elements: 40 and 320

## **集合查找** ##

**find\_first\_of：**  
查找给定集合中的任意一个元素。

bool comp_case_insensitive (char c1, char c2) {
      return (std::tolower(c1)==std::tolower(c2));
    }
    
    int main () {
      int mychars[] = {
       'a','b','c','A','B','C'};
      std::vector<char> haystack (mychars,mychars+6);
      std::vector<char>::iterator it;
      int needle[] = {
       'A','B','C'};
    
    
      it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3);
      if (it!=haystack.end())
        std::cout << "The first match is: " << *it << '\n';
    
      it = find_first_of (haystack.begin(), haystack.end(),
                          needle, needle+3, comp_case_insensitive);
      if (it!=haystack.end())
        std::cout << "The first match is: " << *it << '\n';
      return 0;
    }
    
    The first match is: A
    The first match is: a