In general looks really good, thanks! (just a few comments)
Question: how is this loop more efficient than the non-random access iterator version?
Can you also check the complexity requirement?
Can you also check the permutable constraint?
Please also check an odd number of elements.
Nit: make it a struct, so that it won't be necessary to specify public?
- Address comments
In the forward variant we have to check that __first != __end and __first != --__end. In the random-access version we can just check that __first < --__end, so we do half the comparisons.
I made everything else in this file a class and then made it public. I'd rather keep it that way for consistency.