Performance issues when using iterators?

Question

I have a function that takes a list of characters and generates the following lexicographic permutation. For fun, I tried to generalize the code for using iterators, as well as the ability to generate permutations of more different types.

template<typename ITER> bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag) { for(ITER i = end-1; i != start; --i) { if(*(i-1) < *i) { // found where can be swapped for(ITER j = end-1; j != (i-1); --j) { if(*(i-1) < *j) { // found what to swap with auto temp = *j; *j = *(i-1); *(i-1) = temp; // put everything from i on into "sorted" order by reversing for(ITER k = end-1; k > i; --k,++i) { temp = *k; *k = *i; *i = temp; } return true; } } } } return false; } 

However, I run into problems when, when I do not use raw pointers, code performance is much slower. Here is my test setup:

 template<typename ITER> bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag); template<typename ITER> bool nextPermutation(ITER start, ITER end) { return nextPermutation(start, end, std::iterator_traits<ITER>::iterator_category()); } #define USE_VECTOR int main(void) { bool hasNext = true; #ifdef USE_VECTOR std::vector<char> c; for(char i = '0'; i <= '9'; ++i) { c.push_back(i); } for(size_t i = 0; i < 999999 && hasNext; ++i) { hasNext = nextPermutation(c.begin(), c.end()); } #else char c[] = "0123456789"; size_t LENGTH = 10; for(size_t i = 0; i < 999999 && hasNext; ++i) { hasNext = nextPermutation(c, c+LENGTH); } #endif std::cout << "done" << std::endl; std::cin.ignore(); return 0; } 

When USE_VECTOR defined, it takes ~ 20 seconds to run this test setup. When I determine this, the codes work in less than a second (I did not write a synchronization code, but suffice it to say that there is a very significant difference in performance).

Now my question is, where do I take such a huge performance hit that will affect the use of an iterator (std :: string iterator, std :: vector iterator, etc.) compared to a raw pointer?

Answer 1

Without optimization due to heavy debugging of the iterator ( _ITERATOR_DEBUG_LEVEL is set to 2 by default in debug mode, as well as full debugging), my machine also has slow code.
However, with /02 iterator debugging is completely disabled, and the code runs completely until the console window appears.
Here you have a good debugging example that makes things slower but more secure. :)

Answer 2

In my window, these are timings, taking the above time, removing cin.ignore() and comparing them with:

 $ g++-4.6 -O4 -DUSE_VECTOR -std=gnu++0x t.cpp -ot $ time for a in $(seq 1 1000); do ./t; done > /dev/null 

real 0m10.145s user 0m7.204s sys 0m1.088s

 $ g++-4.6 -O4 -std=gnu++0x t.cpp -ot $ time for a in $(seq 1 1000); do ./t; done > /dev/null 

real 0m7.693s user 0m3.280s sys 0m0.984s

** There is no shocking difference if you ask me **

Now for the hit:

 $ g++-4.6 -O0 -std=gnu++0x t.cpp -ot $ time for a in $(seq 1 1000); do ./t; done > /dev/null 

real 0m29.540s user 0m27.294s sys 0m0.976s