C++ algorithm std::search

C++ <algorithm> std::search

The std::search function template in C++ is used to find the first occurrence of a subsequence within a sequence. It searches for a range of elements (the subsequence) within another range (the sequence) and returns an iterator to the beginning of the first occurrence. This function is part of the <algorithm> header.

Syntax of std::search

</>

Copy

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                         BinaryPredicate pred);

Parameters of std::search

Parameter	Description
`first1, last1`	Forward iterators to the initial and final positions of the sequence to be searched. The range used is `[first1, last1)`, which contains all the elements between `first1` and `last1`, including the element pointed to by `first1` but not the element pointed to by `last1`.
`first2, last2`	Forward iterators to the initial and final positions of the subsequence to search for. The range used is `[first2, last2)`.
`pred` (optional)	Binary function that accepts two elements as arguments (one from each of the two sequences, in the same order) and returns a value convertible to `bool`. The value returned indicates whether the elements are considered to match in the context of this function. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return Value of std::search

The function returns an iterator to the first element of the first occurrence of the subsequence [first2, last2) in the range [first1, last1). If the subsequence is not found, the function returns last1.

Example 1: Searching for a Subsequence in a Vector

In this example, we use std::search to find the first occurrence of a subsequence within a vector of integers.

Program

</>

Copy

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

int main() {
    std::vector<int> sequence = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> subsequence = {4, 5, 6};

    auto it = std::search(sequence.begin(), sequence.end(),
                          subsequence.begin(), subsequence.end());

    if (it != sequence.end()) {
        std::cout << "Subsequence found at position: "
                  << std::distance(sequence.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found." << std::endl;
    }

    return 0;
}

Output

Subsequence found at position: 3

Explanation

We include the necessary headers: <iostream> for input/output operations, <vector> for the std::vector container, and <algorithm> for the std::search function.
We define a vector sequence containing integers from 1 to 9.
We define another vector subsequence containing the integers 4, 5, and 6.
We call std::search, passing iterators to the beginning and end of both the sequence and the subsequence. The function searches for the first occurrence of the subsequence within the sequence.
If the subsequence is found, std::search returns an iterator to the first element of the subsequence within the sequence. We calculate the position by finding the distance from the beginning of the sequence to the iterator and print the position.
If the subsequence is not found, std::search returns sequence.end(), and we print a message indicating that the subsequence was not found.

Example 2: Searching for a Subsequence in a String

In this example, we use std::search to find the first occurrence of a substring within a string.

Program

</>

Copy

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string text = "Hello, this is a simple example.";
    std::string pattern = "simple";

    auto it = std::search(text.begin(), text.end(),
                          pattern.begin(), pattern.end());

    if (it != text.end()) {
        std::cout << "Pattern found at position: "
                  << std::distance(text.begin(), it) << std::endl;
    } else {
        std::cout << "Pattern not found." << std::endl;
    }

    return 0;
}

Output

Pattern found at position: 17

Explanation

We include the necessary headers: <iostream> for input/output operations, <string> for the std::string class, and <algorithm> for the std::search function.
We define a string text containing the sentence “Hello, this is a simple example.”
We define another string pattern containing the word “simple” that we want to search for within the text.
We call std::search, passing iterators to the beginning and end of both the text and the pattern. The function searches for the first occurrence of the pattern within the text.
If the pattern is found, std::search returns an iterator pointing to the beginning of the first occurrence of the pattern. We calculate the position by finding the distance from the beginning of the text to the iterator and print the position.
If the pattern is not found, std::search returns text.end(), and we print a message indicating that the pattern was not found.

Examples for Exceptions Thrown by std::search

The std::search function can throw exceptions in the following scenarios:

If the element comparison or the predicate (pred) throws an exception.
If an operation on the iterators, such as dereferencing or incrementing, throws an exception.

Example 1: Predicate Throws an Exception

This example demonstrates a case where the predicate function throws an exception during execution.

Program

</>

Copy

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

bool faulty_predicate(int a, int b) {
    if (a < 0 || b < 0) {
        throw std::runtime_error("Negative value encountered during comparison.");
    }
    return a == b;
}

int main() {
    std::vector<int> sequence = {1, -2, 3, 4, 5};
    std::vector<int> subsequence = {3, 4};

    try {
        auto it = std::search(sequence.begin(), sequence.end(),
                              subsequence.begin(), subsequence.end(),
                              faulty_predicate);

        if (it != sequence.end()) {
            std::cout << "Subsequence found at position: "
                      << std::distance(sequence.begin(), it) << std::endl;
        } else {
            std::cout << "Subsequence not found." << std::endl;
        }
    } catch (const std::runtime_error& e) {
        std::cout << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output

Exception caught: Negative value encountered during comparison.

Explanation

We define a custom predicate faulty_predicate that throws a std::runtime_error if either input value is negative.
We initialize a vector sequence containing integers, including a negative value, and another vector subsequence with elements to search for.
The std::search function applies the predicate to compare elements from the sequence and the subsequence.
When the predicate encounters a negative value, it throws an exception.
The exception is caught in the try-catch block, and an error message is displayed.

Example 2: Iterator Throws an Exception

This example demonstrates a case where a custom iterator throws an exception during iteration.

Program

</>

Copy

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

class FaultyIterator {
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = int;
    using difference_type = std::ptrdiff_t;
    using pointer = const int*;
    using reference = const int&;

    FaultyIterator(const int* ptr, bool fail_after = false)
        : ptr(ptr), fail_after(fail_after), count(0) {}

    reference operator*() const {
        if (fail_after && count >= 2) {
            throw std::runtime_error("Iterator error during dereference.");
        }
        return *ptr;
    }

    FaultyIterator& operator++() {
        ++ptr;
        ++count;
        return *this;
    }

    bool operator!=(const FaultyIterator& other) const {
        return ptr != other.ptr;
    }

    bool operator==(const FaultyIterator& other) const {
        return ptr == other.ptr;
    }

private:
    const int* ptr;
    bool fail_after;
    int count;
};

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4};

    try {
        auto it = std::search(
            FaultyIterator(arr1, true),
            FaultyIterator(arr1 + 5),
            FaultyIterator(arr2),
            FaultyIterator(arr2 + 2)
        );

        if (it != FaultyIterator(arr1 + 5)) {
            std::cout << "Subsequence found.\n";
        } else {
            std::cout << "Subsequence not found.\n";
        }
    } catch (const std::runtime_error& e) {
        std::cout << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output

Exception caught: Iterator error during dereference.

Explanation

We define a custom iterator FaultyIterator that throws a std::runtime_error after accessing two elements.
We create two arrays, arr1 and arr2, for the sequence and subsequence.
The std::search function uses the custom iterator to compare elements from the sequence and the subsequence.
The custom iterator throws an exception during the third access, which is caught in the try-catch block, and an error message is displayed.

TutorialKart

C++ algorithm std::search Function Template