найти в контейнере объектов чистых виртуальных классов

Question

Для достижения контейнера непересекающихся интервалов я определил следующее:

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), но проблема в том, что класс interval является чисто виртуальным и поэтому я не могу создать любой экземпляр.

Как я могу преодолеть это?

Answer 1

Поскольку вы не перекрывающихся интервалов, вы можете использовать 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 найдет первый интервал, который не менее (т.е. больше или равно), чем значение , Так как мы сравниваем с самого начала, мы имеем два случая:

• Значение является началом интервала, и в этом случае сам интервал будет возвращен (первый if);
• Значение не является началом интервала, и в этом случае возвращается следующий интервал, поэтому нам необходимо уменьшить it (--it).

Поскольку мы только проверяем старт в std::lower_bound, нам нужно проверить конец перед возвратом.

std::lower_bound имеет логарифмическую сложность и выше вызов действует, потому что диапазон [first, last) является упорядоченным относительно компаратора мы предоставляем (лямбда) - Я предполагаю, что db сортируется в соответствии с началом интервалов.

См. http://rextester.com/FBHYH63411 для полной реализации.

Боковое примечание: Если вы не часто вставляете/удаляете интервалы, вам может быть полезно использовать отсортированный std::vector.

---

Edit: Старого ответ - Вы, вероятно, не можете использовать 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; 
});