CODEWITHSUNDEEP
c++algorithmstl
haslersn
haslersn

Reputation: 585

Inplace versions of set_difference, set_intersection and set_union

I implemented versions of set_union, set_intersection and set_difference that take a sorted container and a sorted range (that must not be within the container), and write the result of the operation into the container.

template<class Container, class Iter>
void assign_difference(Container& cont, Iter first, Iter last)
{
    auto new_end = std::set_difference( // (1)
        cont.begin(), cont.end(), first, last, cont.begin());
    cont.erase(new_end, cont.end());
}

template<class Container, class Iter>
void assign_intersection(Container& cont, Iter first, Iter last)
{
    auto new_end = std::set_intersection( // (2)
        cont.begin(), cont.end(), first, last, cont.begin());
    cont.erase(new_end, cont.end());
}

template<class Container, class Iter>
void assign_union(Container& cont, Iter first, Iter last)
{
    auto insert_count = last - first;
    cont.resize(cont.size() + insert_count); // T must be default-constructible
    auto rfirst1 = cont.rbegin() + insert_count, rlast1 = cont.rend();
    auto rfirst2 = std::make_reverse_iterator(last);
    auto rlast2 = std::make_reverse_iterator(first);
    rlast1 = std::set_union( // (3)
        rfirst1, rlast1, rfirst2, rlast2, cont.rbegin(), std::greater<>());
    cont.erase(std::copy(rlast1.base(), cont.end(), cont.begin()), cont.end());
}

The goal was:

As you can see in the lines marked (1), (2) and (3), the same container is used as input and output for those STL algorithms. Assuming a usual implementation of those STL algorithms, this code works, since it only writes to parts of the container that have already been processed.

As pointed out in the comments, it's not guaranteed by the standard that this works. set_union, set_intersection and set_difference require that the resulting range doesn't overlap with one of the input ranges. However, can there be a STL implementation that breaks the code?

If your answer is yes, please provide a conforming implementations of one of the three used STL algorithms that breaks the code.

Upvotes: 3

Views: 956

Answers (2)

Stefano Buora
Stefano Buora

Reputation: 1062

As rule of thumb I use do not write on a container on which you are iterating. Everything can happen. In general it's odd.

As @Yakk said, it sounds ill. That's it. Something to be removed from your code base an sleep peacefully.

If you really need those functions, I would suggest to write by yourself the inner loop (eg: the inner of std::set_intersection) in order to handle the constraint you need for your algorithm to work.

I don't think that seeking for an STL implementation on which it doesn't work is the right approach. It doesn't sound like a long term solution. For the long term: the standard should be your reference, and as someone already pointed out, your solution doesn't seems to properly deal with it.

My 2 cents

Upvotes: 0

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275760

A conforming implementation could check if argument 1 and 5 of set_intersection are equal, and if they are format your harddrive.

If you violate the requirements, the behaviour of your program is not constrained by the standard; your program is ill formed.

There are situations where UB may be worth the risk and cost (auditing all compiler changes and assembly output). I do not see the point here; write your own. Any fancy optimizations that the std library comes up with could cause problems when you violate requirements as you are doing, and as you have noted the naive implementation is simple.

Upvotes: 3

Related Questions