c++ - 成对 vector : first pair values are non-sorted and second pair values are sorted: how to find a sorted value when having the non-sorted one

Question

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

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

Answer 1

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

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

如果您的 vector 未按第二个值排序，这将不起作用。您可能希望断言它首先排序，以避免发生意外。

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

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 的示例，它是一个线性搜索但不关心 vector 是否已排序。

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
}