On this topic, what is the difference between boost::random_access_traversal_tag and std::random_access_iterator_tag,
Take a look at http://www.boost.org/doc/libs/1_47_0/libs/iterator/doc/new-iter-concepts.htm...
and should I implement both?
One or the other, not both. I would image that for Boost libraries, the convention is to use the Boost concepts, but I'm no authority on this.
What is the reasoning for not both?
Because they're pretty much the same thing. Your tag dispatching logic will be something like this: if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag) call the random access version else call the input iterator version Of course it won't look like that, the choice will be made at compile time via template specialization, but that's the logic. You can also have the logic: if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag) call the random access version else call the input iterator version But it wouldn't make sense to do something like: if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag) call the random access version else if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag) call the random access version else call the input iterator version because the first case covers all the random access iterators already. Hope that makes sense... or maybe I'm misunderstanding what you mean by "implement both"? Regards, Nate