title: C++ random access iterators for containers with elements loaded on demand
body: <p>I'm currently working on a small project which requires loading messages from a file. The messages are stored sequentially in the file and files can become huge, so loading the entire file content into memory is unrewarding.</p>
  
  <p>Therefore we decided to implement a <code>FileReader</code> class that is capable of moving to specific elements in  the file quickly and load them on request. Commonly used something along the following lines</p>
  
  <pre><code>SpecificMessage m;
  FileReader fr;
  fr.open("file.bin");
  fr.moveTo(120); // Move to Message #120
  fr.read(&amp;m);    // Try deserializing as SpecificMessage 
  </code></pre>
  
  <p>The FileReader per se works great. Therefore we thought about adding STL compliant iterator support as well: A random access iterator that provides read-only references to specific messages. Used in the following way</p>
  
  <pre><code>for (auto iter = fr.begin&lt;SpecificMessage&gt;(); iter != fr.end&lt;SpecificMessage&gt;(); ++iter) {
    // ...
  }
  </code></pre>
  
  <p>Remark: the above assumes that the file only contains messages of type SpecificMessage. We've been using <code>boost::iterator_facade</code> to simplify the implementation.</p>
  
  <p>Now my <strong>question</strong> boils down to: how to implement the iterator correctly? Since <code>FileReader</code> does not actually hold a sequence of messages internally, but loads them on request. </p>
  
  <p>What we've tried so far:</p>
  
  <p><strong>Storing the message as an iterator member</strong></p>
  
  <p>This approach stores the message in the iterator instance. Which works great for simple use-cases but fails for more complex uses. E.g. <code>std::reverse_iterator</code> has a dereference operation that looks like this</p>
  
  <pre><code> reference operator*() const
   {  // return designated value
     _RanIt _Tmp = current;
     return (*--_Tmp);
   }
  </code></pre>
  
  <p>This breaks our approach as a reference to a message from a temporary iterator is returned.</p>
  
  <p><strong>Making the reference type equal the value type</strong></p>
  
  <p>@DDrmmr in the comments suggested making the reference type equal the value type, so that a copy of the internally stored object is returned. However, I think this is not valid for the reverse iterator which implements the -> operator as</p>
  
  <pre><code>pointer operator-&gt;() const {
    return (&amp;**this);
  }
  </code></pre>
  
  <p>which derefs itself, calls the *operator which then returns a copy of a temporary and finally returns the address of this temporary.</p>
  
  <p><strong>Storing the message externally</strong></p>
  
  <p>Alternatively I though about storing the message externally:</p>
  
  <pre><code>SpecificMessage m;
  auto iter = fr.begin&lt;SpecificMessage&gt;(&amp;m);
  // ...
  </code></pre>
  
  <p>which also seems to be flawed for </p>
  
  <pre><code>auto iter2 = iter + 2
  </code></pre>
  
  <p>which will have both <code>iter2</code> and <code>iter</code> point to the same content.</p>