C++ map erase using forward and reverse iterators

Question

I have a template function like this

template<typename T>
void foo(T start , T end)
{
  while(start != end)
  {
     if(cond)
       m.erase(start);
    start++;
  }

}

Now I have to pass both forward and reverse iterator as the typename. Two separate calls in which one is forward and one is reverse iterator. How do I do this ?

Why create artificial problems? Pass in compatible iterators. — LogicStuff, May 09 '16 at 09:07
Then I would require two separate functions and whenever something changes, I would have to remember to change both — Ram, May 09 '16 at 09:12

score 2 · Accepted Answer · edited May 23 '17 at 12:24

First of all, let me reiterate LogicStuff's comment: You should really try to pass in compatible iterators instead.

If you really, really, really have no alternative to doing it the way you are doing it right now, you could use some template functions:

#include <vector>
#include <iostream>

// Used when both iterators have the same type
template <typename T>
void foo(T begin, T end)
{
  for (; begin != end; ++begin)
  {
    std::cout << " " << *begin;
  }
}

// Overload for a forward begin and reverse end
template <typename T>
void foo(T begin, std::reverse_iterator<T> end)
{
  foo(begin, end.base());
}

// Overload for a reverse begin and forward end
template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(begin, std::reverse_iterator<T>(end));
}

int main()
{
  std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  foo(v.begin(), v.end()); std::cout << std::endl;
  foo(v.begin(), v.rbegin()); std::cout << std::endl;
  foo(v.rbegin(), v.begin()); std::cout << std::endl;
  foo(v.rbegin(), v.rend()); std::cout << std::endl;
}

See it running on ideone.

Here I convert reverse iterators to forward iterators. This SO post gives you more details about that. But read that post very carefully, there be dragons. My example above just outputs numbers and does not modify the underlying container. And I do not check the validity of the iterators, nor do I do any bounds checking. For your own case, make sure you test all the edge cases (either iterator being at or beyond the beginning/end of your container; off-by-one errors, etc.).

Also, note that in your example code, the call to erase() invalidates the iterator, so you should write the loop body like this:

if (cond) {
  // guarantees to return an iterator to the element following
  // the erased element.
  start = m.erase(start);
} else {
  ++start;
}

Edit: If you require that iterators are always converted to their forward equivalents, you can change the last overload and add another:

template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(end, begin.base()); // Note: order of iteration reversed!
}

template <typename T>
void foo(std::reverse_iterator<T> begin, std::reverse_iterator<T> end)
{
  foo(end.base(), begin.base()); // Note: order of iteration reversed!
}

But be aware that the order of iteration is now reversed: in my example, calling foo(v.rbegin(), v.rend()) printed 9 8 7 ... 1 in the first incarnation, and now it prints 1 2 3 ... 9. Example here.

And again, you'd be off much better if you could feed in compatible iterators instead.

I am not very sure how you would go about after creating this function signature template void foo(T start, U end) — Ram, May 09 '16 at 09:18
Yes, I'm working on expanding my answer. Give me a moment :) — mindriot, May 09 '16 at 09:19
Thanks for your solution mindriot. But my main problem is calling erase function inside the template function. Erase requires only forward iterators, while the template accepts both forward and reverse iterators. Any other way of doing the same ? — Ram, May 09 '16 at 09:44

C++ map erase using forward and reverse iterators

1 Answers1