rotate algorithm seems inefficient for bidirectional iterators

[Sidney Marshall]

I was looking at the implementation of the rotate(first, middle, 
last) algorithm and found what I think is an inefficiency. The number 
of swaps for forward iterators and random access iterators is 
generally the same but for bidirectional iterators is sometimes much 
greater. For the case where the two halves are equal it uses twice as 
many swaps. Running the code:

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <cstdlib>
#include <algorithm>

using namespace std;

static long int c;

class swapable {
   swapable() { // needed to count all swaps - maybe to make this a non pod
   }
};

void swap(swapable &a, swapable &b) {
   c++;
}

template<class T>
void doit(T container) {
   auto b = container.begin();
   auto e = container.end();
   c = 0;
   for(auto m = b; m != e; ++m) {
     rotate(b, m, e);
   }
   cout << "c: " << c << endl;
}

int main(int argc, char *argv[]) {
   int n = atoi(argv[1]);
   cout << "n: " << n << endl;
   doit(forward_list<swapable>(n));
   doit(list<swapable>(n));
   doit(vector<swapable>(n));
}

I can count the number of swaps. It is always true that the 
bidirectional iterator does equal or more swaps than the forward 
iterator. Looking at the code verifies this observation. Why is the 
bidirectional code used at all?

If this is an inappropriate message, please let me know. If you would 
like me to examine other algorithms also let me know.

--Sidney Marshall