Combining C++ standard algorithms by looping only once

Question

I currently have this code up and running:

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

I would like to make it more compact and readable it by:

Composing existing standard C++ algorithms (*)
Perform the loop only once

(*) I'm assuming that combining existing algorithms makes my code more readable...

An alternative solution

In addition to defining a custom transform_until algorithm, as suggested by jrok, it might be possible to define a custom iterator adaptor that would iterate using the underlying iterator but redefine operator*() by modifying the underlying reference before returning it. Something like that:

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_;
};

Of course this is still very raw, but it should give the idea. With the above adaptor, I could then write the following:

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

with the following defined in advance (which could be simplified by some template-magic):

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);

If the standard would include such an adaptor I would use it, because it would mean that it was flawless, but since this is not the case I'll probably keep my loop as it is.

Such an adaptor would allow to reuse existing algorithms and mixing them in different ways not possible today, but it might have downsides as well, which I'm likely overlooking at the moment...

In my current code there is a single loop. My point was that after rewriting there would still be a single loop. — José Mari, Dec 27 '12 at 13:09
The premature exodus based on `!isalpha(*it)`is the only thing I see potentially stopping you from achieving what I think you're looking for, and honestly, anything that may do that for your (and I can't see anything immediately that would) would likely be so convoluted you're clarity-factor would go out the window. I'd likely stick with what you have. — WhozCraig, Dec 27 '12 at 14:11
Thank you all for your inspiring answers. I will stick with my current code for now. I believe that `boost::transform_iterator` is the nearest thing I was looking for. This use case would be covered by a "side-effects" iterator adapter, something to be used like this: `word.erase(std::find_if(sidefx_iterator(word.begin(), ::toupper), word.end(), std::not1(::isalpha)), word.end());` — José Mari, Dec 27 '12 at 14:25

score 9 · Accepted Answer · answered Dec 27 '12 at 14:06

I don't think there's a clean way to do this with a single standard algorithm. None that I know of takes a predicate (you need one to decide when to break early) and allows to modify the elements of the source sequence.

You can write your own generic algorithm if you really want to do it "standard" way. Let's call it, hmm, 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 << '.';
}

It's debatable whether this is any better than what you have :) Sometimes a plain for loop is best.

+1, This is about as good as I think the OP is going to get. While he should likely stick with plan A and just keep his loop, this answer is a pretty good concept-to-impl of writing a custom container transformer, appropriate name an all, and still answers the OP's question. Even if the OP doesn't use it, still a good answer. — WhozCraig, Dec 27 '12 at 14:25
I've accepted this answer because the resulting code is short and readable, and expresses a general algorithm that would be useful in general. All existing STL algorithms have a fixed end iterator and require a loop throughout the whole container. I think it is a general need to be able to have a conditional end. — José Mari, Dec 29 '12 at 11:16

score 0 · Answer 2 · edited Apr 02 '16 at 22:20

0

After better understanding your question, I have got an idea that might work, but requires Boost.

You could use a transform_iterator which calls toupper on all characters and use that as the inputiterator to find_if or remove_if. I am not familiar enough with Boost to provide an example though.

As @jrok points out, the transform_iterator will only transform the value during iteration and not actually modify the original container. To get around this, instead of operating on the same sequence, you would want to copy to a new one, using something like remove_copy_if. This copies as long as the predicate is NOT true, so std::not1 would be needed. This would replace the remove_if case.

Use std::copy to copy until the iterator returned by std::find_if to get the other case to work.

Finally, if your output string is empty, it will need a std::inserter type of iterator for the output.

edited Apr 02 '16 at 22:20

Peter Mortensen

30,738
21
105
131

answered Dec 27 '12 at 13:09

Karthik T

31,456
5
68
87

It's looping twice - OP wanted to avoid that. – jrok Dec 27 '12 at 13:10
It looks like there are two loops in your implementation... Am I wrong? – José Mari Dec 27 '12 at 13:11
@MariJosé Ah i better understand your question now, yes you are correct,there are 2 loops. – Karthik T Dec 27 '12 at 13:12
@MariJosé is the new idea closer to what you want? – Karthik T Dec 27 '12 at 13:22
Roberto, when using `boost::transform_iterator` the two loops are still within O(N) overall, because they are not two *complete* loops, unless I'm missing something obvious – José Mari Dec 27 '12 at 14:50
`boost::transform_iterator` won't solve it, because it doesn't modify the sequence, it just returns a transformed value on dereference. – jrok Dec 27 '12 at 15:14
@jrok yes thats true. Copying instead of operating on the same string would work though yes? – Karthik T Dec 27 '12 at 15:20
Yes, but you can't break early with any of sequence modifying algos :) – jrok Dec 27 '12 at 15:24
@jrok yes true. It is either hand written code as in yours or OPs case or extra memory cost to copy as in my case. – Karthik T Dec 27 '12 at 15:28

Combining C++ standard algorithms by looping only once

An alternative solution

2 Answers2

Linked