使用迭代器时存在性能问题？

Question

我有一个函数，它接受字符列表并生成下一个字典序排列。为了好玩，我尝试将代码泛化以使用迭代器，并能够生成更多不同类型的排列。

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;
}

当定义了USE_VECTOR时，运行这个测试程序需要大约20秒钟。当我取消定义它时，代码在少于一秒钟内运行（我没有编写任何计时代码，但可以说性能存在非常显著的差异）。

现在我的问题是，我在哪里会受到如此巨大的性能影响，这会影响使用迭代器（如std :: string迭代器、std :: vector迭代器等）与使用裸指针？

- helloworld922

---

好的，你是否打开了优化选项？另外，为什么不使用像 std::swap 这样的函数？ - GManNickG

主要是因为懒惰。我最初使用char*编写了代码，当我回来时，我只修改了函数定义以便能够接受迭代器。编辑：哦，傻瓜，我忘记了Visual Studio默认情况下不会优化调试版本。 - helloworld922

好吧，不提及std::next_permutation会很残忍...即使你想自己实现，阅读标准库的实现也是有教育意义的。 - Potatoswatter

是的，但我写这个是为了学习（而且我是那些觉得算法很有趣的人之一）。当涉及到标准库的东西时，我仍然对使用指针感到有点不舒服，所以我认为这将是一个不错的练习。 - helloworld922

如果你对处理排列组合算法感兴趣，这里有更多有趣的内容：http://home.roadrunner.com/~hinnant/combinations.html。只需阅读规范，而不是源代码，然后尝试实现它。但源代码也在那里。 - Howard Hinnant

Answer 1

如果没有优化，由于迭代器调试（_ITERATOR_DEBUG_LEVEL 在调试模式下默认为2，即完全调试），该代码在我的计算机上也很慢。
然而，使用 /02，迭代器调试被完全禁用，并且代码在控制台窗口显示之前就已经完全执行了。
这里有一个很好的例子，调试使事情变得更慢但更安全。 :)

- Xeo

---

而且通常在调试中事情变慢的另一个优点，当然，就是你不太可能遇到那些在发布模式下困扰你的恶心的旧竞争条件。更加安全;-) - Steve Jessop

@Steve：我很高兴我还不必编写多线程应用程序。 ;) - Xeo

Answer 2

在我的电脑上，这些是时间记录，从以上时间记录中删除 cin.ignore() 并使用基准测试：

$ 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.145秒 用户 0m7.204秒 系统 0m1.088秒

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

实际时间 0m7.693秒 用户时间 0m3.280秒 系统时间 0m0.984秒

没有什么惊人的差异，如果你问我。

现在来点重头戏：

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

真实 0m29.540秒 用户 0m27.294秒 系统 0m0.976秒

- sehe