std::span_set

[dywoq]

В текущем стандарте C++ множество (std::set) позволяет хранить уникальные элементы в отсортированном порядке, но оно не предоставляет возможностей для работы с частичными диапазонами значений. Для специфичных задач, таких как работа с последовательностями чисел или диапазонами, можно создать новый тип данных span_set. Этот класс будет представлять множество, в котором можно эффективно работать с диапазонами элементов, а также комбинировать их с операциями над обычными множествами.

Основные особенности класса span_set:

1. Частичные диапазоны: Возможность эффективно задавать диапазоны элементов (например, от 1 до 100) без явного перечисления всех элементов.

2. Поддержка стандартных операций над множествами: Объединение, пересечение, разность и т.д.

3. Управление диапазонами: Можно добавлять, удалять и проверять элементы как в пределах диапазонов, так и вне их.

4. Оптимизация: Вместо хранения каждого элемента будет храниться только информация о диапазонах, что позволяет сэкономить память и улучшить производительность для широких диапазонов значений.

Пример использования

#include <span_set>
#include <print>

int main() {
    std::span_set<int> s;
    
    // Добавление отдельных элементов
    s.add(1);
    s.add(5);
    s.add(10);
    
    // Добавление диапазона
    s.add_range(20, 30);  // Добавит все числа от 20 до 30 (включительно)
    
    // Проверка наличия элемента
    std::println("Содержит 25? {}", s.contains(25) ? "да" : "нет"); // да
    
    // Проверка пересечения диапазонов
    std::span_set<int> other_set;
    other_set.add_range(15, 25);  // Добавит все числа от 15 до 25
    
    std::span_set<int> intersection = s.intersection(other_set);
    std::println("Пересечение: {}", intersection);  // 20, 21, ..., 25

    return 0;
}

Пояснение

add_range(start, end) позволяет добавлять диапазоны значений вместо индивидуальных элементов, что делает работу с диапазонами более удобной и производительной.

intersection() возвращает пересечение двух наборов (включая возможные пересекающиеся диапазоны).

[isnullxbh]

А какое ожидается поведение в случае, когда добавляемый диапазон R содержит элемент(ы), уже добавленный(е) в сет?

std::span_set<int> s;
s.add(15);
s.add_range(10, 20);

15 как "одиночное" значение все еще будет присутствовать в s?

[isnullxbh]

И еще вопрос: правильно ли я понимаю, что если бы не пункт про оптимизацию, нам было бы вполне достаточно связки std::set + ranges для решения вышеупомянутых задач?

[dywoq]

А какое ожидается поведение в случае, когда добавляемый диапазон R содержит элемент(ы), уже добавленный(е) в сет?

std::span_set<int> s;
s.add(15);
s.add_range(10, 20);

15 как "одиночное" значение все еще будет присутствовать в s?

В этом случае можно выбросить исключение

[dywoq]

И еще вопрос: правильно ли я понимаю, что если бы не пункт про оптимизацию, нам было бы вполне достаточно связки std::set + ranges для решения вышеупомянутых задач?

Да, можно ещё использовать std::views::iota. Тогда если уже есть альтернативы, тогда можем закрыть тему.