Specializing STL algorithms so they automatically call efficient container member functions when available

Question

The STL has global algorithms that can operate on arbitrary containers as long as they support the basic requirements of that algorithm. For example, some algorithms may require a container to have random access iterators like a vector rather than a list.

When a container has a faster way of doing something than the generic algorithm would, it provides a member function with the same name to achieve the same goal - like a list providing its own remove_if() since it can remove elements by just doing pointer operations in constant time.

My question is - is it possible/advisable to specialize the generic algorithms so they automatically call the member function version for containers where it's more efficient? E.g. have std::remove_if call list::remove_if internally for lists. Is this already done in the STL?

Answer 1

Not in the case of remove_if, since the semantics are different. std::remove_if doesn't actually erase anything from the container, whereas list::remove_if does, so you definitely don't want the former calling the latter.

Neither you nor the implementation can literally specialize the generic algorithms for containers because the algorithms are function templates that take iterators, and the containers are themselves class templates, whose iterator type depends on the template parameter. So in order to specialize std::remove_if generically for list<T>::iterator you would need a partial specialization of remove_if, and there ain't no such thing as a partial specialization of a function template.

I can't remember whether implementations are allowed to overload algorithms for particular iterator types, but even if not the "official" algorithm can call a function that could be overloaded, or it can use a class that could be partially specialized. Unfortunately none of these techniques help you if you've written your own container, and have spotted a way to make a standard algorithm especially efficient for it.

Suppose for example you have a container with a random-access iterator, but where you have an especially efficient sort technique that works with the standard ordering: a bucket sort, perhaps. Then you might think of putting a free function template <typename T> void sort(MyContainer<T>::iterator first, MyContainer<T>::iterator last) in the same namespace as the class, and allow people to call it with using std::sort; sort(it1, it2); instead std::sort(it1, it2);. The problem is that if they do that in generic code, they risk that someone else writing some other container type will have a function named sort that doesn't even sort the range (the English word "sort" has more than one meaning, after all). So basically you cannot generically sort an iterator range in a way that picks up on efficiencies for user-defined containers.

When the difference in the code depends only on the category of the iterator (for example std::distance which is fast for random access iterators and slow otherwise), this is done using something called "iterator tag dispatch", and that's the most common case where there's a clear efficiency difference between different containers.

If there are any remaining cases that apply to standard containers (discounting ones where the result is different or where the efficiency only requires a particular iterator category), let's have them.

Answer 2

What you are looking for isn't specialization, but overloading. You could provide alternative versions of the algorithms (not, legally, in namespace std, though) that take containers as arguments, rather than iterator pairs, and either call the STL pendants calling begin() and end() on the container, or do something else. Such an approach of course does require the code to call your functions instead of the STL functions, though.

This has certainly been done before, so you might actually find a set of headers out there saving you the work to write all this boilerplate code.

Answer 3

The only way to do this would be to create your own wrapper templates for each of the algorithms, taking a container rather than a pair of iterators. Then you could specialize your wrapper for each container type that could be optimized. Unfortunately this removes a lot of the flexibility of the standard algorithms, and litters your programs with a bunch of non-standard calls.

Answer 4

It is not possible - the algorithms work with iterators, and iterators have no knowledge of the container object they refer to. Even if they did, there would be no way to determine at compile time whether a given iterator range refers to the whole of a container, so it could not be done by specialisation alone; there would need to be an extra runtime check.