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.
Add a comment
|
2 Answers
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
5 Comments
Aconcagua
As is, violates the requirement of 'not allocating any memory' – you'd some kind of ignoring insertion iterator instead of the
std::back_inserter for the second vector.
Quimby
@Aconcagua Fair enough, I mean it is just an example, OP did not specify where to store the transformed result.
Aconcagua
Not storing at all – wanting just to iterate over
std::for_each is the way to go. OP apparently just stumbled over std::transform (-> 'I have found'), but that's not the right one here ;)Quimby
@Aconcagua That is possible, we won't know until OP says more.
Aconcagua
Hm... Not wanting to store the result anywhere is expressed clearly and explicitly enough, I'd say ('I want to [...] without [...] allocating any memory'). Absolutely wanting to use
std::transform? I'd have considered the uncertainty about alike – but if indeed not, then we might revert the vector in place (don't think this can be done with std::transform at all, however, though there's std::reverse then) – or we need a standard iterator ignoring the data received or write custom one on our own if need be...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.
1 Comment
Aconcagua
Side note: If having to apply lambdas anyway, then classic loops (yes, you explicitly excluded…) still can yield simpler code, though admitted, in case of first variant (corresponding to the example using
std::reverse_iterator) care has to be taken a bit on correctly iterating downwards (special case of lb marking the begin, as one cannot decrement it further then): while(ub-- != lb) { use *ub } or, if yet needing the original upper bound: for(auto i = ub; i-- != lb) { use *i } analogously to down-counting unsigned integrals: for(unsigned i = 4; i-- != 0;) { i == 3,2,1,0 }.