如何根据 .first 值从 std::vector of std::pair 中删除一个元素?
How to delete an element from a std::vector of std::pair based on .first value?
好的,我已经排序了 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 的元素,但我不知道它位于向量的哪个索引处。
您的矢量已排序,因此您可以(并且应该)使用 std::lower_bound
和 std::upper_bound
。
这些给你一个 range 匹配一些标准(前提是容器的排序顺序使它有意义),并通过一个很好的二进制搜索来实现。
提供一个自定义比较器,它只检查每对中的第一项。
#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
是唯一的,你不需要上限检查,可以只删除位置 lower
的元素......但你必须首先确保它是实际上等于i
(可能是greater-than),而且它不是data.end()
.
该算法基本上实现了 std::map::erase
(或 std::multimap::erase
),但在连续存储中使用排序数据。它非常适合快速查找相对较小的数据集;不幸的是,您在擦除后 遇到了将后续元素打乱的成本。地图通过间接存储数据来避免这种情况。双端队列对你来说可能是一个很好的中间地带。根据您的正常数据和访问模式,只有您知道。
您可能还会发现,因为元素类型只是一个 pair<int, double>
,您的编译器可能会将整个负载的 operator=
调用换成一个简单的 memmove
,即在你现在谈论的规模上已经足够快了。
好的,我已经排序了 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 的元素,但我不知道它位于向量的哪个索引处。
您的矢量已排序,因此您可以(并且应该)使用 std::lower_bound
和 std::upper_bound
。
这些给你一个 range 匹配一些标准(前提是容器的排序顺序使它有意义),并通过一个很好的二进制搜索来实现。
提供一个自定义比较器,它只检查每对中的第一项。
#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
是唯一的,你不需要上限检查,可以只删除位置 lower
的元素......但你必须首先确保它是实际上等于i
(可能是greater-than),而且它不是data.end()
.
该算法基本上实现了 std::map::erase
(或 std::multimap::erase
),但在连续存储中使用排序数据。它非常适合快速查找相对较小的数据集;不幸的是,您在擦除后 遇到了将后续元素打乱的成本。地图通过间接存储数据来避免这种情况。双端队列对你来说可能是一个很好的中间地带。根据您的正常数据和访问模式,只有您知道。
您可能还会发现,因为元素类型只是一个 pair<int, double>
,您的编译器可能会将整个负载的 operator=
调用换成一个简单的 memmove
,即在你现在谈论的规模上已经足够快了。