title: Sort custom container (implemented as one integer)
body: <p>I have a class which holds small numbers inside bigger integer variable. It works fine and fast and looks like this:</p>
  
  <pre><code>template
  class Container&lt;IntegerT&gt;
    static int bitsPerElement;
    IntegerT data; // [0000] [0000] [0000] [0000] up to 128bits(or maybe more)
    int size;
  </code></pre>
  
  <p>iterator as value_type return "reference" to container element:</p>
  
  <pre><code>Container::iterator
    DataRef operator*()
  
  DataRef
    Container* parent;
    int position;
  </code></pre>
  
  <p>But i got a problem of unavailability of std::sort, because it have no clue how to actually swap elements of this container (direct swapping of DataRefs is obviously pointless).</p>
  
  <p>Is there any magic way to make std::sort work with it (actually to force it use custom swap function)? </p>
  
  <p>Or is there decent alternative to std::sort which can handle this situation? (storing DataRefs in array is not considered as a solution)</p>
  
  <p>Which is the fastest way to sort this data structure? </p>
  
  <pre><code>#ifndef INTSTORAGE_H
  #define INTSTORAGE_H
  
  #include &lt;algorithm&gt;
  
  template&lt;class T&gt; class IntStorage;
  
  template&lt;class T&gt;
  class DataRef
  {
    public:
      DataRef(IntStorage&lt;T&gt;* parent, int position) : m_parent(parent), m_position(position) {}
      DataRef(DataRef&amp;&amp; o) = default;
      DataRef(const DataRef&amp; o) = default;
  
      int value() const {return m_parent-&gt;value(m_position);}
      void setValue(int value) {m_parent-&gt;setValue(m_position, value);}
  
      DataRef&amp; operator=(const DataRef&amp; c)
      { setValue(c.value()); return *this; }
      DataRef&amp; operator=(const DataRef&amp;&amp; c)
      { setValue(c.value()); return *this; }
      bool operator&lt;(const DataRef&amp; o) const
      { return value() &lt;  o.value(); }
  
      IntStorage&lt;T&gt;* m_parent;
      int m_position;
  };
  
  template&lt;class T&gt;
  class IntStorage
  {
      template&lt;typename&gt; friend class IntStorage;
      template&lt;typename&gt; friend class DataRef;
    public:
      void append(int value)
      {
        data |= (static_cast&lt;T&gt;(value) &lt;&lt; (s_bitsPerItem * size));
        ++size;
      }
  
      void setValue(int index, T value)
      {
        data = ((~(s_mask &lt;&lt; (s_bitsPerItem * index))) &amp; data)
               | (static_cast&lt;T&gt;(value) &lt;&lt; (s_bitsPerItem * index));
      }
      T value(int i) const { return (data &amp; s_mask &lt;&lt; (i * s_bitsPerItem)) &gt;&gt; (i * s_bitsPerItem); }
  
      class iterator
      {
        public:
          using iterator_category = std::random_access_iterator_tag;
          using difference_type = int;
          using value_type = DataRef&lt;T&gt;;
          using pointer = DataRef&lt;T&gt;*;
          using reference = DataRef&lt;T&gt;&amp;;
  
          iterator(IntStorage&lt;T&gt;* parent, int pos = 0) : ref(parent, pos) {}
          inline bool operator==(const iterator&amp; o) const { return ref.m_parent == o.ref.m_parent &amp;&amp; ref.m_position == o.ref.m_position;}
          inline bool operator!=(const iterator&amp; o) const { return !operator==(o);}
          inline const DataRef&lt;T&gt;&amp; operator*() const {  return ref;}
          inline DataRef&lt;T&gt;&amp; operator*() { return ref; }
          inline iterator&amp; operator++() { ++ref.m_position; return *this; }
          inline iterator&amp; operator--() { --ref.m_position; return *this; }
          inline int operator-(const iterator&amp; o) const {  return ref.m_position - o.ref.m_position; }
          inline iterator operator+(int diff) const {  return iterator(ref.m_parent, ref.m_position + diff); }
          inline iterator operator-(int diff) const {  return iterator(ref.m_parent, ref.m_position - diff); }
          inline bool operator&lt;(const iterator&amp; o) const {  return ref.m_position &lt; o.ref.m_position; }
          DataRef&lt;T&gt; ref;
      };
      friend class iterator;
  
      iterator begin()  {return iterator(this, 0);}
      iterator end()    {return iterator(this, size);}
      iterator cbegin() {return iterator(this, 0);}
      iterator cend()   {return iterator(this, size);}
  
      static constexpr T s_mask = 0b111111;
      static constexpr int s_bitsPerItem = 6;
      int size = 0;
      T data = 0;
  };
  
  #endif // INTSTORAGE_H
  </code></pre>