Overloading for_each for specific iterator types

Question

I'm using a typedef to define the type of a container in my program so that I can easily switch between using normal STL containers and STXXL containers, along the lines of:

typedef stxxl:vector<Data> MyContainer;

or

typedef std:vector<Data> MyContainer;

One difficulty is that STXXL provides a special version of std::for_each, stxxl::for_each that is optimised for use with STXXL containers. I'd prefer to use this function when MyContainer is typedeffed as a stxxl::vector.

One solution would be to define my own for_each function that calls the right for_each function and use that whenever I want to call for_each.

Another solution that I'm currently investigating is to overload/specialize std::foreach so that it calls stxxl::for_each whenever it is called with a stxxl::vector<Data>::(const_)iterator as first and second argument.

I cannot get the second idea to work though. I've tried the following:

namespace std
{
    template <class UnaryFunction>
    UnaryFunction for_each(stxxl:vector<Data>::const_iterator first, 
        stxxl:vector<Data>::const_iterator last, UnaryFunction f)
    {
        stxxl::for_each(first, last, f, 4);
    }
}

Along with a similar function for non-const iterators. They don't get called though.

What would be the preferred solution to this problem? How can I get my version of std::for_each for stxxl::vector iterators to get called?

Update: I got the second idea to work now, as posted. The problem was that I was including the wrong file (ouch...). The first question remains though: What is the preferred solution to this problem? Is it okay to overload std::for_each, as the std namespace is not intended for mere mortals?

Answer 1

std::for_each is a public well documented algorithm function, I don't think I wound like it if some library I am using goes around changing it ;-. Possibly other parts of my program need the good old for_each

So I would go with the solution that doesn't break this interface and leaves std::for_each as it is.

Answer 2

You can specialize templates in std (17.4.3.1), but you can't add overloads. Your definition is an overload, not a specialization of the standard for_each template, and in any case functions can't be partially specialized. So it's undefined to put any definition in namespace std that might do what you want.

ADL is supposed to make this work smoothly without any need for that, though. I assume the stxxl iterators are in the stxxl namespace, so for_each(first, last, f, 4); should call stxxl::for_each. If you want std::for_each, you fully qualify the name when you call it.

Answer 3

As much as I would like to say that you want to inject into the std namespace, it really is a sticky wicket as Neil pointed out. The related thread of std::swap points out a number of the details as does the now infamous USENET discussion on the subject.

To sum it up, the only way that you are allowed to inject a name into std is if you can fully specialize it. So, you can write:

namespace std {
    template <>
    MyFunction for_each(stxxl::vector<Data>::const_iterator first,
                        stxxl::vector<Data>::const_iterator last,
                        MyFunction func)
    {
        return stxxl::for_each(first, last, func);
    }
}

for every combination of container and function and you are well within the rules. Unfortunately, partial function template specialization doesn't exist in the current incarnation of the Standard. If you are really curious, dedicate an evening to reading the entire USENET post. It really is quite enlightening and a little frightening. You can probably write a nifty macro (gasp) to automate this for you if you only use a few type/function combinations.

You can use ADL to solve the problem as well provided that none of the stxxl stuff simply exposes an iterator from std using a typedef. I believe that this is generally the preferred solution today.

I would add your own wrapper around for_each that forwards to the appropriate one and call it done. This isn't the most elegant, but it will work now and doesn't rely on any magic to make it happen.

Answer 4

I would not try and specialize std::for_each().
Especially since what you want is partial specialization.

Rather I would write a function that used std::for_each() but had a specialization for stlxxl.
I don't have stlxxl so I have done some code that demonstrates what I mean.

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

//
// Normal version.
template<typename U,typename T,typename A,template<class I,class A> class C>
U Ufor_each(C<T,A>& cont,U const& f)
{
    std::cout << "NORMAL Start" << std::endl;
    return std::for_each(cont.begin(),cont.end(),f);
    return f;
}

// 
// Specialized version.
// You could write a specialized version for stlxxl::vector
template<typename U,typename T>
U Ufor_each(std::vector<T>& cont,U const& f)
{
    std::cout << "Vector Start" << std::endl;
    return std::for_each(cont.begin(),cont.end(),f);
}

struct X
{
    void operator()(int data) const
    {
        std::cout << "Item: " << data << std::endl;
    }
};

int main()
{
    std::vector<int>    vect;
    std::list<int>      list;

    vect.push_back(1);
    list.push_back(4);

    X                   x;
    Ufor_each(vect,x);
    Ufor_each(list,x);
}

I tried but failed to get it working with iterators.

Answer 5

To summarize:

• There is no such thing as partial specialization of functions. Only overloading that function with your specific types
• It is generally forbidden to put stuff in namespace std
• What you really want is to put an overload for for_each in the namespace of the specific iterator types ("next to") you're overloading on. This ensures ADL will find it.