成对向量：第一对值未排序，第二对值已排序：如何在具有未排序值时找到已排序值

Question

我有一个向量对，如下所示。第一对值未排序，第二对值已排序（从零开始）。我可能想通过实现 std::vector 和 std::pair 来存储数据。当我有第一对值（未排序）时，找到相应的第二对值（已排序）的最佳方法是什么？实现它的最佳方法是什么？

另一种方式很直观：当我有第二个对值（已排序，从零开始）时，我可以轻松找到对应的第一个对值（未排序）。

Answer 1

由于第二个值已排序，您可以执行二进制搜索。（如果它没有排序，你可以只使用 std::find_if 这是线性的）

要执行二进制搜索，您需要使用 std::lower_bound，这很棘手。您需要提供一个函子来告诉它您的向量是如何排序的，在本例中是按第二个值排序。如果它找到该值，它 returns 一个迭代器到它。如果找不到该值，它会 returns 指向另一个值的迭代器或结束迭代器。 if 语句检查结束迭代器 first，因为取消引用结束迭代器是无效的。

如果您的矢量未按第二个值排序，则此操作将无效。你可能想断言它是第一个排序的，以避免发生意外。

提供给std::lower_bound的仿函数只需要第二个参数的键类型（搜索时，第一对值不构成键）。但是要断言它已排序，两个参数都必须是存储在向量中的类型。

std::vector<std::pair<T1, T2>> data;
T2 find_val;

// check the vector is sorted properly
assert(std::is_sorted(data.begin(), data.end(), [](const std::pair<T1, T2>& left, const std::pair<T1, T2>& right){ return left.second < right.second; }));

// attempt to find our value
auto find_it = std::lower_bound(data.begin(), data.end(), find_val, [](const std::pair<T1, T2>& left, const T2& right){ return left.second < right; });

// check it's not the end iterator and it actually points to our value
if (find_it != data.end() && find_it->second == find_val)
{
    // found it!
    auto& retrieve_val = find_it->first;
}
else
{
    // not found
}

这是一个使用 std::find_if 的示例，它是线性搜索，但不关心向量是否已排序。

auto find_it = std::find_if(data.begin(), data.end(), [&find_val](const std::pair<T1, T2>& val){ return val.second == find_val; });

if (find_it != data.end())
{
    // found it!
    auto& retrieve_val = find_it->first;
}
else
{
    // not found
}

成对向量：第一对值未排序，第二对值已排序：如何在具有未排序值时找到已排序值

A vector of pairs: first pair values are non-sorted and second pair values are sorted: how to find a sorted value when having the non-sorted one

c++

sorting

find

stdvector

std-pair