使用迭代器时的性能问题?

| 我有一个函数,它接收一个字符列表并生成下一个字典顺序排列。为了娱乐,我尝试将代码泛化为使用迭代器,以及能够生成更多不同类型的排列。
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;
}
但是,我遇到的问题是,当我不使用原始指针时,代码的性能会大大降低。这是我的测试台:
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;
}
当定义为“ 2”时,运行此测试装备大约需要20秒钟。当我取消定义它时,代码会在不到一秒钟的时间内运行(我没有编写任何时序代码,但这足以说明性能存在很大差异)。 现在我的问题是,我在哪里受到如此巨大的性能影响,这会影响使用迭代器(std :: string迭代器,std :: vector迭代器等)与原始指针的比较?     
已邀请:
如果不进行优化,由于需要进行大量的迭代器调试(在调试模式下,
_ITERATOR_DEBUG_LEVEL
默认为2,也就是完全调试),因此代码在我的计算机上也很慢。 但是,对于
/02
,迭代器调试将完全禁用,并且代码将在控制台窗口甚至显示之前全部执行。 在这里,您有一个很好的调试示例,该调试使事情变慢但更安全。 :)     
在我的盒子上,这些是时间,这些时间是采取上述时间后,剔除ѭ5并使用以下方法进行基准测试:
$ g++-4.6 -O4 -DUSE_VECTOR -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null
  真正的0m10.145s       用户0m7.204s       sys 0m1.088s
$ g++-4.6 -O4 -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null
  真正的0m7.693s       用户0m3.280s       sys 0m0.984s **如果您问我,那儿没有惊人的区别** 现在开始:
$ g++-4.6 -O0 -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null
  真正的0m29.540s       用户0m27.294s       sys 0m0.976s     

要回复问题请先登录注册