c++ - 如何只用STL算法实现这个功能

Question

我必须实现一个函数，该函数按字典顺序在控制台上打印每个字符串，首字母为 char c，仅使用 STL 算法。

这是我的想法:

void f(const std::vector<std::string>& vs, const char c)
{   
    std::vector<std::string> tmp = vs;

    std::sort(tmp.begin(), tmp.end());
    std::ostream_iterator<std::string> out(std::cout, "\n");
    std::copy_if(tmp.begin(), tmp.end(), out, *predicate*); 

}

作为谓词我认为:

//*(tmp.begin()->begin()) == c);

但它不起作用。

Answer 1

您得到的答案看起来简单而整洁，但如果您有大量不适合过滤器的数据(在本例中以“c”开头)，则效率可能会非常低下。

我看到两个基本问题。首先，他们对所有数据进行排序，无论它是否符合过滤器。这本身就很低效。其次，他们随后使用 copy_if 对数据进行过滤后的复制——但 copy_if 并没有利用排序的优势。它进行线性搜索，因此它查看所有所有输入数据，包括很多正确的算法已经知道不值得考虑的数据(例如，一旦它得到以 ' 开头的东西d'，它还不如停止，因为没有更多的数据值得考虑)。

或者，他们先进行过滤，但是通过复制所有相关数据到新创建的 vector ，然后对数据拷贝进行排序。这在速度方面可能相当有效，但可能会占用大量额外内存。

我认为最好先过滤但不要进行不必要的复制，然后只对符合过滤条件的数据进行排序，最后将排序后的数据复制到输出。在这种情况下，我们可以使用 std::partition 来高效地过滤数据。

auto end = std::partition(in.begin(), in.end(), 
    [](std::string const &s) { return s[0] == 'c';});

std::sort(in.begin(), end);
std::copy(in.begin(), end, std::ostream_iterator<std::string>(std::cout, "\n"));

除了 std::partition 的异常可怕的实现之外，先过滤再排序应该至少与先排序再过滤一样快——如果大量原始输入被过滤掉，首先过滤可能要快得多。与创建过滤拷贝然后排序拷贝相比，它显然可以节省相当多的内存。在大多数情况下，它也会快很多。分区只需要交换字符串，而不是复制它们，这通常要快得多(当 std::string 使用短字符串优化时，主要的异常(exception)是短字符串).