如何仅使用stl algotithms实现此功能

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"开头,那还不如停止,因为没有更多的数据值得考虑).

或者,他们首先进行过滤,但是通过将所有相关数据复制到新创建的向量,然后对数据副本进行排序来进行过滤.这在速度方面可能相当有效,但可能会使用相当多的额外内存.

我认为最好先过滤但不进行不必要的复制,然后只对适合过滤器的数据进行排序,最后将排序后的数据复制到输出中.在这种情况下,我们可以用来有效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使用短字符串优化时的短字符串).