std :: includes实际做什么? [英] What does std::includes actually do?

问题描述

来自该标准 std::includes :

返回:true如果[first2, last2)为空，或者范围[first2, last2)中的每个元素都包含在范围[first1, last1)中. 否则返回false.

Returns: true if [first2, last2) is empty or if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.

^{注意:由于这是在 [alg.set.operations] 下的，因此必须对范围进行排序}

^{Note: as this is under [alg.set.operations], the ranges must be sorted}

从字面上看，如果我们让R1=[first1, last1)和R2=[first2, last2)，则表示正在评估:

Taking this literally, if we let R1=[first1, last1) and R2=[first2, last2), this is evaluating:

∀a∈R2 a∈R1

但是，这并不是实际要评估的内容.对于R1={1}和R2={1,1,1}，std::includes(R1, R2)返回false:

However, this is not what is actually being evaluated. For R1={1} and R2={1,1,1}, std::includes(R1, R2) returns false:

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

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'false'
    std::cout << std::boolalpha
        << std::includes(a.begin(), a.end(), b.begin(), b.end()) << '\n';
}

^{在Wandbox上直播}

这是令人惊讶的.我同时使用libstdc ++和libc ++进行了验证，但考虑到它是算法库的一部分，这对我来说似乎不太可能是标准库实现中的错误.如果这不是应该运行std::includes的算法，那是什么?

This is surprising. I verified it with both libstdc++ and libc++, but it seems unlikely to me that this would be a bug in the standard library implementation, considering it's part of the algorithms library. If this isn't the algorithm that std::includes is supposed to run, what is?

推荐答案

我在cpplang松弛中发布了此内容，并

I posted this in the cpplang slack, and Casey Carter responded:

标准中算法的描述有缺陷.目的是确定[如果]针头中的每个元素都按顺序出现在草垛中.

The description of the algorithm in the standard is defective. The intent is to determine [if] every element in the needle appears in order in the haystack.

[它实际执行的算法是:]如果已排序序列R1和R2的交集等于R2，则返回true"

[The algorithm it actually performs is:] "Returns true if the intersection of sorted sequences R1 and R2 is equal to R2"

或者，如果我们确保确定子序列的含义，

Or, if we ensure we are certain of the meaning of subsequence:

返回值:当且仅当[first2，last2)是[first1，last1)的子序列时才为真

Returns: true if and only if [first2, last2) is a subsequence of [first1, last1)

^{链接到凯西·卡特的邮件}

这篇关于std :: includes实际做什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！