c++ - 如何使用 STL 算法找到分隔字符串中两个不同字母的最短星号序列？

Question

我有这样一个字符串:

A*A**B***A**

我对两个不同字母之间的星号序列感兴趣，特别是我需要找到最短的此类序列的长度。对于上面的字符串，答案当然是 2:A**B

我可以使用我习惯的传统循环轻松解决这个问题:

const string s = "A*A**B***A**";
string::size_type last_letter=-1, min_seq_len=s.size();
for(int i = 0; i < s.size(); i++) {
    if(last_letter == -1 || s[i] == '*' || s[i] == s[last_letter]) {
        if(s[i] != '*') {
            last_letter = i;
        }
    } else {
        min_seq_len = min(min_seq_len, i-last_letter-1);
        last_letter = i;
    }
}

但是，有没有办法使用 C++ 来做到这一点 algorithms library 、迭代器等？

我问这个问题是因为我注意到我在学习如何使用这些工具来解决算法问题时遇到了困难，相反我发现手动编写循环更容易。我想最终学习 C++ 算法、范围、迭代器等的操作。

Answer 1

I'm interested in sequences of asterisks that are between two distinct letters, in particular I need to find the length of the shortest such sequence.

1. 你需要最小化一些东西。您可以使用 std::min_element为此。

2. 那东西是一堆“字母+星号+字母” block 。您可以使用 std::find_if 查找非星号.

然后您需要在算法之间编写一些胶水，您可以将其隐藏在类似 STL 的接口(interface)后面。示例:

auto letter_pairs = letter_pair_generator(s);
const auto min_seq_len = std::min_element(
    std::begin(letter_pairs), std::end(letter_pairs),
    [](const auto& x) { return x.asterisk_count(); });

在哪里letter_pair_generator是 std::string 上的适配器它公开了一个类似容器的界面，该界面返回一对不同的字母，中间有星号。示例:

string s = "A*A**B***A**";
for(const auto& p : letter_pair_generator(s)) cout << p;

A*A**B

A**B

A**B***A

B***A

---

instead I find writing loops by hand easier

有时循环比多次调用 <algorithm> 更清晰、更快.这本质上没有错。使用循环并将其包装到更安全/更好的界面中。