C++ algorithm std::is_permutation Function Template

C++ <algorithm> std::is_permutation

The std::is_permutation function template in C++ is used to determine if one sequence is a permutation of another. In other words, it checks whether two sequences contain the same elements, possibly in a different order. This function is part of the <algorithm> header and is available since C++11.

---

Syntax of std::is_permutation

template <class ForwardIterator1, class ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2);

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, BinaryPredicate pred);

---

Parameters of std::is_permutation

Parameter	Description
first1, last1	Forward iterators defining the range [first1, last1) for the first sequence.
first2	Forward iterator to the beginning of the second sequence. The function considers as many elements of this sequence as those in the range [first1, last1). If this sequence is shorter, it causes undefined behavior.
pred (optional)	Binary predicate 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::is_permutation

The function returns a boolean value:

• true if all the elements in the range [first1, last1) compare equal to those of the range starting at first2 in any order.
• false otherwise.

---

Examples for is_permutation

Example 1: Checking if Two Arrays are Permutations of Each Other

In this example, we use std::is_permutation to check if two arrays of integers are permutations of each other.

Program

#include <iostream>
#include <algorithm>
#include <array>

int main() {
    std::array<int, 5> array1 = {1, 2, 3, 4, 5};
    std::array<int, 5> array2 = {3, 1, 4, 5, 2};

    if (std::is_permutation(array1.begin(), array1.end(), array2.begin())) {
        std::cout << "array1 and array2 contain the same elements.\n";
    } else {
        std::cout << "array1 and array2 do not contain the same elements.\n";
    }

    return 0;
}

Output

array1 and array2 contain the same elements.

Explanation

1. We include the necessary headers: <iostream> for input/output operations, <algorithm> for the std::is_permutation function, and <array> for the std::array container.
2. We define two arrays, array1 and array2, each containing five integers. The elements in array2 are a permutation of those in array1.
3. We call std::is_permutation, passing iterators to the beginning and end of array1, and the beginning of array2. The function compares the elements in both arrays to determine if they are permutations of each other.
4. The function returns true since all elements in array1 are present in array2, regardless of order.
5. We print a message indicating that the arrays contain the same elements.

---

Example 2: Using a Custom Predicate with std::is_permutation

In this example, we use std::is_permutation with a custom predicate to check if two sequences are permutations of each other, considering elements equal if their absolute values are the same.

Program

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

bool abs_equal(int a, int b) {
    return std::abs(a) == std::abs(b);
}

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

    if (std::is_permutation(vec1.begin(), vec1.end(), vec2.begin(), abs_equal)) {
        std::cout << "vec1 and vec2 are permutations of each other based on absolute values.\n";
    } else {
        std::cout << "vec1 and vec2 are not permutations of each other based on absolute values.\n";
    }

    return 0;
}

Output

vec1 and vec2 are permutations of each other based on absolute values.

Explanation

1. We include the necessary headers: <iostream> for input/output operations, <vector> for the std::vector container, <algorithm> for the std::is_permutation function, and <cmath> for the std::abs function.
2. We define a custom predicate function abs_equal that returns true if the absolute values of two integers are equal.
3. We initialize two vectors, vec1 and vec2, containing integers where corresponding elements have the same absolute values.
4. We call std::is_permutation, passing iterators to the beginning and end of vec1, the beginning of vec2, and the custom predicate abs_equal. The function compares the elements using the custom predicate instead of the default equality operator.
5. The function returns true because vec1 and vec2 contain the same elements when compared based on their absolute values.
6. We print a message indicating that the two vectors are permutations of each other based on absolute values.

---

Examples for Exceptions Thrown by std::is_permutation

The std::is_permutation 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 custom 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> vec1 = {1, -2, 3, 4};
    std::vector<int> vec2 = {4, 3, 2, 1};

    try {
        bool result = std::is_permutation(vec1.begin(), vec1.end(), vec2.begin(), faulty_predicate);
        if (result) {
            std::cout << "The sequences are permutations of each other.\n";
        } else {
            std::cout << "The sequences are not permutations of each other.\n";
        }
    } 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 faulty_predicate that throws a std::runtime_error if either of the input values is negative.
2. We initialize two vectors, vec1 and vec2. The first vector contains a negative value.
3. The std::is_permutation function applies the predicate to compare elements from both sequences. When the predicate encounters a negative value, it throws an exception.
4. The exception is caught in the try-catch block, and an error message is printed.

---

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 arr1[] = {1, 2, 3, 4};
    int arr2[] = {4, 3, 2, 1};

    try {
        bool result = std::is_permutation(
            FaultyIterator(arr1, true),
            FaultyIterator(arr1 + 4),
            FaultyIterator(arr2)
        );

        if (result) {
            std::cout << "The sequences are permutations of each other.\n";
        } else {
            std::cout << "The sequences are not permutations of each other.\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 create two arrays, arr1 and arr2, to compare as permutations.
3. The std::is_permutation function uses the custom iterator to compare the elements of both arrays.
4. The iterator throws an exception during the third access, which is caught in the try-catch block, and an error message is displayed.