Iterate in reverse given the bound iterators of a range C-CodePudding

Let's say I have a vector std::vector<int> nums; and I have two iterators lower_boud and upper_bound. I want to traverse nums from upper_bound to lower_boud while applying a function to numbers without using loops or allocating any memory. I have found std::transform but I'm not sure how to traverse in reverse.

CodePudding user response：

One can use std::reverse_iterator to change direction of any bidirectional iterator. Just be careful that std::transform(b,e,...) requires b<=e so the positions of reversed iterators must be exchanged.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums{1, 2, 4, 5, 6, 7, 8, 9};
    auto lb = std::lower_bound(nums.begin(), nums.end(), 2);
    auto ub = std::upper_bound(nums.begin(), nums.end(), 8);

    std::vector<int> out1;
    std::cout << "FORWARD\n";
    std::transform(lb, ub, std::back_inserter(out1), [](const auto& e) {
        std::cout << "Transforming forward:" << e << '\n';
        return e;
    });
    std::cout << "REVERSED\n";
    std::vector<int> out2;
    std::transform(std::reverse_iterator(ub), std::reverse_iterator(lb),
                   std::back_inserter(out2), [](const auto& e) {
                       std::cout << "Transforming backward:" << e << '\n';
                       return e;
                   });
}

Output:

FORWARD
Transforming forward:2
Transforming forward:4
Transforming forward:5
Transforming forward:6
Transforming forward:7
Transforming forward:8
REVERSED
Transforming backward:8
Transforming backward:7
Transforming backward:6
Transforming backward:5
Transforming backward:4
Transforming backward:2

CodePudding user response：

std::transform is the wrong standard algorithm if you just want to iterate over the elements, as it requires another iterator to insert the transformed results to (of which the target then requires additional memory). Instead std::for_each is your friend then, in combination with std::reverse_iterator. Note that as you want to iterate from ub down to lb you need to use the reversed ub as starting index and the reversed lb as ending one (this part adopted from Quimby's answer):

std::for_each(std::reverse_iterator(ub), std::reverse_iterator(lb), f);

with f being the function to be applied.

An alternative approach is searching the right iterators directly from the std::vector:

auto lb = std::lower_bound(v.rbegin(), v.rend(), maxValue, std::greater<int>());
auto ub = std::upper_bound(v.rbegin(), v.rend(), minValue, std::greater<int>());

std::for_each(lb, ub, f);

Note that the definition of lower and upper bound applied here contradict the natural feeling of these bounds – in the sense of the inverted comparison – std::greater(!) – they still remain correct (a greater value in this specific context counts as less from point of view of the two bound-finding algorithms), thus the inverted minimum/maximum values as well. For the same reason/in the same sense – and as using the reverse iterators of std::vector – we can iterate from 'lower' to 'upper' just normally.