不造轮子之STL中的查找算法

程序员的园

发布于 2024-09-27 18:41:16

1000

发布于 2024-09-27 18:41:16

文章被收录于专栏：程序员的园——原创文章

在日常的开发中，常涉及到容器的常见操作，如查找、删除、排序等，C++ STL提供了丰富的算法库，可以方便地完成这些操作。为了避免重复造轮子，同时为了提高效率，了解常见的STL算法是非常有必要的。本文将介绍查找相关算法。

1. std::find

功能：查找范围内第一个满足条件的元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found 3 at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "3 not found" << std::endl;
    }
}

2. std::find_if

功能：查找范围内第一个满足条件的元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find_if(vec.begin(), vec.end(), [](inti){ return i % 2 == 0; });
    if (it != vec.end()) {
        std::cout << "Found even number at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No even number found" << std::endl;
    }
}

3. std::find_if_not

功能：查找范围内第一个不满足条件的元素。

#include<iostream>
#include<vector>
#include<algorithm>


intmain() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find_if_not(vec.begin(), vec.end(), [](inti){ return i % 2 == 0; });
    if (it != vec.end()) {
        std::cout << "Found odd number at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "All numbers are even" << std::endl;
    }
}

4. std::find_end

功能：在范围内查找最后一个子序列的位置,注意是子序列，不是子序列内的某个或某几个元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 3, 4, 5};
    std::vector<int> sub = {3, 4, 5}; // 子序列
    auto it = std::find_end(vec.begin(), vec.end(), sub.begin(), sub.end());
    if (it != vec.end()) {
        std::cout << "Last occurrence of subsequence found at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found" << std::endl;
    }
}

5. std::find_first_of

功能：在范围内查找第一个与给定集合中任意元素匹配的元素的位置。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> sub = {3, 4, 6}; // 子序列
    auto it = std::find_first_of(vec.begin(), vec.end(), sub.begin(), sub.end());
    if (it != vec.end()) {
        std::cout << "First match found at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No match found" << std::endl;
    }
}

6. std::adjacent_find

功能：查找范围内第一个相邻元素对的位置。

#include<iostream>
#include<vector>
#include<algorithm>


intmain() {
    std::vector<int> vec = {1, 2, 2, 3, 4, 5};
    auto it = std::adjacent_find(vec.begin(), vec.end());
    if (it != vec.end()) {
        std::cout << "Found adjacent pair at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No adjacent pair found" << std::endl;
    }
}

7. std::binary_search

功能：在已排序的范围内查找元素是否存在。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    bool found = std::binary_search(vec.begin(), vec.end(), 3); // 3 is in the vector
    if (found) {
        std::cout << "3 found" << std::endl;
    } else {
        std::cout << "3 not found" << std::endl;
    }
}

8. std::upper_bound

功能：在有序范围中查找第一个大于指定值的元素的位置。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto it = std::upper_bound(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "First element greater than 3 is: " << *it << std::endl;
    } else {
        std::cout << "No element greater than 3 found" << std::endl;
    }
}

9. std::lower_bound

功能：在有序范围中查找第一个大于等于指定值的元素的位置，与std::upper_bound 类似。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto it = std::lower_bound(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "First element greater than or equal to 3 is: " << *it << std::endl;
    } else {
        std::cout << "No element greater than or equal to 3 found" << std::endl;
    }
}

10. std::equal_range

功能：在有序范围中查找等于指定值的元素的范围。std::equal_range 返回一个 std::pair，其中 first 指向范围的开始（等于指定元素），second 指向范围的结束（第一个大于指定元素的元素）。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto range = std::equal_range(vec.begin(), vec.end(), 4);
    std::cout << "Range of 4: [" << std::distance(vec.begin(), range.first) << ", " << std::distance(vec.begin(), range.second) << "]" << std::endl;
}

11. std::search

功能：在范围内查找子序列的位置，注意是子序列的位置，不是子序列内的某个或某几个元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> sub = {3, 4}; // 子序列
    auto it = std::search(vec.begin(), vec.end(), sub.begin(), sub.end());
    if (it != vec.end()) {
        std::cout << "Subsequence found at index: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found" << std::endl;
    }
}

12. std::mismatch

功能：在两个范围内查找第一个不匹配的位置。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {1, 2, 4, 4, 5};


    // 查找第一个不匹配的元素对
    auto result = std::mismatch(vec1.begin(), vec1.end(), vec2.begin());


    if (result.first != vec1.end() || result.second != vec2.end()) {
        std::cout << "First mismatch found at vec1[" << (result.first - vec1.begin()) << "] = " << *(result.first)
                  << " and vec2[" << (result.second - vec2.begin()) << "] = " << *(result.second) << std::endl;
    } else {
        std::cout << "No mismatch found, vectors are identical." << std::endl;
    }


    // 使用自定义谓词查找第一个不匹配的元素对
    auto result_pred = std::mismatch(vec1.begin(), vec1.end(), vec2.begin(), [](inta, intb) { return a != b; });


    if (result_pred.first != vec1.end() || result_pred.second != vec2.end()) {
        std::cout << "First mismatch found at vec1[" << (result_pred.first - vec1.begin()) << "] = " << *(result_pred.first)
                  << " and vec2[" << (result_pred.second - vec2.begin()) << "] = " << *(result_pred.second) << std::endl;
    } else {
        std::cout << "No mismatch found, vectors are identical according to the predicate." << std::endl;
    }


    return0;
}

13. std::min_element

功能：在范围内查找最小元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::min_element(vec.begin(), vec.end());
    if (it != vec.end()) {
        std::cout << "Minimum element is: " << *it << std::endl;
    } else {
        std::cout << "Vector is empty" << std::endl;
}

14. std::max_element

功能：在范围内查找最大元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::max_element(vec.begin(), vec.end());
    if (it != vec.end()) {
        std::cout << "Maximum element is: " << *it << std::endl;
    } else {
        std::cout << "Vector is empty" << std::endl;
    }
}

15. std::minmax_element

功能：在范围内查找最小和最大元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto result = std::minmax_element(vec.begin(), vec.end());
    if (result.first != vec.end() && result.second != vec.end()) {
        std::cout << "Minimum element is: " << *result.first << std::endl;
        std::cout << "Maximum element is: " << *result.second << std::endl;
    } else {
        std::cout << "Vector is empty" << std::endl;
    }
}

16. std::includes

功能：判断一个有序范围是否包含另一个有序范围的所有元素。

#include<iostream>
#include<vector>
#include<algorithm>


int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {3, 4, 5};
    bool result = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
    if (result) {
        std::cout << "vec2 is included in vec1" << std::endl;
    } else {
        std::cout << "vec2 is not included in vec1" << std::endl;
    }
}

总结

C++ 标准库提供了多种查找算法，可以根据不同的需求选择合适的算法。本文介绍了一些常用的查找算法，包括 std::find、std::find_if、std::find_if_not、std::find_first_of、std::find_end、std::adjacent_find、std::upper_bound、std::equal_range、std::search 和 std::mismatch等。希望这些内容对你有所帮助。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除

include