I used boost::iterator_adapter with a std::vector iterator, all parameters set to boost::use_default. (So this is the same as a plain std::vector iterator) With this configuration, the iterator tag is recognized as "input_iterator_tag" not "random_iterator_tag" as it must be. This hurts because the iterator tag is used to select the right std::distance function. I could solve the problem by explicitly setting the traversal type template parameter to "std::random_access_iterator_tag", while "boost::random_access_traversal_tag" also didn't work. The compiler is VC8.