代码之家 › 专栏 › 技术社区 › Justin

STD:什么包括实际做?

stl-algorithm c++17 language-lawyer c++

31

Justin · 技术社区 · 7 年前

从 the standard, std::includes :

返回: true 如果 [first2, last2) 是空的,或者如果范围中的每个元素 [前2,后2) 包含在范围内 [first1, last1) . 退换商品 false 否则。

^{注意:因为这是在下面

[算法集操作]

,必须对范围进行排序}

从字面上看,如果我们让 R1=[first1, last1) 和 R2=[first2, last2) ,这是在评估:

âaâR2 aâR1

然而,这并不是实际正在评估的。对于 R1={1} 和 R2={1,1,1} , std::includes(R1, R2) 返回错误:

#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';
}

^{Live on Wandbox}

这是令人惊讶的。我用libstdc++和libc++验证了它,但考虑到它是算法库的一部分,在我看来这不太可能是标准库实现中的错误。如果这不是算法 STD:包括 应该跑,什么?

3 回复 | 直到 7 年前

1

30

Justin 7 年前

我把这个贴在CPPLANG Slack上, Casey Carter responded :

标准中对算法的描述有缺陷。其目的是确定针中的每一个元素是否按顺序出现在干草堆中。

[它实际执行的算法是:]“如果排序序列r1和r2的交集等于r2,则返回true”

或者,如果我们确信 subsequence :

返回:如果且仅当[First2,Last2]是[First1,Last1]的子序列时为真

^{link to Casey Carter's message}

2

3

TuÄberk Kaan Duman 7 年前

我相信你是想检查一下 a 包括 b 在你的例子中, 一 不包括 乙 但是 乙 包括 一 . 如果你交换 乙 和 一 它将回归真,因为 一 包括在 乙 .

我希望我没有遗漏明显的东西。

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

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

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

我通过玩算法了解到的是,当你输入 includes(R2, R1) 它检查是否 R2 拥有 R1 作为子组,如果返回Yes true 如果不返回 false 。另外,如果它没有被排序,就会引发一个错误: sequence not ordered .

3

-1

curiousguy 7 年前

像往常一样,在阅读标准时, 你必须读那些不成文的词 .

专注于目的而不仅仅是信。(该标准的措词经常被发现是含糊、不完整、自我参照或自相矛盾的。)

阅读“章节简介” 28.7.6 Set operations on sorted structures [alg.set.operations] “:

此子类定义了排序后的所有基本集合操作结构。他们也 使用多集 包含多个副本等效元素。 集合操作的语义是用标准方法推广到多集 通过将set_-union()定义为包含每个元素的最大出现次数, 将“交集”()设置为包含最小值, 等等。 .

所以很明显在描述 includes :

返回:如果[First2,Last2]为空或范围[First2,Last2]包含在范围[First1,Last1]中。否则返回false。

必须是忽略 . 你需要知道 先验的 多集操作是什么,两个多集的“包含”是什么意思,忽略描述,在你的头脑中重建什么是 明显的 意图。

多集包含:

A包含在B中 敌我识别 A接头B=B。

这对于集合或多集合是正确的。