How to create vector of polymorphic items

[Xcalllibur]

Background Information
- I am consuming an API that gives access to a read-only buffer of floats (const float*)
- I need to break this up into chunks which I do by creating a nonstd::span<const float> initialised with the pointer and the number of elements in the chunk.
- I am using the span-lite implementation of span available from https://github.com/martinmoene/span-lite
- I then wrap this span in a simple structure (used to hold other metadata as well, removed below as it is not important here) as follows:

struct Chunk
{
    explicit Chunk(nonstd::span<const float>& bytes) : bytes(bytes)
    {
    }

public:
    nonstd::span<const float> bytes;
};

I add the resulting structures to a vector, shown by the following code:

const auto chunkCount = 10;
const auto chunkSize = 1024;

const auto* buffer = externalApi.getBufferPointer();
std::vector<Chunk> chunks(chunkCount);
auto offset = 0;

for (auto index = 0; index < chunkCount; ++index, offset += chunkSize)
{
    chunks.emplace_back(&buffer[offset], chunkSize);
}

The above all works and I can use the chunks as expected.

Issue Description
What I want to achieve is to be able to additionally define my own chunks, so:

- Allocate the bytes
- Fill them in as desired
- Add them to the above vector of existing chunks

So the result will be a vector that contains a mix of chunks pointing to data defined by the external API and chunks pointing to data i have created. Since I am allocating the data, it will not be a span<>, but rather an array or similar. My idea is to conceptually have an interface, such as Chunk, that is then subclassed by SpanChunk and ArrayChunk, then added to the vector so that the consumer is not concerned with the actual implementation of the chunks. The interface must satisfy the following constraints:

- Be const iterable (i.e. iterate through the 'bytes' in the chunk). This is important so the chunk can be used with std::transform(), etc
- Be able to index-access the bytes (i.e. const float dataByte = chunk[36])

So far my attempts at implementing such polymorphism has been unsuccessful, though I could achieve the same in C#, Java and other languages I am more familiar with. Can someone guide me in the right direction for how to solve this situation in C++ and perhaps provide some example implementation of the subclasses if this is the right way to solve the problem.

[CodeGoggles]

What is it you don't understand about polymorphic objects?

class Chunk_Class // Parent class
{
	// Basic implementation
protected:

	virtual void Print_Chunk() // this is virtual function
	{
		// has an implementation but can be overridden by a child class
		// if no child class with the same definition exists it will run this code.
	} 
	virtual void Print() = 0; // This is a pure virtual function
	// it has no implementation and specifies all children classes must provide an implementation

};

class Span_Chunk : public Chunk_Class // child class
{
	void Print_Chunk()
	{
		// this is a print chunk function defined in a child class
		// this code will run when you call print chunk from a child object of this type
		// as the parent class only defines it as virtual you do not need a child implementation
		// and if you dont define one it will run the parent implementation.
	}
	void Print()
	{
		// this was defined as a pure virtual class thus it is required to have an implementation.
	}
};

class Array_Chunk : public Chunk_Class // child class
{
	// I decided not to implement a printchunk function so the parent definition runs when called from an object of this type.
	void Print()
	{
		// this was defined as a pure virtual class thus it is required to have an implementation.
	}
};

if you want children to be able to access variables from a parent class but not allow external access to members and functions you can define a protected access specifier like so

class Chunk_Class // Parent class
{
public: // ACCESSIBLE BY EVERYONE

	int varible1;

protected: // ACCESSIBLE BY CHILDREN AND PARENT

	bool varible2;

private: // ONLY PARENT ACCESS

	double varible3;
};

you can add children to a vector like so but they must be pointers to the children as the sizes may vary between a child and parent class object.

Span_Chunk spanObject;
Span_Chunk* spanPtr = &spanObject;
std::vector<Chunk_Class*> chunkVec;

chuckVec.pushback(spanPtr);

Note that you will only be able to access functions defined by the parent class because the vector takes the parent class pointer. That means you would either have to have virtual or pure virtual functions in the parent to access child implementations or cast it to a child type.

[mbozzi]

So the result will be a vector that contains a mix of chunks pointing to data defined by the external API and chunks pointing to data i have created. Since I am allocating the data, it will not be a span<>, but rather an array or similar. My idea is to conceptually have an interface, such as Chunk, that is then subclassed by SpanChunk and ArrayChunk, then added to the vector so that the consumer is not concerned with the actual implementation of the chunks.

Resist the temptation to add more indirection than required. Polymorphism sucks and class hierarchies are complicated.

Instead, store the data you own separately and deal only in spans.

This implies only one indirection, is easy to code, and most importantly, has predictably non-owning semantics. Do not underestimate the complexity involved in mixing owning and non-owning views of data.

[Xcalllibur]

@CodeGoggles Thanks for taking the time to write such a details answer.

What I don't understand about polymorphic objects is how to implement in C++ what I want to achieve. That is, to make the resultant objects iterable and indexable.

So conceptually I want to be able to do this with the final vector of chunks:

for (auto* chunk: chunks)
{
    const std::array<float, chunkSize> results{};

    // Iterate the bytes within the chunk, for example with std::transform()
    std::transform(chunk.cbegin(), chunk.cend(), results.begin(), [position](const float data)
    {
	return data / 2;
    });
}

So the const iterator methods will iterate the underlying bytes of the chunk. If you are familiar with C#, I would do this by having the interface (virtual method here) define a property that returns an IEnumerable<float> that would let me iterate through the underlying bytes.

When I tried to do this in C++ I couldn't work out how to define cbegin()/cend()/etc virtual methods on the base class in such a way that allowed me to have different underlying data structures (e.g. Span vs array) but allowed the consumer to iterate each vector member regardless.

Hopefully I have explained this well enough and this is where I need guidance on the C++ approach to this pattern.

As mentioned above I also need the chunk interface to allow indexing of the underlying bytes too, so that a consumer may loop through the chunks and access specific bytes for example.

[Xcalllibur]

@mbozzi

the complexity involved in mixing owning and non-owning views of data

This is something I have given a lot of thought to and am open to explore this approach in favour of the above.

You make two points in this statement that I am hoping you can clarify further.

store the data you own separately and deal only in spans

1) store the data you own separately - Are you suggesting to allocate the new chunks and store reference to them in a completely new vector? If so, how would I use the chunks in the correct, mixed order?
2) deal only in spans - Are you suggesting to access even the new chunks via spans? Is this so that the access pattern is consistent across all chunks? If the new chunks are stored separately to the span chunks, then why would a consistent access pattern be required?

If you are talking about something completely different would love to hear some further details.

[Xcalllibur]

Seems that what I am looking for is formalised in C++ 20 with the ForwardIterator concept:

https://en.cppreference.com/w/cpp/experimental/ranges/iterator/ForwardIterator

I should note that I am using C++ 17 but conceptually this is what I want to achieve.

Does this mean I should be solving this problem using templates rather than a polymorphic approach?

[mbozzi]

Are you suggesting to allocate the new chunks and store reference to them in a completely new vector?

To my understanding, you've got a set of buffers owned by different architectural subsystems.

When you wish to split those buffers into chunks for further processing, just denote the chunks with span<float const> as you were doing before you introduced the idea of a polymorphic chunk.

Are you suggesting to access even the new chunks via spans? Is this so that the access pattern is consistent across all chunks?

It's for several reasons. In this straightforward design, chunks
1. are trivially easy to define and understand;
2. have constant-time copy and move operations;
3. provide a no-failure exception safety guarantee;
4. require only a single, unavoidable indirection to the buffer; and
5. don't require handling of objects with type pointer-to-chunk & thereby avoid difficulties regarding the identity & lifetime of the pointed-to-chunk.

The last point bears a little more explanation: for runtime polymorphism to be useful, virtual functions must be called through a pointer- or reference-to-base.
chunk* denotes that the chunk is owned by another system;
unique_ptr<chunk> cannot be copied;
shared_ptr<chunk> is an abuse of shared_ptr & a disaster waiting to happen

[mbozzi]

Seems that what I am looking for is formalised in C++ 20 with the ForwardIterator concept

One would hope an iterator over a buffer of floats would be a ContiguousIterator ⊂ ForwardIterator

A plain old float* satisfies both concepts.

[Xcalllibur]

OK just wanted to provide an update for any other C++ beginners trying to solve a similar problem.

I found this video which perfectly answers all my questions:

https://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil

It's a brilliant video and taught me a lot on how to provide polymorphic behaviour but without inheritance and using concepts instead.

Also Richard Hodges used this idiom to implement iterators here:

https://stackoverflow.com/questions/35866041/returning-different-iterators-with-virtual-derived-methods

Also this discussion which educated me that C++ uses duck typing for templating, a fact that I wasn't aware of up until this point, but I can understand the reasoning for now:

https://stackoverflow.com/questions/8764643/is-there-a-standard-c-equivalent-of-ienumerablet-in-c#

I'm very much looking forward to using concepts going forward to make this kind of code easier to write.

[mbozzi]

It's a brilliant video and taught me a lot on how to provide polymorphic behaviour but without inheritance and using concepts instead.

Yes, it's a great talk - even though there is polymorphism: hidden but present. The problems do not go away. Don't forget the talk's title.

Using a forward iterator over a contiguous buffer is a major pessimization in many cases.

Why is a float* not a suitable iterator?

[Xcalllibur]

I am of no illusion that I am an expert here btw - just listening to those who are far more knowledgeable and learning as I go. I'm only a month or so into my C++ journey so feel free to continue educating me if you have the time, I do appreciate it.

Don't forget the talk's title.

The title says that inheritance is the problem, which he does resolve in his implementation quite elegantly I thought.

Why is a float* not a suitable iterator?

There is a slide, one minute in to the video, that states Goal: No raw pointers :) This is advice I see time and time again in what I am reading, so I am trying to not use them. Perhaps if you provide a simplified implementation of the above problem solved using a raw pointer it will be more obvious to me what the advantages are.

[mbozzi]

Goal: No raw pointers :) This is advice I see time and time again in what I am reading, so I am trying to not use them

The problems with raw pointers are best understood in contrast with unique_ptr, which represents the responsibility to release (i.e., ownership of) a pointed-to resource. unique_ptr guarantees that this resource is released exactly once.

Raw pointers cannot provide any such guarantee alone. Therefore the guideline's intent is to discourage the use of raw pointers specifically to represent ownership.

When no ownership transfer is intended, raw pointers are fine. Here is the core guidelines suggesting the same:
https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rr-ptr

Indeed, it's immaterial whether we choose float* or span<float>::iterator. The latter is functionally equivalent to (for these purposes) and quite possibly an alias for float*.

The title says that inheritance is the problem, which he does resolve in his implementation quite elegantly I thought.

Well, the inheritance is nicely hidden - so advantage #5 is retained in exchange for a good amount of developer effort = your employer's money.

Advantages #1-#4 are still lost, even though it's not clear they are necessary sacrifices given the problem description.

#include <span>
#include <vector>

// Some C-style interface in a third-party library
namespace lib
{
  int constexpr buf_sz = 1024; 

  float const* buf() 
  {
    static float internal_buffer[buf_sz];
    return internal_buffer;
  }
}

struct chunk : public std::span<float const>
{ 
  using base_type  = std::span<float const>;
  using base_type::base_type;
};

int main()
{
  std::vector<chunk> chunks; 

  // split the library buffer into chunks
  chunks.emplace_back(lib::buf(), lib::buf_sz);

  // allocate our own buffer
  std::vector<float> buf_a(2048); 

  int constexpr stride = 1024;
  auto start = buf_a.begin();
  auto end   = buf_a.end();

  // split our own buffer into chunks
  for (; start < end; start += stride) 
    chunks.emplace_back(start, std::min(end, start + stride));
}

https://godbolt.org/z/cvTnde