Iterators and templates

Question

I'm trying to implement a function which allows the user to input some type of begin and end iterator, then all perform some operation on the data. However, the function has to be generic enough it should work for many types of iterators (for example std::vector::iterator, std::string::iterator, std::iterator, etc.). The only limit is that the iterators have to be at least forward_iterator_tag capabilities.

My function prototype looks like this:

template <class key_type, class data_type> std::shared_ptr<data_type> 
    remove(std::iterator<std::forward_iterator_tag, key_type> key_start, 
    std::iterator<std::forward_iterator_tag, key_type> key_end);

However, this limits me to using specifically a forward_iterator_tag iterator, so trying to call the function like this:

remove<char, char>(std::iterator<std::random_access_iterator_tag, char>(), std::iterator<std::random_access_iterator_tag, char());

will fail because the compiler can't convert a std::iterator<std::random_access_iterator_tag,...> to a std::iterator<std::forward_access_iterator_tag,...>. Additionally, this method does not work for string iterators, vector iterators, or other stl iterators.

Does someone know how the stl implements the containers/strings to accept iterators from each other? For example, this compiles correctly:

std::string a = "hello";
std::vector<char> v(a.begin(), a.end());

Answer 1

template < typename Iter >
void fun_impl(Iter begin, Iter end, std::forward_iterator_tag)
{
  // do your stuff here...
}

template < typename Iter >
void fun(Iter begin, Iter end)
{
  fun_impl(begin,end, std::iterator_traits<Iter>::iterator_category());
}

The types returned by begin() and end() for various containers are not of type iterator<category...> but subclasses of such (sometimes). You never, when you're writing generic code, target a specific iterator type. Instead you use "tag dispatching" to classify the iterator and call the correct implementation. Since random_iterator_tag is-a forward_iterator_tag it will be automatically converted to such so that the above fun_impl will resolve correctly for any forward_iterator or extension.