C++中vector.erase()的替代方案：元素仅用一次且提升效率

针对你需要避免重复使用vector元素且想规避vector.erase()的O(n)时间复杂度的需求，以下是几种可行的高效方案：

方案一：交换目标元素到末尾再pop_back（O(1)时间） #

如果元素的顺序对你来说不重要，这是最优解。把要删除的元素和vector最后一个元素交换，然后调用pop_back()，无需移动中间所有元素，时间复杂度直接降到O(1)。

修改后的代码片段：

if (sz && h[k] <= t[i]) {
    cout << h[k] << '\n';
    // 交换目标元素到末尾
    swap(h[k], h.back());
    // 删除末尾元素（O(1)操作）
    h.pop_back();
}
else {
    cout << "-1\n";
}

方案二：使用标记法记录已使用元素（O(1)标记/查询） #

如果必须保留原vector的顺序，或不能改变元素位置，可以用一个额外的布尔数组（或哈希集合）标记已使用的索引，无需真的删除元素。

示例代码：

// 提前初始化标记数组，大小与h一致，初始值全为false
vector<bool> used(h.size(), false);
// ...
if (sz && !used[k] && h[k] <= t[i]) {
    cout << h[k] << '\n';
    used[k] = true;
    sz--; // 维护有效元素的数量
}
else {
    cout << "-1\n";
}

注意：后续遍历或访问元素时，需要跳过标记为true的索引，sz需对应未被标记的有效元素数量。

方案三：改用适配随机删除的容器 #

如果你的场景存在大量随机位置删除操作，且对元素随机访问要求不高，可以考虑：

• 用std::list：删除操作是O(1)，但随机访问元素是O(n)，仅适用于不需要按索引快速取值的场景
• 用std::unordered_multiset：支持重复元素，删除操作O(1)，但无法按索引访问，仅适用于按元素值而非索引操作的场景

内容的提问来源于stack exchange，提问作者Eafhc Fhhxxf