Generic erase function

Question

I need to erase elements of different stl and boost containers by an iterator. Sometimes I also need to do that with a reverse_iterator so I wanted to wrap that into a generic function (set).

According to this: Iterator invalidation rules it should mostly be possible.

What I got so far is this:

    template<class T, bool T_IterReturned = helpers::EraseReturnsIterator<T>::value>
    struct EraseImpl
    {
        typedef typename T::iterator iterator;
        typedef typename T::const_iterator const_iterator;
        static iterator erase(list& container, iterator it) {
            return container.erase(it);
        }
        static const_iterator erase(list& container, const_iterator it) {
            return container.erase(it);
        }
    };
    template<class T>
    struct EraseImpl<T, false>
    {
        // This one gets used for e.g. std::set whos erase does not return
        // an iterator until C++11
        typedef typename T::iterator iterator;
        typedef typename T::const_iterator const_iterator;
        static iterator erase(list& container, iterator it) {
            container.erase(it++);
            return it;
        }
        static const_iterator erase(list& container, const_iterator it) {
            container.erase(it++);
            return it;
        }
    };

template<typename T>
inline typename T::iterator erase(T& container, typename T::iterator it)
{
    return detail::EraseImpl<T>::erase(container, it);
}

template<typename T>
inline typename T::reverse_iterator erase(T& container, typename T::reverse_iterator it)
{
    typename T::reverse_iterator tmp = it;
    return typename T::reverse_iterator(erase(container, (++tmp).base()));
}

This should work for most cases, but e.g. a vector-like container that does not return the iterator would break this. Sets do not invalidate any other iterators -> ok to use the next-iterator. For vectors I'd need to store the previous iterator (if any) and return that. For a deque (and similar) w/o iterator return this won't work at all. I don't want to implement an EraseImpl for all known containers as e.g. this would require me to include all their headers which I want to avoid.

Is there anything I can to to avoid specializing it for all types? Of course I can create a trait with an enum like {Use_Next, Use_Prev} and leave it unspecialised for containers invalidating all iterators. But again: I don't want to include all possible headers.

You don't need to include all headers, forward declaration is enough for the traits. — Jarod42, Aug 05 '15 at 03:03
@Jarod42: You cannot forward-declare the Standard Library types. That's why there is a special ``. However, that's the only such header. — MSalters, Aug 05 '15 at 10:35
I suspect there's no general solution. How would you deal with a container that invalidates _all_ iterators on `erase`? Not that farfetched; a vector-like container which shrinks may do so. (Reallocation to smaller block) — MSalters, Aug 05 '15 at 10:39
@MSalters: for the hypothetical vector-like, you may still save index and recreate iterator as `container.begin() + index`... but I agree that it would be a lot of work to handle each strange case. (I wonder which is the less requirement that an iterator container may have). — Jarod42, Aug 05 '15 at 10:46
Then maybe have extra include files for non-iterator returning containers that include the container include and define a trait. And then include those instead of the original ones? Looks ugly anyway... — Flamefire, Aug 05 '15 at 10:58

score 0 · Accepted Answer · edited May 23 '17 at 11:58

Solution I'm currently using is by using a trait class that can be specialized for each container class.

Default is "Not-Allowed", but also providing specializations for containers that have an erase function, that returns an iterator. This is done in a generic way, so only the existence of such a function is checked. If it is found, generic_erase uses it. If not the trait asks the user specialized one what erase does to iterators (next_iterator_valid, prev_iterator_valid, all_invalid) and generic_erase acts accordingly.

This was helpful for that task: Check for function signature also for inherited functions

Generic erase function

1 Answers1