Здравствуйте, pva, Вы писали:
pva>Здравствуйте, rg45, Вы писали:
R>>Ещё пара уточнений. Можно ли ввести какое-либо упорядочение элементов множества.
pva>Да, можно. Выше я немного приврал что тип делает элементы строго отличными друг от друга. Попробую объяснить ниже.
pva>Суть в том, что это a la дерево "symbolic calculation", в котором для узлов в процессе вычисления определяется множество вероятно принимаемых значений.
pva>Например, в какой-то момент решатель видит что результат op(a, b)->bool. Соответственно, допустимые значения {0,1}. not({0,1})={1,0}. Порядок следования важен.
pva>И так далее, двигаясь к корню мы в результате получаем некоторое множество (область) допустимых значений "функций" (МДЗ).
pva>При этом, технически есть еще ограничение размера типа (битовая маска — Mask).
pva>Грубо говоря, если у нас естьMOV al,0a5h
pva>SHL ax,3
pva>То по итогу у нас Mask=11 бит, МДЗ={0x528} (технически это rax=0x528 & Mask). Теперь если сделать AND ax,01a5h
pva>Результатом будет Mask=16 бит, MДЗ={0x120}. Неопределенность затронутой части не играет роли. Но если бы мы _вместо_ предыдущего сделали AND ax,0a5a5h
pva>Результатом будет Mask=11 бит, а вот MДЗ={}, поскольку затронуты были _значимые_ неопределенные биты.
pva>В общем, это напоминает проблемы с неинициализированной памятью в сях, обращение к которой дает неопределенный результат.
R>>И допускается ли дублирование элементов. Например, можно ли добавить в множество диапазон [1-10], а потом еще отдельно, например, 3.
pva>Дублирование элементов не критично. Их можно отсеивать со временем.
pva>Пока писал сам осознал несколько дополнительных подводных камней. Вероятно, есть смысл посмотреть специализированные решатели типа z3 и интегрировать их.
Я тут набросал эскиз — просто для демонстрации идеи. Можно реализовать шаблон класса множества ориентированного на работу с отдельным целочисленным типом а потом сложить все такие множества в общую мапу с ключом std::type_index. Мапу инкапсулировать, конечно же. Для единообразия и упрощения простые числа можно хранить как интервалы. И это будет не хуже, чем вариант с variant (пардон за каламбур).
Вот с итераторами будет только лёгкий геморрой. Потому что итерироваться придется по элементам с разными типами. Но юзабельные компромисные решения тоже можно будет искать. В т.ч. и визиторы.
#include <any>
#include <concepts>
#include <iostream>
#include <map>
#include <set>
#include <typeindex>
template <std::integral T>
struct Interval // Вместо этого можно заюзать boost::interval
{
T lower{};
T upper{};
};
template <std::integral T>
class Set
{
public:
using Interval = Interval<T>;
void insert(T t) {insert({t, t});} // Простые числа тоже хранятся как интервалы
void insert(const Interval&); // Вот тут нужно будет реализовать слияние интервалов
bool contains(T t) const {
const auto it = m_set.lower_bound(t);
return it != m_set.end() and it->lower <= t;
}
private:
struct Comparer { // Хитрый компаратор
using is_transparent = void;
bool operator()(const Interval& a, const Interval& b) const {return a.upper < b.upper;}
bool operator()(const Interval& a, T t) const { return a.upper < t; }
bool operator()(T t, const Interval& a) const { return t < a.upper; }
};
std::set<Interval, Comparer> m_set;
};
class SuperSet
{
public:
void insert(std::integral auto t) {get<decltype(t)>().insert(t);}
template<std::integral T> bool contains(T t) const {return get<T>() and get<T>()->contains(t);}
private:
template <std::integral T> Set<T>& get () {
std::any& any = m_pool[typeid(T)];
return any.has_value() ? std::any_cast<Set<T>&>(any) : any.emplace<Set<T>>();
}
template <std::integral T> const Set<T>* get() const;
std::map<std::type_index, std::any> m_pool;
};
int main() {
SuperSet s;
s.contains(42);
}
