如何基于 .first 值从 std::pair 的 std::vector 中删除元素？

Question

好的，所以我有一个排序的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 的元素，但我不知道它位于向量的哪个索引处。

Answer 1

您的向量已排序，因此您可以（并且应该）使用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);
}

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

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

您可能还会发现，因为元素类型只是 a pair<int, double>，您的编译器可能会将大量operator=调用交换为一个很好的 simple memmove，这在您现在谈论的规模上非常快。