Есть ли коллекция для хранения дискретных интервалов?

Question

Мне нужно хранить дискретные диапазоны в наборе, соединяя смежные диапазоны при вставке.Есть ли в STL структура, которая уже имеет такую ​​функциональность?

Я пробовал boost :: interval, но это довольно тяжело и немного излишне для того, что я пытаюсь сделать.

Например, предположим, что набор пуст и вставлены следующие элементы:

[64, 96]
[0, 4]
[11, 15]
[5, 10]

Ожидаемое содержимое набора интервалов должно быть следующим:

[0, 15]
[64, 96]

Answer 1

Это хорошо известный вопрос. Существует страница википедии о возможных решениях вашего вопроса. Конечно, в C ++ STL вы можете реализовать решение, основанное на наивном подходе, объясненном в википедии, с использованием std::map, поскольку карта представляет собой красно-черное дерево, которое является типом дерева двоичного поиска.

Answer 2

Тот факт, что вы хотите объединить интервалы в случае, если они соседствуют друг с другом, значительно упрощает вашу задачу, чем предлагаемый подход дерево интервалов .

Вместо этого вы можете использовать структуры данных, предложенные Some programmer dude, и очень быстро развернуть собственную реализацию. Здесь я приведу возможную реализацию:

class IntervalSet {
    std::map<int, int> _intervals;

public:
    void Add(int smaller, int bigger) {
        const auto next = _intervals.upper_bound(smaller);
        if (next != _intervals.cbegin()) {
            const auto prev = std::prev(next);
            if (next != _intervals.cend() && next->first <= bigger + 1) {
                bigger = next->second;
                _intervals.erase(next);
            }
            if (prev->second + 1 >= smaller) {
                smaller = prev->first;
                _intervals.erase(prev);
            }
        }
        _intervals[smaller] = bigger;
    }

    const auto& Intervals() const { return _intervals; }

    bool IsInsideInterval(int v) const {
        const auto suspectNext = _intervals.upper_bound(v);
        const auto suspect = std::prev(suspectNext);
        return suspect->first <= v && v <= suspect->second;
    }
};

Маленькие тесты:

IntervalSet is;
is.Add(64, 96);
is.Add(0, 4);
is.Add(11, 15);
is.Add(5, 10);
for (const auto p : is.Intervals()) std::cout << "(" << p.first << ", " << p.second << ") ";

(0, 15) (64, 96)

Работает также с пересекающимися интервалами:

IntervalSet is;
is.Add(0, 10);
is.Add(5, 15);
is.Add(10, 20);
for (const auto p : is.Intervals()) std::cout << "(" << p.first << ", " << p.second << ") ";

(0,20)