时间戳

首页 > 解决方案 > 如何根据 .first 值从 std::pair 的 std::vector 中删除元素？

c++ - 如何根据 .first 值从 std::pair 的 std::vector 中删除元素？

问题描述

好的，所以我有一个排序的std::vector<std::pair<int,double>>. 我似乎无法找到的是如何根据 std::pair (int) 的“第一个”元素的值从向量中删除一个条目。我可能会在我的算法中多次这样做，所以我不想每次都遍历向量（可能包含多达一百万个条目）。我知道我们可以使用 std::erase 或 remove 轻松地根据索引删除元素，但是有没有办法根据对的第一个元素的值来做到这一点？或者我们可以得到那个元素的索引然后使用 std::erase 吗？

注意： std::pair 的第一个元素的值对于向量是唯一的。鉴于程序的限制，我需要使用向量（即不能使用地图或不同的容器）。

示例：我有一个这样的容器：

std::vector<std::pair<int,double>> vec = { {20, 60.3}, ... {10, -20.2}, {1020, -80.9}};

我想快速从向量中删除第一个元素 == 10 的元素，但我不知道它位于向量的哪个索引处。

标签： c++stdvectorstd-pair

解决方案

您的向量已排序，因此您可以（并且应该）使用std::lower_boundand std::upper_bound。

这些为您提供了与某些标准匹配的范围（前提是容器的排序顺序使其有意义），并通过良好的二进制搜索来实现。

提供一个只检查每对的第一项的自定义比较器。

#include <utility>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<std::pair<int,double>> data = { {20, 60.3}, {10, -20.2}, {1020, -80.9}};
    
    const int intToSearchFor = 10;
    
    const auto lower = std::lower_bound(
       data.begin(),
       data.end(),
       intToSearchFor,
       [](const std::pair<int, double>& el, const int i)
       {
          return el.first < i;
       }
    );
    
    const auto upper = std::upper_bound(
       data.begin(),
       data.end(),
       intToSearchFor,
       [](const int i, const std::pair<int, double>& el)
       {
          return i < el.first;
       }
    );
    
    data.erase(lower, upper);
}

如果您int的 s 是唯一的，则不需要上限检查，并且可以擦除位置处的元素lower……但是您必须首先确保它实际上等于i（可能大于），而且它不是data.end()。

该算法基本上实现std::map::erase（或std::multimap::erase）但在连续存储中使用排序数据。它非常适合快速查找相对较小的数据集；不幸的是，你被一个擦除后的后续元素洗牌的成本所困扰。地图通过间接存储数据来避免这种情况。双端队列对你来说可能是一个很好的中间立场。根据您的正常数据和访问模式，只有您可以知道。

您可能还会发现，因为元素类型只是 a pair<int, double>，您的编译器可能会将整个operator=调用负载换成一个不错的 simple memmove，这在您现在谈论的规模上已经足够快了。

推荐阅读