Bha*_*ali 3 c++ stl stl-algorithm
而在C++ STL使用的算法,我发现的类似的方法很多std::merge,std::inplace_merge,std::set_union,std::upper_bound,std::lower-bound等...只需要排序的数据作为输入.
有意义的是,在排序数据上,这些算法会提供更快的结果,但为什么它们也不能处理未排序的数据呢？为什么大多数算法都设计有这样的数据依赖？
有意义的是,在排序数据上,这些算法会提供更快的结果,但为什么它们也不能处理未排序的数据呢？为什么大多数算法都设计有这样的数据依赖？
对于排序数据的"有意义"的算法,开发人员应该知道是否是这种情况,并且可以根据需要轻松地对输入进行排序.算法可以检查数据是否先排序,但这会浪费时间.例如,upper_bound可以是预先排序的输入上的O(logN),而检查排序将是O(N).还要记住,一般情况下,算法无处可存储状态,说"我检查了一次并且数据已经排序"(并且他们怎么能知道在不了解线程存在的情况下如何使用锁等等将持续多长时间),所以他们必须为每次调用数据做这件事.
此外,您提到的一些算法 - 例如std::merge- 可以在InputIterators上使用,这意味着您可以处理只能读取一次的输入,例如从键盘可以暂时可用但不会自动保留在任何地方供您重新访问,所以有一个额外的传递来检查某些人的输入值是否已经排序是不切实际的.