使用 std::remove_if 和 lambda 谓词来删除多个元素

Question

使用 std::remove_if 和 lambda 谓词同时删除多个元素的最快最有效的方法是什么？目前我有一个带有位置和唯一 ID 的点结构。在更新循环中，我们填充点向量，并在更新循环结束时添加要删除的点。目前我必须在循环中调用 remove_if 以从点向量中删除所有已删除的点。例如，如果我们每帧添加 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

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

然后，将 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 元素的存储方式，您失去了内存位置并放弃了缓存机会。

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

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

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

使用 std::remove_if 和 lambda 谓词来删除多个元素

Using std::remove_if with lambda predicate to delete multiple elements

c++

std