C在一组区间内有效搜索值

Question

假设我有一组由成对描述的间隔。我想找到所有包含给定值的区间集。

我制定了这个在O（n）时间内有效的解决方案，作为我追求的一个例子：

#include <iostream>
#include <vector>

using namespace std;

struct data
{
    int minValue;
    int maxValue;
};

void searchValue(const vector<data> &v, int target)
{
    for(size_t i = 0; i < v.size(); i++)
    {
        if(target >= v[i].minValue && target <= v[i].maxValue)
            cout << "Found target at set " << i << " (" << v[i].minValue << "," << v[i].maxValue << ")" << endl;
    }
}

int main()
{
    data d1 = {-1, 0};
    data d2 = {0, 3};
    data d3 = {-1, 5};
    data d4 = {10, 11};
    data d5 = {9, 12};

    // Vector to hold the interval sets
    vector<data> v{d1, d2, d3, d4, d5};

    // Search for the interval sets which contain the number 2
    searchValue(v, 2);

    return 0;
}

找到所有可能的集合非常重要，而不仅仅是一个。

我现在正在寻找一种计算效率更高的解决方案，可能在对数时间内。我认为可能有多集/多映射、lower_bound/upper_bound等解决方案，但迄今为止我还没有任何成功。

这可以通过使用区间树来实现，但我相信可能有一个解决方案，只使用STL。

Answer 1

我只担心查找，数据在获取后是不变的

我有两个可能的解决方案，如何初步准备数据，所以你可以有一个相当快的查找速度。

第一种是在准备好的std::map中使用给定位置作为键。

第二种方法的创建速度应该较慢，但通过计算索引，可以直接访问std：：vector中所需的数据。

我没有在速度方面进行任何测量，并且两个示例都没有在内存管理方面进行优化。

Ex1：

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

struct data
{
    int minValue;
    int maxValue;
};

class intervall_container
{
    using vec_t = std::vector<data>;
    using map_t = std::map<int, vec_t>;

    map_t m_map;

    void insert(const data& d)
    {
        for (int i = d.minValue; i <= d.maxValue; ++i) {
            m_map[i].push_back(d);
        }
    }

public:
    intervall_container(std::initializer_list<data> init)
    {
        std::for_each(init.begin(), init.end(), [this](const data& d) {insert(d); });
    }
    intervall_container(const intervall_container&) = delete;
    ~intervall_container() {}

    vec_t searchValue(int pos) const
    {
        auto result = m_map.find(pos);
        if (result == m_map.end()) return vec_t();
        return result->second;
    }
};

int main()
{
    data d1 = { -1, 0 };
    data d2 = { 0, 3 };
    data d3 = { -1, 5 };
    data d4 = { 10, 11 };
    data d5 = { 9, 12 };

    // Vector to hold the interval sets
    intervall_container v{ d1, d2, d3, d4, d5 };

    // Search for the interval sets which contain the number 2
    int value = 2;
    auto result = v.searchValue(value);
    for (auto iter = result.cbegin(); iter != result.cend(); ++iter)
    {
        std::cout << "Value '" << value << "' lies within the bounds of DataRange(" << iter->minValue << ", " << iter->maxValue << ").\n";
    }
    return 0;
}

例2：

#include <vector>
#include <algorithm>
#include <iostream>
#include <limits>

struct data
{
    int minValue;
    int maxValue;
};


struct intervall_container
{
    using vec_t = std::vector<data>;

    int m_offset;
    std::vector<vec_t> m_vecs;  

public:
    intervall_container(std::initializer_list<data> init)
    {
        int minmin = std::numeric_limits<int>::max(); //min minValue
        int maxmax = std::numeric_limits<int>::min(); //max maxValue
        for (auto iter = init.begin(); iter != init.end(); ++iter)
        {
            if (iter->minValue < minmin) minmin = iter->minValue;
            if (iter->maxValue > maxmax) maxmax = iter->maxValue;
        }
        m_offset = minmin;
        for (int value = minmin; value < maxmax; ++value)
        {
            vec_t vec;
            for (auto iter = init.begin(); iter != init.end(); ++iter)
            {
                if (iter->minValue <= value && value <= iter->maxValue)
                {
                    vec.push_back(*iter);
                }
            }
            m_vecs.push_back(vec);
        }
    }
    intervall_container(const intervall_container&) = delete;
    ~intervall_container() {}

    vec_t searchValue(int pos) const
    {
        pos -= m_offset;
        if(pos < 0 || pos >= m_vecs.size()) return vec_t();
        return m_vecs[pos];
    }
};


int main()
{
    data d1 = { -1, 0 };
    data d2 = { 0, 3 };
    data d3 = { -1, 5 };
    data d4 = { 10, 11 };
    data d5 = { 9, 12 };

    // Vector to hold the interval sets
    intervall_container v{ d1, d2, d3, d4, d5 };

    // Search for the interval sets which contain the number 2
    int value = 2;
    auto result = v.searchValue(value);
    for (auto iter = result.cbegin(); iter != result.cend(); ++iter)
    {
        std::cout << "Value '" << value << "' lies within the bounds of DataRange(" << iter->minValue << ", " << iter->maxValue << ").\n";
    }
    return 0;
}

Answer 2

我只想简单地回答“解决了！”但后来我想起了xkcd的古人智慧。

STL的set和multiset通常实现为红黑树。间隔树可以在红黑树之上实现。这让我想到STL的multiset可以用作解决方案的一部分。处理键多重性需要Multiset而不是set。

因此，第一步是使用multiset作为间隔的容器。在内部，multiset中的元素是经过排序的，因此我们需要比较间隔。如果intervalBig完全包含intervalSmall，我们可以说intervalBig大于另一intervalSmall。

至此，我们的解决方案是一个包含排序区间的多重集。现在我们需要一种搜索此容器的方法。这就是STL的find\u if发挥作用的地方。为了让它发挥作用，我们只需要我们的时间间隔能够相互比较。

要处理多个解决方案，只需迭代find\u if给出的前一个解决方案，因为multiset是有序的。

C 11中有一个解决方案：

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

using namespace std;

struct data
{
    int minValue;
    int maxValue;

    // for find_if comparisons
    bool operator()(const data& rhs){
        return rhs.minValue <= this->minValue && rhs.maxValue >= this->maxValue;
    }
};

// for set's internal sorting
struct compareData
{
    // Checks if lhs <= rhs. For an interval this can be defined as rhs being a bounding box that contains lhs.
    bool operator()(const data& lhs, const data& rhs){
        return rhs.minValue <= lhs.minValue && rhs.maxValue >= lhs.maxValue;
    }
};

int main()
{
    data d1 = {-1, 0};
    data d2 = {0, 3};
    data d2dup = {0, 3};
    data d3 = {-1, 5};
    data d4 = {10, 11};
    data d5 = {9, 12};

    std::multiset<data, compareData> intervals = { d1, d2, d3, d4, d5, d2dup };

    double target = 0;
    data tmp = { target, target };

    // find all sets which contain target
    for (auto it = find_if(intervals.begin(), intervals.end(), tmp); it != intervals.end(); it = find_if(++it, intervals.end(), tmp))
        cout << "Found target at set (" << it->minValue << "," << it->maxValue << ")" << endl;
}

这实际上是C中具有重叠搜索的区间树。由于multiset是有序的，搜索时间应该是O（logn）。

Answer 3

使用STL似乎很困难。

您可以使用间隔树：

http://en.wikipedia.org/wiki/Interval_tree

具体而言，它允许有效地找到与任何给定间隔或点重叠的所有间隔。