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

Question

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

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

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

Answer 1

您的 vector 已排序，因此您可以(并且应该)使用 std::lower_bound和 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 )但在连续存储中具有排序数据。它非常适合快速查找相对较小的数据集；不幸的是，您被删除后将后续元素改组的成本困住了。 map 通过间接存储数据来避免这种情况。双端队列对你来说可能是一个很好的中间立场。根据您的正常数据和访问模式，只有您可以知道。
您可能还会发现，因为元素类型只是 pair<int, double> ，您的编译器可能会交换 operator= 的全部负载需要一个漂亮简单的 memmove ，这在你现在谈论的规模上是非常快的。