我必须实现一个函数，该函数在控制台上按字典顺序打印每个字符串，该字符串作为第一个字母，字符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);
但它不起作用。
你得到的答案看起来简单而整洁，但如果你有很多数据不符合过滤器(在这种情况下以"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使用短字符串优化时，主要例外是短字符串)。
我认为对所有元素进行排序然后仅打印以c开头的元素是一种浪费。不如只对那些进行排序呢？
struct first_char_is {
char x;
first_char_is(char x) : x(x) {}
bool operator()(const std::string& s) {
return s.size() > 0 && s[0] == x;
}
};
void f(const std::vector<std::string>& vs, const char c)
{
std::vector<std::string> tmp;
std::copy_if(vs.begin(), vs.end(), std::back_inserter(tmp),
first_char_is(c));
std::sort(tmp.begin(), tmp.end());
std::ostream_iterator<std::string> out(std::cout, "n");
std::copy(tmp.begin(), tmp.end(), out);
}
然而，在C++字符串是可变的，COW 字符串实现有其自身的问题。这意味着当您复制字符串向量时，所有字符串数据也会重复。为了节省内存，另一种方法是保留原始数组的索引并对其进行排序，但我不确定这是否符合"仅 stl"人工要求(无论这可能意味着什么)。
struct IndirectComp {
const std::vector<std::string>& vs;
IndirectComp(const std::vector<std::string>& vs) : vs(vs) {}
const bool operator()(int a, int b) {
return vs[a] <= vs[b];
}
};
void f(const std::vector<std::string>& vs, const char c)
{
std::vector<int> ix;
for (int i=0,n=vs.size(); i<n; i++) {
if (vs[i].size() && vs[i][0] == c) {
ix.push_back(i);
}
}
std::sort(ix.begin(), ix.end(), IndirectComp(vs));
for (int i=0,n=ix.size(); i<n; i++) {
std::cout << vs[ix[i]] << "n";
}
}
最简单的方法是使用 lambda 作为谓词：
void f(std::vector<std::string> vs, const char c)
{
std::sort(vs.begin(), vs.end());
std::ostream_iterator<std::string> out(std::cout, "n");
std::copy_if(vs.begin(), vs.end(), out,
[c](const std::string & s){return !s.empty() && s.front() == c;}
);
}
仅使用<algorithm>编写谓词是不可能的。然而，λ可以用std::bind、std::equal_to、std::string::front、std::logical_and和<functional>std::string::empty来重建。但是，这将使您的代码非常复杂。
由于您已经在使用 C++11，因此我建议您使用 lambda。
像本杰明·林德利一样，我认为公认的答案是次优的，这可能是一个更好的方法(未经测试，但你明白了)：
void f(std::vector<std::string> vs, const char c)
{
std::vector<std::string> result;
std::copy_if(vs.begin(), vs.end(), std::back_inserter(result),
[c](const std::string& s) { return !s.empty() && s.front() == c; });
std::sort(result.begin(), result.end());
std::copy(result.begin(), result.end(), std::ostream_iterator(std::cout, "n"));
}
如果我们假设输入向量有N个条目，其中K以字母c开头，那么这将执行O(N)搜索/复制，然后是O(K.logK)(平均)排序，然后O(K)"复制"到输出流。Zeta回答中的方法首先具有O(N.logN)排序，如果K << N，它将占主导地位(正如我们对常规文本所期望的那样)。
编辑：正如Jerry Coffin的回答所指出的那样，如果弄乱输入向量是可以接受的(这是原始问题中的常量引用)，那么您可以使用std::partition在没有临时副本的情况下逃脱 - 感谢他想到这一点。
有 3 个解决方案：
- 排序然后复制满足您要求的元素，复杂 N*log(N) + N
- 复制满足您要求的元素然后排序，复杂度 N+n*log(n)
- 排序并搜索范围 std：：下限，复杂度 N*log(N) + 2*log(N) + n
在所有情况下，N 是向量的大小，n 是满足谓词的元素数。一般来说，n<=N，根据您的数据集(普通的英语文本)，它可以是n<<N。