Boost range iterator pointing to wrong element
Hi all, I have a vector<pair<bool, int>> from which I need to read (and possibly write) only the vector elements for which the boolean value of the pair is true. I am using boost range filter and reverse adaptors to do that. However, I noticed that the order of the adaptors, ie whether I use reversed | filtered or filtered | reversed produces different results. In fact, for the latter when I use an iterator to the transformed range to change the boolean value of the pair, then the iterator after the change points to a different vector element. This does not happen when I use reversed | filtered. Below is the code demonstrating the issue. Any ideas as to why this is happening are much appreciated! #include <boost/range/adaptors.hpp> #include <vector> #include <utility> #include <iostream> using namespace boost::adaptors; using container_type = std::vector<std::pair<bool,int>>; struct to_include { bool operator()(const std::pair<bool,int>& x) { return x.first; } }; int main() { container_type container; /* element0: 1, 1 */ /* element1: 1, 2 */ /* element2: 1, 3 */ for(size_t i=0; i!=3; ++i) container.push_back(std::make_pair(true, i+1)); container_type container_cpy = container; /* filter and then reverse */ auto fr = container | filtered(to_include()) | reversed; auto fr_it1 = fr.begin(); auto fr_it2 = std::next(fr_it1); fr_it2->first = false; std::cout << "FILTER AND THEN REVERSE\n"; std::cout << fr_it2->first << " " << fr_it2->second << '\n'; /* prints (1,1) instead of (0,2) */ /* reverse and then filter */ auto rf = container_cpy | reversed | filtered(to_include()); auto rf_it1 = rf.begin(); auto rf_it2 = std::next(rf_it1); rf_it2->first = false; std::cout << "\nREVERSE AND THEN FILTER\n"; std::cout << rf_it2->first << " " << rf_it2->second << '\n'; /* prints (0,2) */ return 0; }
On 9/22/2013 6:37 AM, Quoth Giorgos Sermaidis:
struct to_include { bool operator()(const std::pair<bool,int>& x) { return x.first; } }; [...] /* reverse and then filter */ auto rf = container_cpy | reversed | filtered(to_include()); auto rf_it1 = rf.begin(); auto rf_it2 = std::next(rf_it1); rf_it2->first = false;
This is just a guess, but it strikes me as potentially dodgy to retain iterators to a filtered sequence after modifying the result of the filter predicate on that sequence. (This seems like something that would invalidate iterators, just like certain collection modifications do.) Have you tried re-acquiring the iterators from "rf" or "fr" after assigning to "first", rather than continuing to use them? (You shouldn't need to reconstruct "rf" or "fr" themselves, just the iterators.)
struct to_include { bool operator()(const std::pair<bool,int>& x) { return x.first; } }; [...] /* reverse and then filter */ auto rf = container_cpy | reversed | filtered(to_include()); auto rf_it1 = rf.begin(); auto rf_it2 = std::next(rf_it1); rf_it2->first = false;
This is just a guess, but it strikes me as potentially dodgy to retain iterators to a filtered sequence after modifying the result of the filter predicate on that sequence. (This seems like something that would invalidate iterators, just like certain collection modifications do.)
Gavin is right. Filtered ranges assume that the value of the predicate on sequence elements does not change during the iterator's lifetime. You are breaking that assumption, and so anything can happen. (I can't find any documentation about this assumption, however. We should probably add some.) If you're wondering how the result that you're seeing comes about, it's like this: - reverse_iterator stores an iterator of the underlying range not to the element it is pointing to, but to the next position. This is because there is a past-the-end iterator but not a before-the-begin one, so we need the begin() of the reversed range to store the end() of the underlying range, which, being the past-the-end iterator, is one position ahead of what the begin() of the reversed range is actually pointing to, which is the last actual element) - so reverse_iterator's dereference operator calls prior() on the stored underlying iterator to get the underlying iterator we actually want to dereference. - filter_iterator simply stores an iterator of the underlying type to the element it is pointing to - so filter_iterator's dereference operator just dereferences the underlying iterator. - When the outer range is the reversed range, you dereference the reverse_iterator, which calls prior() on the filter_iterator. - prior() on a filter_iterator walks the range backwards until an element matching the predicate is found. since you've modified the (0, 2) element so it no longer matches the predicate, it skips it and goes on to the (1, 1) element, which is what you rr - When the outer range is the filtered range, you dereference the filter_iterator which just derefernces the underlying reverse_iterator. No calls to the predicate are made, and (0, 2) element is returned. So to sum it up, the difference is referring to the current element of the filtered range in one case, and referring to the next element and calling prior() to get at the current element in the other case. The two are equivalent under the assumption that the predicate's value does not change while you're iterating. Regards, Nate
participants (3)
-
Gavin Lambert -
Giorgos Sermaidis -
Nathan Ridge