c++ - 在纯虚拟类的对象容器中找到

为了实现不重叠间隔的容器，我定义了以下内容：

set<unique_ptr<interval>> db;

为确保已定义非重叠属性：

bool operator<(const unique_ptr<interval>& lhs,
               const unique_ptr<interval>& rhs);

interval类有2个字段：start，last，因此我可以确定某些int是否属于某些interval实例的范围。

现在我有一个int n，我想在集合中进行搜索以查找包含它的间隔。

我考虑过同时创建unique_ptr<interval> dummy_interval和搜索调用first=last=n的问题，但是问题是类db.find(dummy_interval)是纯虚拟的，因此我无法创建它的任何实例。

我该如何克服？

最佳答案

由于您具有非重叠间隔，因此可以将std::lower_bound与自定义比较器一起使用：

template <typename It>
It find_interval(It first, It last, int value) {
    // See explanation below.
    auto it = std::lower_bound(first, last, value,
                               [](const std::unique_ptr<interval>& i1, int value) {
                                   return i1->start < value;
                               });
    if (it != last && (*it)->start == value) {
        return it;
    }
    --it;
    // Change this to: (*it)->end > value ? it : last
    // ...if the upper bound of the interval are not included.
    return (*it)->end < value ? last : it;
}

std::lower_bound将查找不小于（即大于或等于）值的第一个间隔。由于我们正在与开始进行比较，因此有两种情况：


该值是间隔的开始，在这种情况下，间隔本身将被返回（first if）；
该值不是间隔的开始，在这种情况下，将返回下一个间隔，因此我们需要减小it（--it）。


由于我们仅检查std::lower_bound中的开始，因此我们需要在返回之前检查结束。

std::lower_bound具有对数复杂度，并且上述调用是有效的，因为范围[first, last)相对于我们提供的比较器（lambda）是有序的-我假设db根据间隔的开始进行排序。

有关完整的实现，请参见http://rextester.com/FBHYH63411。

旁注：如果您不经常插入/删除间隔，最好使用已排序的std::vector。



编辑：旧答案-
您可能无法使用std::set::find查找间隔，因为在db中使用的比较器会比较两个interval，而不是interval和int，并且std::set::find使用此比较器（即使带有“虚拟”间隔，则需要一个有效的关联，可能很难获得）。

您需要更改结构并使用例如Interval Tree来保持对数复杂度，或者使用具有线性复杂度的非“专用” std::find：

std::find(db.begin(), db.end(), [n](const std::unique_ptr<interval> &it) {
    return it->start < n && n < it->end;
});

关于c++ - 在纯虚拟类的对象容器中找到，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39703557/