C++ algorithm std::search_n Function Template

C++ <algorithm> std::search_n

The std::search_n function template in C++ is used to find the first occurrence of a sequence of n identical elements within a range. It searches for n consecutive elements that match a specified value or satisfy a given predicate and returns an iterator to the beginning of the first such occurrence. This function is part of the <algorithm> header.

---

Syntax of std::search_n

template <class ForwardIterator, class Size, class T>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size count, const T& value);

template <class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size count, const T& value, BinaryPredicate pred);

---

Parameters of std::search_n

Parameter	Description
first, last	Forward iterators to the initial and final positions of the sequence to be searched. The range used is [first, last), which contains all the elements between first and last, including the element pointed to by first but not the element pointed to by last.
count	The number of consecutive elements to search for.
value	The value to be matched against the elements in the range.
pred (optional)	Binary function that accepts two elements as arguments (one from the sequence and one equal to value) 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_n

The function returns an iterator to the first element of the first occurrence of count consecutive elements in the range [first, last) that match value (or satisfy the predicate pred, if provided). If no such sequence is found, the function returns last.

---

Examples for search_n

Example 1: Searching for Consecutive Values in a Vector

In this example, we use std::search_n to find the first occurrence of three consecutive elements with the value 5 in a vector of integers.

Program

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

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

    auto it = std::search_n(data.begin(), data.end(), 3, 5);

    if (it != data.end()) {
        std::cout << "Sequence of three 5s found at position: "
                  << std::distance(data.begin(), it) << std::endl;
    } else {
        std::cout << "Sequence not found." << std::endl;
    }

    return 0;
}

Output

Sequence of three 5s found at position: 2

Explanation

1. We include the necessary headers: <iostream> for input/output operations, <vector> for the std::vector container, and <algorithm> for the std::search_n function.
2. We define a vector data containing integers, including a sequence of three consecutive 5s.
3. We call std::search_n, passing iterators to the beginning and end of the vector, the count of consecutive elements to search for (3), and the value to match (5). The function searches for the first occurrence of three consecutive 5s within the vector.
4. If the sequence is found, std::search_n returns an iterator to the first element of the sequence. We calculate the position by finding the distance from the beginning of the vector to the iterator and print the position.
5. If the sequence is not found, std::search_n returns data.end(), and we print a message indicating that the sequence was not found.

---

Example 2: Searching for Consecutive Elements Satisfying a Predicate

In this example, we use std::search_n with a custom predicate to find the first occurrence of two consecutive even numbers in a list of integers.

Program

#include <iostream>
#include <list>
#include <algorithm>

bool is_even(int a, int b) {
    return (a % 2 == 0) && (b % 2 == 0);
}

int main() {
    std::list<int> data = {1, 3, 4, 6, 7, 8, 10};

    auto it = std::search_n(data.begin(), data.end(), 2, 0, is_even);

    if (it != data.end()) {
        std::cout << "Sequence of two consecutive even numbers found at position: "
                  << std::distance(data.begin(), it) << std::endl;
    } else {
        std::cout << "Sequence not found." << std::endl;
    }

    return 0;
}

Output

Sequence of two consecutive even numbers found at position: 2

Explanation

1. We include the necessary headers: <iostream> for input/output operations, <list> for the std::list container, and <algorithm> for the std::search_n function.
2. We define a list data containing integers, including some even and odd values.
3. We define a custom predicate function is_even that checks if two integers are both even.
4. We call std::search_n, passing iterators to the beginning and end of the list, the count of consecutive elements to search for (2), the value 0 (which is not used for comparison due to the custom predicate), and the custom predicate is_even. The function searches for the first occurrence of two consecutive even numbers within the list.
5. If the sequence is found, std::search_n returns an iterator to the first element of the sequence. We calculate the position by finding the distance from the beginning of the list to the iterator and print the position.
6. If the sequence is not found, std::search_n returns data.end(), and we print a message indicating that the sequence was not found.

---

Examples for Exceptions Thrown by std::search_n

The std::search_n 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

#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> data = {1, -2, -2, -2, 5};

    try {
        auto it = std::search_n(data.begin(), data.end(), 3, -2, faulty_predicate);

        if (it != data.end()) {
            std::cout << "Sequence found at position: "
                      << std::distance(data.begin(), it) << std::endl;
        } else {
            std::cout << "Sequence 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

1. We define a custom predicate function faulty_predicate that throws a std::runtime_error if any of the compared values are negative.
2. We initialize a vector data containing integers, including negative values.
3. The std::search_n function applies the predicate to compare elements in the range. When it encounters a negative value, the predicate throws an exception.
4. 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

#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 arr[] = {1, 2, 2, 2, 3};

    try {
        auto it = std::search_n(
            FaultyIterator(arr, true),
            FaultyIterator(arr + 5),
            3,
            2
        );

        if (it != FaultyIterator(arr + 5)) {
            std::cout << "Sequence found.\n";
        } else {
            std::cout << "Sequence 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

1. We define a custom iterator FaultyIterator that throws a std::runtime_error after accessing two elements.
2. We initialize an array arr containing integers to be searched.
3. The std::search_n function uses the custom iterator to compare elements in the range.
4. The iterator throws an exception during the third access, which is caught in the try-catch block, and an error message is displayed.