仅通过一次循环将C++标准算法组合

Question

我目前已经拥有并运行了这段代码：

string word="test,";
string::iterator it = word.begin();
for (; it != word.end(); it++)
{
    if (!isalpha(*it)) {
        break;
    }
    else {
       *it = toupper(*it);
    }
}
word.erase(it, word.end());
// word should now be: TEST

我希望通过以下方式使其更加紧凑和易读：

1. 组合现有的标准C++算法(*)
2. 仅执行一次循环

(*) 我假设组合现有的算法可以使我的代码更易读...

另一种解决方案

除了像jrok建议的定义自定义transform_until算法之外，还可以定义一个自定义迭代器适配器，该适配器使用基础迭代器进行迭代，但在返回之前通过修改基础引用来重新定义operator*()。类似这样：

template <typename Iterator, typename UnaryFunction = typename Iterator::value_type (*)(typename Iterator::value_type)>
class sidefx_iterator: public std::iterator<
                         typename std::forward_iterator_tag,
                         typename std::iterator_traits<Iterator>::value_type,
                         typename std::iterator_traits<Iterator>::difference_type,
                         typename std::iterator_traits<Iterator>::pointer,
                         typename std::iterator_traits<Iterator>::reference >
{
  public:
    explicit sidefx_iterator(Iterator x, UnaryFunction fx) : current_(x), fx_(fx) {}

    typename Iterator::reference operator*() const { *current_ = fx_(*current_); return *current_; }
    typename Iterator::pointer operator->() const { return current_.operator->(); }
    Iterator& operator++() { return ++current_; }
    Iterator& operator++(int) { return current_++; }
    bool operator==(const sidefx_iterator<Iterator>& other) const { return current_ == other.current_; }
    bool operator==(const Iterator& other) const { return current_ == other; }
    bool operator!=(const sidefx_iterator<Iterator>& other) const { return current_ != other.current_; }
    bool operator!=(const Iterator& other) const { return current_ != other; }
    operator Iterator() const { return current_; }

  private:
    Iterator current_;
    UnaryFunction fx_;
};

当然，这还是很初步的，但它应该能够给出思路。有了上述的适配器，我接下来可以编写以下代码：

word.erase(std::find_if(it, it_end, std::not1(std::ref(::isalpha))), word.end());

预先定义以下内容（可通过一些模板魔法简化）：

using TransformIterator = sidefx_iterator<typename std::string::iterator>;
TransformIterator it(word.begin(), reinterpret_cast<typename std::string::value_type(*)(typename std::string::value_type)>(static_cast<int(*)(int)>(std::toupper)));
TransformIterator it_end(word.end(), nullptr);

如果标准包括这样的适配器，我会使用它，因为这意味着它是无缺陷的，但由于情况并非如此，我可能会保持我的循环不变。

这样的适配器将允许重用现有算法，并以不同的方式进行混合，这是今天不可能的，但它也可能有缺点，我可能目前正在忽视...

- José Mari

---

在我的当前代码中只有一个循环。我的意思是，在重写后仍然只会有一个循环。 - José Mari

基于 !isalpha(*it) 的过早退出是我唯一可能阻止你实现你所追求的目标的事情，而且老实说，任何可能做到这一点的方法（我一眼看不出来有什么）都很复杂，会让你的清晰度降低。 我建议你还是坚持现在的做法。 - WhozCraig

感谢大家的启发性回答。我现在会继续使用我的当前代码。我相信boost::transform_iterator是我正在寻找的最接近的东西。这种用例将被“副作用”迭代器适配器所覆盖，类似于这样使用：word.erase(std::find_if(sidefx_iterator(word.begin(), ::toupper), word.end(), std::not1(::isalpha)), word.end()); - José Mari

Answer 1

我认为没有一种干净的方法可以使用单一的标准算法来完成这个任务。据我所知，没有一个算法可以接受谓词（你需要一个来决定何时提前停止）并允许修改源序列中的元素。

如果你真的想按照“标准”方式完成，可以编写自己的通用算法。让我们称之为——呃，transform_until:

#include <cctype>
#include <string>
#include <iostream>

template<typename InputIt, typename OutputIt,
         typename UnaryPredicate, typename UnaryOperation>
OutputIt transform_until(InputIt first, InputIt last, OutputIt out,
                         UnaryPredicate p, UnaryOperation op)
{
    while (first != last && !p(*first)) {
        *out = op(*first);
        ++first;
        ++out;
    }
    return first;
}

int main()
{
    std::string word = "test,";
    auto it =
    transform_until(word.begin(), word.end(), word.begin(),
                    [](char c) { return !::isalpha(static_cast<unsigned char>(c)); },
                    [](char c) { return ::toupper(static_cast<unsigned char>(c)); });
    word.erase(it, word.end());
    std::cout << word << '.';
}

这个还有待商榷，是否比你现有的好取决于具体情况 :) 有时候，简单的for循环是最好的选择。

- jrok

---

+1，这大概是我认为楼主能得到的最好结果了。虽然他可能应该坚持计划 A 并保留他的循环，但这个答案是一个相当不错的概念转换成实现的例子，适当地命名所有自定义容器转换器，并且回答了楼主的问题。即使楼主不使用它，这仍然是一个好答案。 - WhozCraig

我接受了这个答案，因为生成的代码短小易读，并且表达了一般算法，在一般情况下非常有用。所有现有的STL算法都有一个固定的结束迭代器，并需要在整个容器中进行循环。我认为能够有一个条件性结束是一种普遍需求。 - José Mari

Answer 2

在更好地理解您的问题后，我有一个可能可行但需要 Boost 的想法。

您可以使用 transform_iterator，它会对所有字符调用 toupper 并将其用作 find_if 或 remove_if 的输入迭代器。不过，我对 Boost 不够熟悉，无法提供示例。

正如 @jrok 指出的那样，transform_iterator 仅在迭代期间转换值，而不会实际修改原始容器。为了解决这个问题，您需要将其复制到新容器中，使用类似 remove_copy_if 的东西。只要谓词不为真，就会进行复制，因此需要使用 std::not1。这将替换 remove_if 的情况。

使用std::copy函数复制，直到由std::find_if返回的迭代器以使另一种情况起作用。

最后，如果您的输出字符串为空，则需要一个std::inserter类型的迭代器来输出。

- Karthik T

---

它循环了两次 - OP想避免这种情况。 - jrok

@MariJosé，啊，我现在更好地理解你的问题了，是的，你是正确的，有两个循环。 - Karthik T

@MariJosé，新的想法更接近你想要的吗？ - Karthik T

Roberto，在使用 boost::transform_iterator 时，两个循环仍然在 O(N) 范围内，因为它们不是两个完整的循环，除非我漏掉了一些明显的东西。 - José Mari

boost::transform_iterator 无法解决这个问题，因为它不会修改序列，只是在解引用时返回一个转换后的值。 - jrok