c++ - 用于在整数值集中搜索区间的高效 C++ 数据结构

Question

我正在寻找一种数据结构(和 C++ 实现)，它允许(有效地)搜索在给定区间内具有整数值的所有元素。示例:假设集合包含:

3,4,5,7,11,13,17,20,21

现在我想现在 [5,19] 中这个集合中的所有元素。所以答案应该是5,7,11,13,17

对于我的使用来说，琐碎的搜索不是一种选择，因为元素的数量很大(几百万个元素)而且我必须经常进行搜索。有什么建议吗？

Answer 1

为此，您通常使用 std::set，这是一个有序集，其顶部构建有搜索树(至少这是一种可能的实现方式)。

要获取查询区间内的元素，请找到指向您要查找的第一个和最后一个元素的两个迭代器。这是算法 std::lower_bound 和 upper_bound 的用例，将两个区间限制视为包含:[x,y]。 (如果你想让结尾独占，请对结尾也使用 lower_bound。)

这些算法在集合大小上具有对数复杂度:O(log n)

请注意，如果您在应用这些操作之前对其进行排序，您也可以使用 std::vector。这在某些情况下可能是有利的，但如果您总是想对元素进行排序，请使用 std::set，因为它会自动为您完成。

Live demo

#include <set>
#include <algorithm>
#include <iostream>

int main()
{
    // Your set (Note that these numbers don't have to be given in order):
    std::set<int> s = { 3,4,5,7,11,13,17,20,21 };

    // Your query:
    int x = 5;
    int y = 19;

    // The iterators:
    auto lower = std::lower_bound(s.begin(), s.end(), x);
    auto upper = std::upper_bound(s.begin(), s.end(), y);

    // Iterating over them:
    for (auto it = lower; it != upper; ++it) {
        // Do something with *it, or just print *it:
        std::cout << *it << '\n';
    }
}

输出:

5
7
11
13
17