Storing many derived classes without pointers

[Kiryu]

I'm currently writing a Minecraft-like game (Actually cubeworld, but no one knows what that is). Of course the map consists of many different cubes. Because I want to implement some more complex cubes, I'm looking for a way to store them.

The simplest approach would have been to have a basic block class and then some derived classes that implement more complex actions and store extra data.

Example:

class Block {
private:
	vec4 m_color;
	static BlockType m_blockType = BASIC;
public:
	Block(vec4 color){
		m_color = color;
	}

	/* ... */
};

class ComplexBlock : public Block {
private:
	int m_complexity;
	static BlockType m_blockType = COMPLEX_BLOCK;
public:
	ComplexBlock(vec4 color, int complexity) : (color) {
		m_complexity = complexity;
	}

	int getComplexity() const{
		return m_complexity;
	}

	/* ... */
};

Untested, but I hope I got the idea accross!
Now the part that annoys me, storing every block.
The basic approach would be to store a std::vector<Block*>.
But I'd like to avoid pointers as far as possible.

Is there any way to store them without using pointers?
I don't feel comfortable to mess around with pointers of objects that small and that many. It just would be unpractical, in my opinion.

Thanks in advance

~David

EDIT: I already wrote a prototype. Seen here https://youtu.be/BNgzApen7oI
But there I only had one basic Block class with no way of expanding.

[dhayden]

Why not store vector<Block> ?

[TheIdeasMan]

Kiryu wrote:

I don't feel comfortable to mess around with pointers of objects that small and that many. It just would be unpractical, in my opinion.

If you did use std::vector<Block*> you could do polymorphism, which sounds like what you probably want. One can have the correct derived class function be called, no matter what the type of derived class is stored in the container.

http://www.cplusplus.com/doc/tutorial/polymorphism/

Take very careful note of the very first sentence:

Tutorial wrote:

One of the key features of class inheritance is that a pointer to a derived class is type-compatible with a pointer to its base class. Polymorphism is the art of taking advantage of this simple but powerful and versatile feature.

[Kiryu]

Yea, okay. My point wasn't clear. I don't want to use Polymorphism.
At least not by using pointers.

[AbstractionAnon]

I don't want to use Polymorphism.

Then you're missing out on a very powerful feature of C++.

At least not by using pointers.

As TheIdeasMan pointed out, polymorphism only works with pointers.

I suggest you get comfortable with using pointers.

[Kiryu]

Then you're missing out on a very powerful feature of C++.

I don't want to use it in this case.

But okay, I'll again wrap my head around it to figure out a nice implementation.

[mbozzi]

polymorphism only works with pointers

Pedantically, it also works with references. You can pretend to store references in containers by using std::reference_wrapper.
It also works with std::unique_ptr. A container of unique_ptr often avoids the memory management problem that containers of raw pointers pose; the container takes ownership of each element.

You can also go the generic route - that is, using simple duck-typing or the Curiously Recurring Template Pattern at your discretion, e.g.:

# include <iostream>

struct GrassBlock { 
  std::string name() const { return "grass"; }
};

template <typename Block>
std::string get_name(Block const& b) { return b.name(); }

int main() { 
  GrassBlock g{};  
  std::cout << get_name(g) << '\n';
}

http://coliru.stacked-crooked.com/a/c0d6b3bbda988a3e

Edit:
Fixed a typo.

[gunnerfunner]

Max; please don't hate me but getting the following off your program:
|error: 'struct GrassBlock' has no member named 'get_name'|

Perhaps you meant something like this?

# include <iostream>

template <typename Child>
struct Block
{
    void interface()
    {
        static_cast<Child*>(this)->get_name();
    }
};

struct GrassBlock : Block<GrassBlock>
{
  void get_name()const
  {
      std::cout << "grass \n";
  }
};

int main()
{
  GrassBlock g{};
  g.interface();
}

[mbozzi]

@gunnerfunner, thanks again!

In the code I just posted, I meant
std::cout << get_name(g) << '\n';
And some other things which are now fixed.

--

Also, here is the rest of my previous post:

If the goal is to keep a collection of all sorts of blocks, this won't cut it, because every conceivable Block is a different type. You really do need runtime polymorphism, though, by definition: everything that does different things based on the kind of block you have is a sort of polymorphism.

The goal is to be able to write this:

class Block; // ...
struct DirtBlock { std::string name() const { return "dirt"; } };
struct GrassBlock { std::string name() const { return "grass"; } };
int main() {
  GrassBlock g{};
  DirtBlock d{};
  
  Block dirt{d}, grass{g}; // same type! std::vector<Block> is allowed.
  std::cout << dirt.name() << '\n' << grass.name() << '\n';
}

Our proposed class Block should be able to store anything that looks like a Block, without caring what it is. Note that DirtBlock and GrassBlock could both be passed to get_name() as defined above -- that is, they both share a common interface, but they are otherwise completely unrelated. Maybe surprisingly, this is possible without anything too arcane, and it suggests a technique called type erasure.

You can use something like the following Block class to store every unrelated class that (non-intrusively) implements the Block interface, in a similar way that the first snippet indicates.

namespace detail { // internal interface definition
  struct BlockInterface {
    // maybe provide assignment semantics here, or factored out
    virtual ~BlockInterface() = default;
    virtual std::string name() const = 0;
  };
}
class Block: detail::BlockInterface {
  template <typename T> struct RealBlock : detail::BlockInterface {
    template <typename U> explicit RealBlock(U &&u) : t(std::forward<U>(u)) {}
    std::string name() const { return t.name(); }
    T t;
  };
  std::unique_ptr<BlockInterface> b;
public:
  Block() = default;
  // Subtle pitfall: constructor template must be explicit or otherwise not
  // participate in overload resolution in the case that T deduces to a
  // cv-qualified Block, otherwise it will conflict with move and copy
  // constructors.
  template <typename T>
  explicit Block(T &&t) : b{std::make_unique<RealBlock<T>>(t)} {}
  std::string name() const override { return b ? b->name() : "no name"; }
};

If you need to do things with one kind of block that you can't do with others, you have to know exactly what kind of block it is. This is the bottom line, although you can encode the dynamic type in some arbitrary way (or use RTTI) and get it back through downcasting -- that is, by using a switch at runtime.

In the most basic case this involves repeated dynamic_cast or the equivalent, but if needed, type erasure can make the process less exhaustive. You can also provide default implementations of functions which certain Blocks do not implement at all, although this gets a little ugly.

Here's an example of how to do that, about as simple as I can make it right now. Feel free to ask if something's not clear.

#include <iostream>
#include <memory>
#include <type_traits>

struct GrassBlock {
  explicit GrassBlock(int x) : v{x} {}
  std::string name() const { return "grass"; }
  int value() const { return v; }

  int v;
};
struct DirtBlock {
  std::string name() const { return "dirt"; }
};

namespace detail {
// Dummy parameters cause the first overload to be preferred.
// expression SFINAE causes the second overload to be selected if
// substitution fails in the decltype expression
// This allows us to do something based on the return type,
// specifically, to select a default implementation when required
template <typename T>
static auto has_value_impl(int)
    -> decltype(void(std::declval<T>().value()), std::true_type{});
template <typename> static std::false_type has_value_impl(long);

template <typename T> struct has_value : decltype(has_value_impl<T>(0)) {};
template <typename T> constexpr bool has_value_v = has_value<T>::value;

struct BlockInterface { // internal interface
  // maybe provide assignment semantics here, or factored out
  virtual std::string name() const = 0;
  virtual int value() const = 0;
  virtual ~BlockInterface() = default;
};
} // namespace detail
class Block : detail::BlockInterface {
  template <typename T> struct RealBlock : detail::BlockInterface {
    template <typename U> explicit RealBlock(U &&u) : t(std::forward<U>(u)) {}
    std::string name() const override { return t.name(); }

    template <bool UseDefault> 
    std::enable_if_t<!UseDefault, int> value_impl() const {
      return t.value();
    }

    template <bool UseDefault> 
    std::enable_if_t<UseDefault, int> value_impl() const {
      return 42;
    }

    int value() const override { return value_impl<!detail::has_value_v<T>>(); }
    T t;
  };
  std::unique_ptr<BlockInterface> b;

public:
  Block() = default;
  // Subtle pitfall: constructor template must be explicit or otherwise not
  // participate in overload resolution in the case that T deduces to a
  // cv-qualified Block, otherwise it will conflict with move and copy
  // constructors.
  template <typename T>
  explicit Block(T &&t) : b{std::make_unique<RealBlock<T>>(t)} {}
  std::string name() const override { return b ? b->name() : "no name"; }
  int value() const override { return b ? b->value() : 0; }
};

int main() {
  GrassBlock g{2};
  DirtBlock d{};

  Block dirt{d}, grass{g};
  std::cout << dirt.name() << '\n' << grass.name() << '\n';
  std::cout << dirt.value() << '\n' << grass.value() << '\n';
}

Demo:
http://coliru.stacked-crooked.com/a/0031843707793850

[gunnerfunner]

Max: you've sure taken a lot of care in drafting above, I salute you. One thing you've mentioned:

Our proposed class Block should be able to store anything that looks like a Bloc

... now this is quite interesting because there's no any inheritance here, so it seems we can have a version of 'polymorphism'(?) even without inheritance? I'd also be grafeful if you could suggest some references for reading this topic as well. Many thanks,

[JLBorges]

> I don't feel comfortable to mess around with pointers of objects that small and that many.

std::variant http://en.cppreference.com/w/cpp/utility/variant
(C++17: the current versions of GNU or Microsoft compiler)
or boost::variant http://www.boost.org/doc/libs/1_64_0/doc/html/variant.html (older compilers)
is tailor made for holding values of small objects of similar, but different types.

if a variant holds a value of some object type T, the object representation of T is allocated directly within the object representation of the variant itself. Variant is not allowed to allocate additional (dynamic) memory.

#include <iostream>
#include <variant>
#include <vector>

struct block { virtual void display() const = 0 ; } ;

struct block_one : block
{
    virtual void display() const override { std::cout << "block_one::display\n" ; }
    // ...
};

struct block_two : block
{
    virtual void display() const override { std::cout << "block_two::display\n" ; }
    // ...
};

struct displayable_like_block // not related by inheritance
{
    void show() const { std::cout << "displayable_like_block::show\n" ; }
    // ...
};

struct display_it
{
    void operator() ( const block& b ) { b.display() ; }
    void operator() ( const displayable_like_block& d ) { d.show() ; }
};

int main()
{
    using blockish = std::variant< block_one, block_two, displayable_like_block > ; // boost::variant

    std::vector<blockish> blocks { block_one{}, displayable_like_block{}, block_two{}, displayable_like_block{} };
    for( const auto& blk : blocks ) std::visit( display_it{}, blk ) ; // boost::apply_visitor
}

http://coliru.stacked-crooked.com/a/3fe2d8e00ca27602

[Enoizat]

Wow, JLBorges... I’m at a loss for words.
How long did it take you to get to that level?
Have you ever entertained the idea of making some tutorial on Youtube or similar? Rumor has it that somebody’s gained quite a tidy sum by advertising, it they succeed in having followers enough. And I’d be the first (my English permitting).
I think you’ve already got plenty of experience about problem solving in C++ and a lot of topics explanation about which are hard to find on Internet.

Well, thank you for sharing your knowledge, anyway.

[TheIdeasMan]

@Enoizat

Wait until you see some of JLBorges really good code :+)

[Enoizat]

I'm not sure I'm ready for that code :-)

[mbozzi]

So it seems we can have a version of 'polymorphism'(?) even without inheritance?

Speaking technically, yes! C++ supports both static multiple dispatch in the form of the overload resolution mechanism and dynamic single dispatch in the form of virtual functions.

The sort of information hiding used by the class Block above uses the virtual function mechanism between a inner template sub-class and its non-template base class. To hide the real type of the Block we're storing, Block's constructor instantiates that sub-class and keeps a pointer to the base class.
Specifically, there's inheritance between every RealBlock<T> and BlockInterface, and this is where the dynamic polymorphism comes from.

The same idea (of type erasure) is used by std::function and std::any to bind anything callable, or anything at all, respectively.

I'd also be grateful if you could suggest some references about this topic as well

About type erasure (not the Java kind):
https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Type_Erasure#Type_Erasure
http://www.cplusplus.com/articles/oz18T05o/

Last,

To contrast std::variant (which looks superior for OP's purposes) and a type-erasure approach:
Because std::variant is statically-typed, it possible to get the active variant alternative statically: the interface of individual variant alternatives are extensible without touching the variant itself.

The extra indirection implied by type erasure incurs a runtime cost. It is also impossible to retrieve the erased type without RTTI. However, type-erasure eliminates the maintenance demand of adding new variant members, which might be untenable in some cases (e.g. if it was part of a library). OP should prefer variant if possible, unless the additional extensibility is required.

[gunnerfunner]

mbozzi: this is great stuff, thanks once and once again. You've really taken a lot of care into this thread and illuminated us all.
Yes, std::variant looks an interesting approach; one question I have though is if every time a (sub) class is added to the program whether the variant's template union needs to be redefined with the using declaration and then another container with this new union declared.

[JLBorges]

> However, type-erasure eliminates the maintenance demand of adding new variant members,
> which might be untenable in some cases (e.g. if it was part of a library).

1. If all the types that are placed into the variant have same or similarly callable operations, the variant can be extended to include additional types with no library maintenance overhead.

2. If all the types that are placed into the variant may not have similarly callable operations, we can provide for user customisation with indirection via a traits type.

In any case, trying to implement type-erasure, and also meeting the specified requirement of using pure value semantics ("store them without using pointers") is best avoided.

Case 1 (simple):

#include <iostream>
#include <variant>
#include <vector>

template < int N > struct block
{ void display() const { std::cout << "block<" << N << ">::display\n" ; } };

const auto display_it = [] ( const auto& object ) { object.display() ; };

template < int... N > using blockish = std::variant< block<N>... > ;

int main()
{
    {
        std::vector< blockish<0,1,2> > blocks { block<1>{}, block<2>{}, block<0>{} };
        for( const auto& blk : blocks ) std::visit( display_it, blk ) ; // boost::apply_visitor
    }
    std::cout << "-----------------------------------------------------------\n" ;
    {
        std::vector< blockish<0,1,2,4,5> > blocks { block<4>{}, block<1>{}, block<2>{}, block<5>{}, block<0>{} };
        for( const auto& blk : blocks ) std::visit( display_it, blk ) ; // boost::apply_visitor
    }
}

http://coliru.stacked-crooked.com/a/9ec42a3d859b40c4

Case 2 (user-customisable traits):

#include <iostream>
#include <variant>
#include <vector>

struct one { void display() const { std::cout << "one::display\n" ; } };
struct two { void display() const { std::cout << "two::display\n" ; } };

template < typename T > struct do_display
{ void operator() ( const T& object ) const { object.display() ; }; };

struct display_it // display_traits
{
    template < typename T > void operator() ( const T& object ) const
    { do_display<T>{}(object) ; }
};

struct three
{ void show( std::ostream& stm = std::cout ) const { stm << "three::show\n" ; } };

template<> struct do_display<three> // user provided customisation for three
{ void operator() ( const three& object ) const { object.show() ; }; };

int main()
{
    using blockish = std::variant< one, two, three > ;
    std::vector<blockish> blocks { one{}, two{}, three{} };
    for( const auto& blk : blocks ) std::visit( display_it{}, blk ) ; 
}

http://coliru.stacked-crooked.com/a/22f3b0c9a1425763

[Kiryu]

Sorry for the late answer, I kinda forgot about it because of frustration. I'm the kinda guy, if something does not work exactly how I want it, I don't want to have anything to do with it anymore .. bad habit!

Thanks for all you answers, I'm sure some of them took a lot of time, but the proposed solutions are all way to complicated and go too far into the unknown of my understanding. I learned in the past that I shouldn't work with anything I don't fully understand, and the Block class in my engine is used very often, so I'd like to have a flawless system I fully understand.

Maybe in the future, when my skill has increased, I'll look back at this thread!

With much thanks

David