Interfacing std compatibility to opaque data with external evaluation dispatch

Question

I am receiving managed data in a low level { void * data; uint stride, count; } format. I can read, write and swap data items, but not to add or remove / resize / reallocate. There's enough information to iterate and random access, but no type info for dereferencing. All opaque items can be mem copied and moved trivially.

Is it possible in modern C++ to facilitate std compatibility for such a data format, omitting the dereferencing interface, and delegating the evaluation to an external context? Something like:

std::sort(OpaqueFirst, OpaqueLast, [](Opaque a, Opaque b){ return handle(a, b); });

Answer 1

The basic idea is to create a type that refers to one of your subarrays and define swap to actually swap their contents:

struct buffer {std::span<std::byte> s;};  // but see below

void swap(const buffer &a,const buffer &b) {
  assert(a.s.size()==b.s.size());
  auto i=b.s.begin();
  for(auto &x : a.s) std::swap(x,*i++);
}

Then we merely have to create a lazy range of such objects, which is easy with std::views::transform wrapped around std::views::iota, and write the trivial comparator from the question:

struct array { void * data; uint stride, count; };

void sort(const array &a,bool lt(const void*,const void*)) {
  std::ranges::sort
    (std::views::transform
     (std::views::iota(uint(),a.count),
      [&](uint i)
      {return buffer{{static_cast<std::byte*>(a.data)+a.stride*i,a.stride}};}),
     [&](const buffer &x,const buffer &y) {return lt(x.s.data(),y.s.data());});
}

Unfortunately, sort demands to be able to move range elements into temporary variables, not just swap them. That requires a rather more complicated wrapper type that can actually own the data temporarily, which in turn requires dynamic allocation since array::stride isn't a constant:

struct buffer {
  std::unique_ptr<std::byte[]> u;
  std::span<std::byte> s;

  buffer(std::span<std::byte> s) : s(s) {}
  buffer(buffer &&b) noexcept {
    if(b.u) u=std::move(b.u);
    else {
      u=std::make_unique<std::byte[]>(b.s.size());
      std::ranges::copy(b.s,u.get());
      s={u.get(),b.s.size()};
    }
  }

  void operator=(const buffer &b) const noexcept;
  buffer& operator=(const buffer &b) noexcept {
    assert(s.size()==b.s.size());
    std::ranges::copy(b.s,s.begin());
    return *this;
  }
};

Retaining our custom swap avoids using such allocations for every element swap, so the performance isn't terrible. The unimplemented operator=(…) const is necessary to convince the library that buffer is a proxy type that should support sorting via prvalues.

A complete example with the full buffer type exists on Compiler Explorer.