C++ Basics: Find a Contiguous Pattern Inside a Sequence

Use std::search to locate the first complete adjacent pattern in integer data.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as search-contiguous-pattern-demo.cpp:

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

int main()
{
    const std::vector<int> stream{1, 2, 1, 2, 3, 4};
    const std::vector<int> marker{1, 2, 3};
    const auto found = std::search(stream.begin(), stream.end(), marker.begin(), marker.end());
    if (found == stream.end()) std::cout << "Not found\n";
    else std::cout << "Marker starts at " << std::distance(stream.begin(), found) << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic search-contiguous-pattern-demo.cpp -o search-contiguous-pattern-demo &&
./search-contiguous-pattern-demo

Observed output:

Marker starts at 2

Read the result

The first 1, 2 pair is followed by another 1 and therefore is not a match. The complete marker starts at index 2. std::search finds a contiguous subsequence, rather than scattered values that merely occur in order.

Apply it carefully

An empty pattern matches at begin(), even for an empty input. Decide whether an empty marker is valid for your application before interpreting the result as a discovered event. This example uses a nonempty marker, so end() unambiguously means absent. The ordinary overload can compare many candidate positions; specialized searchers may be appropriate for repeated large searches.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- search-contiguous-pattern-demo.cpp search-contiguous-pattern-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.