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

将此Python行转换为C++?

code-translation c++ python

-1

vxs8122 · 技术社区 · 6 年前

diff = list(set(map(tuple, paths1)) - set(map(tuple, paths2)))

在哪里? paths1 和 paths2 是对的列表。

例子:

paths1 = [[(1,2),(2,3),(3,4)],[(1,3),(3,5)]]
paths2 = [[(5,2),(2,3),(3,4)],[(1,3),(3,5)]]
print(list(set(map(tuple, paths1)) - set(map(tuple, paths2))))

应输出 [((1, 2), (2, 3), (3, 4))] . 内部列表必须先转换为元组,因为无法将此类型的列表散列为set。

在下面提供的C++代码中,我尝试使用标准库中的SETION差异函数:

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

int main () {

    std::vector < std::pair < int, int >>v1 =
        { std::make_pair (1, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
    std::vector < std::pair < int, int >>v2 =
        { std::make_pair (5, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
    std::vector < std::pair < int, int >>v3 =
        { std::make_pair (1, 3), std::make_pair (3, 5) };

    std::vector < std::vector < std::pair < int, int >>>V1 = { v1, v3 };
    std::vector < std::vector < std::pair < int, int >>>V2 = { v2, v3 };
    std::vector < std::vector < std::pair < int, int >>>diff;

    std::set_difference (V1.begin (), V1.end (), V2.begin (), V2.end (),
                std::inserter (diff, diff.begin ()));

    std::cout << "[";
    for (auto v : diff) {
        std::cout << "[";
        for (auto p : v)
            std::cout << "(" << p.first << "," << p.second << ")";
        std::cout << "]";
    }
    std::cout << "]\n";

}

此代码已打印 [[(1,2)(2,3)(3,4)][(1,3)(3,5)]] . 为什么第二个内部列表在应该删除的时候没有删除?

1 回复 | 直到 6 年前

1

4

abarnert 6 年前

Python集基于散列。因此,Python集合的不同之处在于迭代左集合,在右集合的hashmap中查找每个元素,并跳过匹配的元素。

C++集是基于排序(实际上是二进制搜索树),而不是散列。同样的算法也可以工作,但它需要(对数线性而不是线性时间)。所以他们使用不同的算法做在线性时间内工作:假设两个范围都已排序,则可以并行地遍历这两个范围。

因此,C++ set_difference 仅适用于排序范围:

从排序范围复制元素 [first1, last1) 在排序范围内找不到的 [first2, last2) 从开始的范围 d_first .

当你给它非排序的范围时,它不知道你已经做了,并试图并行地走它们,然后变得困惑。在左边的列表通过 (5, 2) ,它已经超过了所有其他元素,因此不会跳过其他元素。