C++: boost range iterator pointing to wrong element

Question

I ran into a strange problem. 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, when I use filtered | reversed then 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;
}

Answer 1

This is a subtle issue. The point here is that after you modify the element pointed to by fr_it2, you also implicitly modify fr_it1 because fr is a lazy view on the original range. This means that the transformed filter needs to be recomputed. This is a very non-intuitive property, because for eager STL ranges, modifications through iterators don't modify the iterators themselves, but for lazy ranges this is no longer true!

In fact, if you print the entire fr and rf ranges using "fresh" iterators, you will see that their contents are in fact the same.

fr_it2->first = false;
for (auto e : fr) std::cout << e.first << e.second << ";"; // prints 13;11
...
rf_it2->first = false;
for (auto e : rf) std::cout << e.first << e.second << ";"; // prints 13;11

Live Example 1. So in fact the middle element is indeed deleted!

I think you should not modify elements through iterators into the adapated range, but rather through iterators into your primary container, like this:

auto fr_it1 = container.begin();
...
auto rf_it1 = container_cpy.begin();

Live Example 2. If you do that, you get consistent results that show "0 2" for both approaches.