std::ranges::mismatch() 算法

自 C++20 起

简化

// (1)
constexpr mismatch_result<I1, I2>
    mismatch( I1 first1, S1 last1, I2 first2, S2 last2,
              Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
constexpr mismatch_result<ranges::borrowed_iterator_t<R1>,
                          ranges::borrowed_iterator_t<R2>>
    mismatch( R1&& r1, R2&& r2, Pred pred = {},
              Proj1 proj1 = {}, Proj2 proj2 = {} );

参数类型是泛型的，并具有以下约束

• I1, I2 - std::input_iterator
• S1, S2 - std::sentinel_for<I>, std::sentinel_for<I1>, std::sentinel_for<I2>
• R1, R2 - std::ranges::input_range
• Pred - (无)
• Proj1, Proj2 - (无)

对于所有重载，Pred 模板参数的默认类型为 std::equal_to。
Proj1 和 Proj2 模板参数对于所有重载都具有默认类型 std::identity。

此外，每个重载都有以下约束

• (1) - indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
• (2) - indirectly_comparable< ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>

（为方便阅读，此处省略了 std:: 命名空间）

详细

// (1)
template<
  std::input_iterator I1,
  std::sentinel_for<I1> S1,
  std::input_iterator I2,
  std::sentinel_for<I2> S2,
  class Pred = ranges::equal_to,
  class Proj1 = std::identity,
  class Proj2 = std::identity
>
  requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr mismatch_result<I1, I2>
    mismatch( I1 first1, S1 last1, I2 first2, S2 last2,
              Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
template<
  ranges::input_range R1,
  ranges::input_range R2,
  class Pred = ranges::equal_to,
  class Proj1 = std::identity,
  class Proj2 = std::identity
>
  requires std::indirectly_comparable<
             ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
constexpr mismatch_result<ranges::borrowed_iterator_t<R1>,
                          ranges::borrowed_iterator_t<R2>>
    mismatch( R1&& r1, R2&& r2, Pred pred = {},
              Proj1 proj1 = {}, Proj2 proj2 = {} );

辅助类型定义如下：

template< class I1, class I2 >
using mismatch_result = ranges::in_in_result<I1, I2>;

返回来自两个范围的投影元素的第一个不匹配对：一个由 [first1; last1) 或 r1 定义，另一个由 [first2; last2) 或 r2 定义。

• (1) 元素使用给定的二元谓词 p 进行比较。

• (2) 与 (1) 相同，但使用 r 作为源范围，如同使用 ranges::begin(r) 作为 first 和 ranges::end(r) 作为 last。

本页描述的函数类实体是niebloids。

参数

first1 last1	表示要比较的第一个元素范围的迭代器-哨兵对。
r1	要比较的第一个元素范围。
first2 last2	表示要比较的第二个元素范围的迭代器-哨兵对。
r2	要比较的第二个元素范围。
pred	应用于投影元素的谓词。
proj1	应用于第一个元素范围的投影。
proj2	应用于第二个元素范围的投影。

返回值

ranges::mismatch_result 包含指向前两个不相等元素的迭代器。

如果在比较达到 last1 或 last2（以先发生者为准）时没有发现不匹配，则对象包含结束迭代器和来自另一个范围的相应迭代器。

复杂度

最多应用 std::min(last1 - first1, last2 - first2) 次谓词和相应的投影。

异常

(无)

可能的实现

mismatch(1) 和 mismatch(2)

struct mismatch_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr std::mismatch_result<I1, I2>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                   Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; first1 != last1 && first2 != last2; ++first1, (void)++first2)
            if (not std::invoke(pred, std::invoke(proj1, *first1),
                                      std::invoke(proj2, *first2)))
                break;

        return {first1, first2};
    }

    template<ranges::input_range R1, ranges::input_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
    constexpr ranges::mismatch_result<ranges::borrowed_iterator_t<R1>,
                                      ranges::borrowed_iterator_t<R2>>
        operator()(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::ref(pred), std::ref(proj1), std::ref(proj2));
    }
};

inline constexpr mismatch_fn mismatch;

示例

此程序确定在给定字符串的开头和结尾同时以相反顺序（可能重叠）找到的最长子字符串。

Main.cpp

#include <algorithm>
#include <iostream>
#include <ranges>
#include <string_view>

[[nodiscard]]
constexpr std::string_view mirror_ends(const std::string_view in)
{
    const auto end = std::ranges::mismatch(in, in | std::views::reverse).in1;
    return {in.cbegin(), end};
}

int main()
{
    std::cout << mirror_ends("abXYZba") << '\n'
              << mirror_ends("abca") << '\n'
              << mirror_ends("ABBA") << '\n'
              << mirror_ends("level") << '\n';

    using namespace std::literals::string_view_literals;

    static_assert("123"sv == mirror_ends("123!@#321"));
    static_assert("radar"sv == mirror_ends("radar"));
}

输出

ab
a
ABBA
level