title: (Re)Using std::algorithms with non-standard containers
body: <p>I have a "column" container type:</p>
  
  <pre><code>struct MyColumnType { 
    // Data: Each row represents a member of an object.
    vector&lt;double&gt; a;   // All vectors are guaranteed to have always
    vector&lt;string&gt; b;   // the same length.
    vector&lt;int&gt; c;
  
    void copy(int from_pos, int to_pos); // The column type provides an interface
    void swap(int pos_a, int pos_b);     // for copying, swapping, ...
  
    void push_back();      // And for resizing the container.
    void pop_back();
    void insert(int pos);
    void remove(int pos);
    // The interface can be extended/modified if required
  };
  </code></pre>
  
  <p><strong>Usage:</strong></p>
  
  <pre><code>// If table is a constructed container with elements stored 
  // To acces the members of the object stored at the 4th position:
  table.a[4] = 4.0;
  table.b[4] = "4th";
  table.c[4] = 4;
  </code></pre>
  
  <p><strong>Question:</strong> How can I create a standard-compliant random access iterator (and probably a required proxy reference type) for this kind of container?</p>
  
  <p>I want to be able to use <code>std::algorithms</code> for random access iterators with my type, e.g. <code>sort</code> (note: for sorting the comparison would be provided by an user-defined functor, e.g. a lambda). </p>
  
  <p>In particular the iterator should provide an interface similar to </p>
  
  <pre><code>struct {
    double&amp; a;
    string&amp; b;
    int&amp; c;
  };
  </code></pre>
  
  <p><strong>Note 0:</strong> C++11/C++14 is allowed.</p>
  
  <p><strong>Note 1:</strong> There is an old paper <a href="http://hci.iwr.uni-heidelberg.de/vigra/documents/DataAccessors.ps">http://hci.iwr.uni-heidelberg.de/vigra/documents/DataAccessors.ps</a> where a similar attempt is undertaken. However, I haven't been able to get their approach working with sort. Requirements like defaultConstructible are hard to satisfy using a proxy type approach (why does <code>std::sort</code> require types to be default constructible instead of swappable is beyond my understanding).</p>
  
  <p><strong>Note 2:</strong> I cannot do the following:</p>
  
  <pre><code>struct MyType {
    double a;
    string b;
    int c;
  };
  
  std::vector&lt;MyType&gt; v;
  </code></pre>
  
  <p>and then use <code>std::algorithm</code>. </p>
  
  <p><strong>Motivation:</strong> Performance. A cache-line is usually 64bytes, i.e. 8 doubles. In this simple struct if you iterate over the doubles, you are polluting a cache-line with a string an an int. In other cases, you might get only 1 double transfered per cache-line. That is, you end up using 1/8-th of the memory bandwith available. If you need to iterate over a couple of Gb of doubles, this simple decision improves your application performance by a factor of 6-7x. And no, I cannot give that up.</p>
  
  <p><strong>Bonus:</strong> the answer should be as generic as possible. Think about adding/removing fields to the container type as adding/removing members to a struct. You don't want to change a lot of code every time you add a new member.</p>