title: How to use std::sort with opaque data types efficiently?
body: <p>I'm working on an SDK which defines interfaces like</p>
  
  <pre><code>class FooIter
  {
      // Move to the next foo, return false if there is none.
      virtual bool Move() = 0;
  
      // Return a pointer to the current foo.
      virtual const void* GetFoo() = 0;
  
      // Get the size of a 'foo', which is a fixed-size POD.
      virtual size_t GetFooSize() = 0;
  
      // Get a comparator for foos.
      virtual const FooComparator* GetComparator() = 0;
  };
  
  class FooComparator
  {
      virtual int compare(const void* first, const void* second) const = 0;
  };
  </code></pre>
  
  <p>So basically, a foo is an opaque type that I can treat as a fixed-length binary buffer + and associated ordering function.</p>
  
  <p>Now, I want to sort these foos before passing them back to client code. There may potentially be <strong>many</strong> foos, so I'll have to implement external sorting, but I'd like to use std::sort to sort the initial runs.</p>
  
  <p>I was thinking I would allocate a buffer of size N * FooIter::GetFooSize(), fill it with foos using FooIter, and then sort it with std::sort before writing it to disk.</p>
  
  <p>I can start by writing an iterator class</p>
  
  <pre><code>class FooBufferIter
  {
  public:
      FooBufferIter(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}
  
      FooWrapper operator*() {return FooWrapper(m_fooAddr, m_fooSize);}
  
      FooBufferIter operator++() {return FooBufferIter(m_fooAddr + m_fooSize, m_fooSize);}
  
      // All other needed iterator methods.
  private:
      const void* m_fooAddr;
      int m_fooSize;
  };
  </code></pre>
  
  <p>and a wrapper class for foo memory</p>
  
  <pre><code>class FooWrapper
  {
  public:
      FooWrapper(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}
  
  private:
      const void* m_fooAddr;
      int m_fooSize;
  };
  </code></pre>
  
  <p>My understanding is that std::sort will use std::swap to rearrange the elements in the sequence. My issue is I can't see how to specialize std::swap on FooWrapper to perform the swap efficiently (most importantly, no dynamic allocation). I could swap byte by byte, but that also seems inefficient.</p>
  
  <p>Another way of doing this would be to sort a parallel sequence of pointers into my Foo array, but I don't want to do that, since in practice, the foos will likely be quite small, so the parallel sequence could use just as much memory as the foo sequence, and I want to maximize the number of them I can sort at a time.</p>
  
  <p>There's also good ol' qsort which is probably more suited to this kind of thing, but I'm not sure how to convert the FooComparator object into a function pointer (there may be multiple implementations of FooComparator).</p>
  
  <p>Or is there a better way of going about this? I don't really want to write my own sort implementation, although it probably wouldn't be <em>too</em> hard.</p>