C++中set_difference的用法是否恰当？有无更优实现方案？

问题背景 #

我是C新手，正在将旧Julia代码转换为C代码。原Julia代码为：
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));

疑问：复制route对象并排序其vertices才能执行set_difference是否必要？改用创建包含1至data.vertices.size()元素的集合，再移除route.vertices中的元素是否更合适？

复制排序的必要性 #

• 排序是必须的：std::set_difference的前置条件是两个输入范围必须按升序（默认）有序，否则结果完全不可预测。如果不能保证原route.vertices本身是有序的，复制后排序是唯一符合标准库要求的做法。
• 复制是否必要？：如果原route.vertices允许被修改，你可以直接在原容器上排序，之后再恢复（比如排序前复制一份备份），但这种做法会增加代码复杂度，对于新手来说，直接复制一份来排序更直观、不容易出错，优先保证代码清晰性更重要。

两种方案的对比 #

方案1：现有实现（复制排序+set_difference）

• 优势：
  • 基于标准库算法，代码简洁易读，符合C++惯用写法
  • 时间复杂度：排序为O(n log n)，set_difference为O(n+m)，整体效率优异
  • 内存开销可控，仅用vector即可完成，无需额外复杂数据结构
• 劣势：当route.vertices数据量极大时，复制操作会带来一定内存消耗

方案2：集合实现（创建全量集合后移除元素）

示例代码：

// 注意：Julia的1:dimension是1起始，你的原C++代码用了0起始，需对齐逻辑
std::unordered_set<int> all_set;
for (int i = 1; i <= data.vertices.size(); ++i) {
    all_set.insert(i);
}
for (int v : route.vertices) {
    all_set.erase(v);
}
// 若需要有序结果，需额外排序
std::vector<int> insertable(all_set.begin(), all_set.end());
std::sort(insertable.begin(), insertable.end());

• 优势：
  • 无需对route.vertices排序，适合原容器完全无序且不想改动它的场景
  • 逻辑和Julia的setdiff语义更贴近，直接模拟集合差集
• 劣势：
  • 如果需要有序结果，最后还要额外排序，反而多了一步开销
  • 集合的插入/删除有固定开销，数据量较大时，效率未必优于方案1
  • std::set或std::unordered_set的内存密度远低于vector，内存开销更高

选择建议 #

• 如果insertable需要有序结果，且route.vertices数据量不是极端庞大，优先用你的现有方案——标准库算法经过高度优化，代码也更简洁。
• 如果不需要有序结果，或者route.vertices存在大量重复元素（集合会自动去重，而set_difference要求原范围无重复才能和Julia语义一致），可以考虑集合方案。
• 重要提醒：注意索引一致性！Julia是1-based索引，你的C++代码用std::iota从0开始生成all_vertices，这和原Julia代码的1:route.data.dimension逻辑不符，需要根据实际需求调整起始值。

内容的提问来源于stack exchange，提问作者Lucas Ximenes Guilhon