为什么std :: is_permutation()这样的函数本身不安全？

Question

C和C++程序员在过去十年左右的时间里经常受到打击,因为他们经常无法执行正确的边界检查,特别是在字符串上.这些故障经常导致主要软件产品出现严重的安全问题.由于缓冲区溢出的不安全感变得很好理解,驱动提起正确的边界检查也像推很多程序员从传统buffer-和字符串处理函数strcpy()和sprintf()至少部分是因为这些功能的倾向,通过使邀请缓冲区溢出问题关于目标缓冲区大小的假设.一个STL类型等优点std::string,并std::vector为他们的缓存访问强有力的控制.

但有一件事困扰着我.<algorithms>C++标头中许多最广泛使用的函数似乎都积极地乞求溢出滥用:特别是那些采用begin迭代器(尤其是InputIterator)而没有匹配end迭代器的函数.例如:

template <class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);

template <class InputIterator, class OutputIterator, class UnaryOperation>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperation op);

template <class ForwardIterator1, class ForwardIterator2>
   bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2);

最后一个例子 - is_permutation()特别有启发性.copy()并且transform()很容易理解,因此C++程序员应该知道在调用这些函数之前手动检查输出容器的边界,或者使用类似的东西back_inserter来确保输出容器根据需要增长.因此,可以说,虽然copy()并且transform()可以被滥用,但任何事情都可以,并且程序员很容易接受有关这些功能的最佳实践的教育.

is_permutation()是一个棘手的案例.只要看一下上面的函数声明,你会假设第二个范围的大小(开头的那个first2)？第二个范围是否需要与第一个范围相同,或者不小,或者不大？我打赌,这些问题的简单答案并没有出现在你脑海中.对于大多数程序员而言,"置换"的概念并不像复制概念那样舒适和熟悉.因此,似乎相对容易is_permutation()出错并以某种方式溢出缓冲区.

"抬头看看!" 我听你说.嗯,是的,当然.但是,如果程序员记住他们应该做的一切,并查找其他所有内容,那么我们就不会有错误和安全漏洞,是吗？

那么,为什么没有is_permutation()和类似的函数(即函数占用所有输入迭代器而不是每个范围的完整的开始端迭代器对)需要一个完整的开始 - 结束对所有输入范围？(注意lexicographical_compare(),例如,确实满足了这个要求.)函数is_permutation()实际上并不像我想象的那样不安全吗？

Answer 1

大多数语言本质上都是不安全的,程序员可以正确使用它.程序员在调用函数之前必须知道所使用的参数是否正确.

此外,在某些情况下,copy它可以在开放范围内使用前向迭代器.例如:

std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout," "));

没有相应的迭代器来标记流的结尾,并且流确实没有结束,您可以继续添加它.

Answer 2

在C++ 14中,有四个迭代器版本equal,is_permutation并且mismatch正是为了解决这一点.