in-place set_intersection, set_difference

[loskutov]

Согласно стандарту, вызов std::set_intersection с output range, пересекающимся с input range, приводит к неопределённому поведению, что делает невалидным код вроде:

// std::vector<int> lhs, rhs;
lhs.erase(std::set_intersection(lhs.begin(), lhs.end(),
                                rhs.begin(), rhs.end(),
                                lhs.begin()),
          lhs.end()
);

При этом желание пересечь два множества, не выделяя дополнительной памяти, является довольно естественным и не накладывает дополнительных ограничений на имплементацию: см. libstdc++, libc++ — даже в случае, если output range совпадает с каким-либо из input range, рассматриваемые алгоритмом интервалы (суффиксы исходных) всё равно не пересекаются с заполненной частью output range, и запись туда никак не влияет на последующие чтения.

Аналогичные соображения применимы и к std::set_difference (для первого input range) и соответствующим функциям из пространства имён std::ranges.

Конечно, в случае, когда output range начинается строго внутри одного из input ranges, получается что-то странное, и в таком случае ничего не гарантировать выглядит разумным решением. Предлагается переписать preconditions, чтобы UB получалось только в таком случае, а если пересечение имеется, но такое, что input range начинается внутри (возможно, в начале) output range — такие входные данные должны быть допустимыми.

[sergii-rybin-tfs]

Немного с другой области, но уж очень хочется перегрузки этих алгоритмов для unordered_set\map контейнеров с константной сложностью (Как в пайтоне).

[apolukhin]

Звучит очееь интересно! А можете реализовать эти алгоритмы и сделать PR в Boost.Algorithm https://github.com/boostorg/algorithm ?

[loskutov]

Речь ведь о фиксации гарантий, которым уже удовлетворяют распространённые имплементации стандартной библиотеки — вероятно, можно даже в качестве defect report оформить.