我有一个函数,它接受字符列表并生成下一个字典序排列。为了好玩,我尝试将代码泛化以使用迭代器,并能够生成更多不同类型的排列。
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迭代器等)与使用裸指针?
std::swap
这样的函数? - GManNickGchar*
编写了代码,当我回来时,我只修改了函数定义以便能够接受迭代器。编辑:哦,傻瓜,我忘记了Visual Studio默认情况下不会优化调试版本。 - helloworld922std::next_permutation
会很残忍...即使你想自己实现,阅读标准库的实现也是有教育意义的。 - Potatoswatter