c++ - 使用带有 lambda 谓词的 std::remove_if 删除多个元素

Question

使用带有 lambda 谓词的 std::remove_if 同时删除多个元素的最快和最有效的方法是什么？目前我有一个带有位置和唯一 ID 的点结构。在更新循环中，我们填充点 vector ，并在更新循环结束时添加要删除的点。目前，我必须在循环内调用 remove_if 以从点 vector 中删除所有已删除的点。例如，如果我们每帧添加 10 个点，然后循环所有点以检查该点是否在屏幕边界之外，如果它被添加到 deletedPoints_。

struct Point
{
    /// Position.
    Vector3 position_;
    /// Unique id per point
    int id_;
}

/// Current max id
int maxId_;

/// All points
std::vector<Point> points_;
/// Deleted points
std::vector<Point> deletedPoints_;


//Updates with 60fps
void App::Update()
{
    /// Add 10 points per frame
    for (int i = 0; i < 10; ++i)
    {
        Point newPoint;
        /// Add position
        newPoint.position_ = worldPosition;
        /// Add id starts from 1
        maxId_ += 1;
        startPoint.id_ = maxId_;
        /// Add new point in points
        points_.push(newPoint);
    }

    /// If points outside of screen bounds add them to deletedPoints_
    if (points_.size() > 0)
    {
        for (int i = 0; i < points_.size(); ++i)
        {
            /// Bounds
            Vector2 min = Vector2(0.00,0.00);
            Vector2 max = Vector2(1.00,1.00);
            /// Check Bounds 
            if(points_[i].x < min.x || points_[i].y < min.y || points_[i].x > max.x || points_[i].y > max.y)
            {   
                deletedPoints_.push(points_[i]);
            }

        }

        /// Loop deleted points
        for (int i = 0; i < deletedPoints_.size(); ++i)
        {
            int id = deletedPoints_[i].id_;
            /// Remove by id
            auto removeIt = std::remove_if(points_.begin(), points_.end(),
                                  [id](const TrailPoint2& point)
                                  { return point.id_ == id; });
            points_.erase(removeIt, points_.end());
        }
    }


 }

Answer 1

在不改变结构的情况下，最快的解决方法是反转整个循环并检查 deletedPoints而不是从 lambda 的内部。

然后，生成deletedPoints一个std::set<int>存储您的唯一 ID。那么它会比较快，因为std::set<int>::find不需要扫描整个容器，尽管您的最终复杂度仍然不是线性时间。

std::vector<Point> points_;
std::set<int> deletedPointIds_;

/// Remove by id
auto removeIt = std::remove_if(points_.begin(), points_.end(),
                      [&](const TrailPoint2& point)
                      { return deletedPointIds_.count(point.id_); });
points_.erase(removeIt, points_.end());
deletedPointIds_.clear();

也就是说，是否切换到 std::set 实际上会更快取决于一些事情；由于 set 的方式，您失去了内存位置并放弃了缓存机会的元素被存储。

另一种方法可能是保留 vector (ID 而不是点!)，对其进行预排序，然后使用 std::binary_search获得快速搜索的好处以及顺序存储数据的好处。但是，执行此搜索可能不适合您的应用程序，具体取决于您拥有多少数据以及您需要多久执行一次此算法。

您也可以使用 std::unordered_set<int>而不是 std::set ;这与 std::set 有相同的问题但是基于哈希的查找可能比基于树的查找更快。同样，这完全取决于数据的大小、形式和分布。

最终，唯一确定的方法是在模拟范围内尝试一些事情并测量。