CODEWITHSUNDEEP
c++pure-virtual
Hanna Khalil
Hanna Khalil

Reputation: 1055

find in container of objects of pure virtual classes

To achieve container of non-overlapping intervals I defined the following:

set<unique_ptr<interval>> db;

To ensure non-overlapping property have defined:

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

The interval class has 2 fields: start, last and so I can determine if some int falls in the range of certain interval instance.

Now I have an int n which I want to search in in the set to find which interval contains it.

I thought on creating unique_ptr<interval> dummy_interval with both first=last=n and searching call db.find(dummy_interval) but the problem is that class interval is pure virtual and so I can't create any instance of it.

How can I overcome that?

Upvotes: 0

Views: 99

Answers (1)

Holt
Holt

Reputation: 37696

Since you have non-overlapping intervals, you can use std::lower_bound with a custom comparator:

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 will find the first interval that is not less (i.e. greater or equal) than value. Since we are comparing with the start, we have two case:

  • The value is the start of the interval, in which case the interval itself will be returned (firstif);
  • The value is not the start of the interval, in which case the next interval will be returned, so we need to decrement it (--it).

Since we are only checking the start in std::lower_bound, we need to check the end before returning.

std::lower_bound has a logarithmic complexity, and the above call is valid because the range [first, last) is ordered with respect to the comparator we provide (the lambda) - I am assuming db is sorted according to the start of intervals.

See http://rextester.com/FBHYH63411 for a full implementation.

Side note: If you are not inserting/removing intervals often, you may be better off using a sorted std::vector.

Edit: Old answer - You probably cannot use std::set::find to find your interval because the comparator you are using in db compares two interval, not an interval and an int, and std::set::find uses this comparator (even with a "dummy" interval, you would need a valid relation, which may be hard to obtain).

Either you need to change the structure and use, e.g., an Interval Tree to keep logarithmic complexity, or you use the non-"specialized" std::find with linear complexity:

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

Upvotes: 1

Related Questions