c++ - 数字对的有效搜索

Question

我有一个问题，我有一大串数字对。类似的东西:

(0,  1)
(10, 5)
(5, 6)
(8, 6)
(7, 5)
.....

如果该对存在于列表中，我需要使我可以进行非常快速的查找。我的第一个想法是制作 map< std::pair<int,int> >容器。并使用 container.find() 进行搜索.

第二个想法是制作vector<vector<int>我可以搜索的容器是使用 std::find(container[id1].begin(),container[id1].end(),id2) 存在的对;

第二种方法比第一种方法快一点，但如果可能的话，我需要更有效的方法。

那么问题是有没有更有效的方法来查找列表中是否存在数字对？

启动程序时我知道的对数，所以我不太关心对插入/删除，我只需要非常快速的搜索。

Answer 1

如果您不关心插入，您可以使用排序的 std::vector 和 std::binary_search，或 std::lower_bound。

int main()
{
    using namespace std;
    vector<pair<int, int>> pairs;
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(3, 1));
    pairs.push_back(make_pair(3, 2));
    pairs.push_back(make_pair(4, 1));

    auto compare = [](const pair<int, int>& lh, const pair<int, int>& rh)
        {
            return lh.first != rh.first ? 
                   lh.first < rh.first : lh.second < rh.second;
        };

    sort(begin(pairs), end(pairs), compare);
    auto lookup = make_pair(3, 1);
    bool has31 = binary_search(begin(pairs), end(pairs), lookup, compare);

    auto iter31 = lower_bound(begin(pairs), end(pairs), lookup, compare);

    if (iter31 != end(pairs) && *iter31 == lookup)
        cout << iter31->first << "; " << iter31->second << "at position "
            << distance(begin(pairs), iter31);
}