将此 python 行转换为 C++？

Question

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))]。必须首先将内部列表转换为元组，因为这种类型的列表无法散列为集合。

在下面提供的 C++ 代码中，我尝试使用标准库中的 set_difference 函数：

#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)]]。为什么第二个内部列表在应该删除的时候没有删除？

Answer 1

Python 集合基于散列。因此，Python 集合差异通过迭代左侧集合、在右侧集合的哈希图中查找每个元素并跳过匹配的元素来工作。

C++ 集基于排序（实际上是二叉搜索树），而不是散列。相同的算法可以工作，但需要（对数线性时间而不是线性时间。所以他们使用不同的算法 does 在线性时间内工作：假设两个范围都已排序，你可以两个人平行走就行了。

因此，C++ set_difference 仅适用于排序范围：

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first.

当你给它未排序的范围时，它不知道你已经这样做了，并试图并行遍历它们，并感到困惑。在左侧列表通过 (5, 2) 之后，它已经超过了所有其他元素，因此不会跳过任何其他元素。

将此 python 行转换为 C++？

Converting this python line to C++?

c++

python

code-translation