这是在 C++ 中执行 set_difference 的正确方法吗？

Question

我正在将一些旧的 Julia 代码转换为 C++，作为 C++ 的新手，我发现自己倾向于使用它的许多新功能，即使它们不是必需的。目前，这条线产生了一些问题：

insertable = setdiff(route.vertices, 1:route.data.dimension)

我在 C++ 方面想到的是：

Route route_cpy = route;
std::sort(route_cpy.vertices.begin(), route_cpy.vertices.end(), [](int a, int b) { return a < b; });
std::vector<int> all_vertices(data.vertices.size()); std::iota(all_vertices.begin(), all_vertices.end(), 0);
std::vector<int> insertable;
std::set_difference(all_vertices.begin(), all_vertices.end(), route_cpy.vertices.begin(), route_cpy.vertices.end(),
    std::back_inserter(insertable));

请注意，在执行 set_difference 之前，我必须复制路线对象以对其顶点进行排序。这一切有必要吗？创建一个包含从 1 到 data.vertices.size() 的值的集合，然后删除 Route.vertices() 中存在的值会更好吗？

Answer 1

所以问题是哪种方法具有更好的时间复杂度。让我们针对每种情况进行分析（设

route.vertices

的大小为

n

，

all_vertices

的大小为

m

）：

1. 使用

   std::vector

   、

   std::sort

   和

   std::set_difference

   首先，您正在复制

   std::vector

   ，其复杂性是

   O(n)

   。然后你就可以对它进行复杂性排序

   O(n * log n)

   。然后使用

   std::set_difference

   ，它具有线性时间复杂度或

   O(n + m)

   （因为这个函数需要迭代两个数组）。所以，添加后我们将得到：

   O(n + n * log n + n + m)

   =

   O(n * (log n + 2) + m)

   =

   O(n * log(3n) + m)

   。另请注意，

   std::vector

   非常有效地使用缓存。

2. 使用

   std::set

   、

   std::set::erase

   。从

   std::set

   构造

   std::vector

   的时间复杂度为

   O(n * log n)

   。然后，您需要擦除元素（或者尝试擦除，如果它们不在这个集合中）

   m

   次，每次操作都会花费

   O(m * log n)

   。所以总时间复杂度为：

   O(n * log n + m * log n)

   =

   O((n + m) * log n)

   。此外，

   std::set

   分配内存的效率不如

   std::vector

   。

作为结论，在这种情况下使用

std::vector

更好。不用担心使用标准库中的算法，它们通常比手动实现更快。 但还有更有效的方法来实现这一点，使用

for

循环迭代

route_cpy

并添加到

insertable

的每两个元素之间的

route_cpy

值，时间复杂度为

O(n * log(2n) + m)

并且不使用额外的内存对于

all_vertices

数组（并且不复制整个

route

，而是仅复制

route.vertices

），这是主要改进：

auto copy_vertices = route.vertices;
std::sort(copy_vertices.begin(), copy_vertices.end());
std::vector<int> insertable;
for (int i = 0; i < copy_vertices[0]; i++)
{
    insertable.push_back(i);
}
for (int i = 1; i < copy_vertices.size(); i++)
{
    for (int j = copy_vertices[i-1] + 1; j < copy_vertices[i]; j++)
    {
        insertable.push_back(j);
    }
}
for (int i = copy_vertices.back() + 1; i < data.vertices.size(); i++)
{
    insertable.push_back(i);
}