如何高效从std::vector<Object*>中批量删除指定指针？

针对你遇到的性能问题，核心要解决两个点：减少元素移动的次数和降低查找待删除元素的时间复杂度，以下是两种更优的实现思路：

方案一：使用哈希集合加速查找（O(n + r) 时间复杂度） #

把待删除的指针存入std::unordered_set，这样判断某个指针是否需要删除的操作从O(r)降到O(1)，整体复杂度从O(n×r)优化到线性级别，同时配合erase/remove_if惯用法，只做一次元素移动和最多一次内存重分配。

示例代码：

#include <unordered_set>
#include <algorithm>

void RemoveObjects(const std::vector<Object*>& elementsToRemove, std::vector<Object*>& myObjectsVector) {
    // 构建哈希集合，O(r)时间
    std::unordered_set<Object*> toRemoveSet(elementsToRemove.begin(), elementsToRemove.end());
    
    // erase/remove_if惯用法，O(n)时间，只做一次元素移动
    myObjectsVector.erase(
        std::remove_if(myObjectsVector.begin(), myObjectsVector.end(),
            [&toRemoveSet](Object* obj) {
                return toRemoveSet.count(obj);
            }),
        myObjectsVector.end()
    );
}

如果你的指针值分布容易导致哈希冲突，也可以替换为std::set（红黑树实现），查找会变成O(log r)，整体复杂度O(n log r + r log r)，适合对哈希稳定性要求更高的场景。

方案二：排序待删除列表+二分查找（O(n log r + r log r) 时间复杂度） #

如果不想引入哈希集合的额外内存开销，可以先对elementsToRemove排序，然后用二分查找判断指针是否在待删除列表中，时间复杂度接近线性，内存占用更低。

示例代码：

#include <algorithm>

void RemoveObjects(std::vector<Object*>& elementsToRemove, std::vector<Object*>& myObjectsVector) {
    // 对待删除列表排序，O(r log r)时间
    std::sort(elementsToRemove.begin(), elementsToRemove.end());
    
    // erase/remove_if + 二分查找，O(n log r)时间
    myObjectsVector.erase(
        std::remove_if(myObjectsVector.begin(), myObjectsVector.end(),
            [&elementsToRemove](Object* obj) {
                return std::binary_search(elementsToRemove.begin(), elementsToRemove.end(), obj);
            }),
        myObjectsVector.end()
    );
}

为什么这两种方案比原方法好？ #

1. 避免多次重分配：erase/remove_if会先把需要保留的元素移动到vector前端，最后一次性删除尾部的冗余元素，整个过程最多触发一次内存重分配（如果vector容量足够的话甚至不会重分配），而逐个删除会每次删除都移动后面的元素，效率极低。
2. 降低查找复杂度：不管是哈希集合还是排序二分，都把原方案中O(r)的单次查找成本大幅降低，当r较大时性能提升非常明显。

另外提醒：如果这些指针是需要手动释放内存的，记得在删除之前先遍历elementsToRemove调用delete，避免内存泄漏。

内容的提问来源于stack exchange，提问作者K. Kapelinski