Implementing a variant type from scratch in C++

{41 Comments}

When programming in C++ we sometimes need heterogeneous containers that can hold more than one type of value (though not more than one at the same time). If our container needs only contain basic types and Plain Old Data Structures, the solution is simple:

union simple_variant_1 {
   int as_integer;
   bool as_bool;
   float as_float
}

If we want to know which type is stored inside, we can make a tagged union, something along the lines of:

struct simple_variant_2 {
   enum {t_int, t_bool, t_float} type_id;
   union {
      int as_integer;
      bool as_bool;
      float as_float
   }
}

From the efficiency standpoint, this is probably almost an optimal solution. An union will only consume as much space as the largest of its member types. If we try to access the as_float member variable when the actual value stored is int, we will see implementation-dependent gibberish values but that’s OK because we know we are accessing the wring type. Likewise, basic types do not need to be initialized or finalized – they can safely contain gibberish and after we are done using them, they don’t need to do free memory, clean up global state etc.

The problem of course arises, when we want to use “smart” objects, such as std::string, std::vector, … in our union. These types implement custom constructors, copy and move operators, destructors, … The internal structure of std::string, for example, contains a pointer to the string data. If this structure is not properly initialized, it will point to a random location in memory, causing a segmentation fault the first time we access it. If it is not finalized, the memory that it allocated will not be freed thus causing memory leaks.

This is exactly the reason why non-basic types were disallowed in C++ unions. When the union is created, there is simply no means of knowing which of its members should be initialized and when it goes out of scope, the compiler cannot know on which type to perform the destructor. In C++11, the rules have been relaxed, but this requires us to take the initializing/finalizing part into our own hands.

This is how a variant type implementation can look like. We use the rarely-used placement new syntax that allows us to decouple the memory acquisition and object initialization that the new operator provides, by performing only the initialization part on a memory that we already have. In the same manner, we have to manually call the destructor, because free also attempts to deallocate memory.

struct variant {
   enum variant_type {t_int, t_string};
   variant_type type_;
   union {
      int as_integer;
      string as_string;
   };
   variant(variant_type type) : type_(type) {
       if (type == t_string)
           new (&as_string) string();
       else
           new (&as_integer) int();
   }
   ~variant() {
       if (type_ == t_string)
           as_string.~string();
       else
           as_integer.~int();
   }
};

Of course in the above example, we notice that new (&int) as_integer and as_integer.~int() are completely redundant, because integers do not need neither initialization nor finalization, so their constructors and destructors are NOP. This is included for consistency once we get to the point of using templates for generic variant types.

Note: In fact the above code does not even compile on GCC 4.8 and Clang 3.4, but when we use templates to refer to int with a generic template parameter, everything works as expected.

The above code works just well but this approach does not lend itself to implement generic templated types. What we would like is something, that can be used like this:

variant<int, float, string> var;
var.as<string>() = "Hello world!";
cout << var.as<string>(); // Prints Hello World
var.as<int>() = 42;
cout << var.as<int>(); // Prints 42
var.as<float>() = 3.14;
cout << var.as<float>(); // Prints 3.14

In the following section we will build the fully-templated variant type from scratch.

Basic construction

We begin the construction by evaluating the basic layout of our variant type. The approach with unions works well, when we have a hard-coded set of types to choose from, but not so much when we have a templated-type.

We start by setting the basic layout to something like this:

struct variant {
   type type_id;
   char data[enough];
}

This of course raises the question of “How much is enough?”. Since we need every object to fit into the container, it must be at least as big as the largest of the member types.
This is the time to introduce a helper object and some variadic template magic:

template<typename F, typename... Ts>
struct variant_helper {
  static const size_t size = 
    sizeof(F) > variant_helper<Ts...>::size ? sizeof(F) : variant_helper<Ts...>::size;
};

template<typename F>
struct variant_helper<F>  {
	static const size_t size = sizeof(F);
};

We will use the helper object for everything that will require a template specialization for the case of one single member type so as to avoid the code duplication in the main variant class.

This allows us to define:

template<size_t size>
class raw_data { char data[size]; };

template<typename... Ts>
struct variant {
  typedef variant_helper<Ts...> helper;

  type type_id;
  raw_data<helper::size> data;
}

We use the wrapper class raw_data to work around the awkwardness and inconsistency of C-style arrays. This also allows us to easily change the definition if we are programming for a platform where say, sizeof(char) != 1.

Edit (10/11/2013): as some have pointed out, this implementation of raw_data will lead to alignment issues on certain platforms, which can be alleviated by declaring the container type a union of all the variant member types. C++11 provides a very nice container type that works with variadic templates, that we can directly use in this code without any other changes. We can also use aligned_storage. The full source code has been updated.

Type identification

We need a way to create a mapping between member types and values that will be stored in the type_id variable. We will use C++’s very handy RTTI utilities. This requires that the program be compiled with RTTI data and in theory it would be possible to implement this without using it but we would have to manually create type traits for every type that we would like to use, like this:

template<typename T> struct type_traits;
template<> struct type_traits<int> { static const size_t id = 0; };
template<> struct type_traits<string> { static const size_t id = 1; };
template<> struct type_traits<float> { static const size_t id = 2; };
/* ... */

This is useful in some cases, for example if we want to have precise control over the representation of the stored type ID, but very cumbersome when writing a general-purpose container. If we take a look at the std::type_info, we see that typeid(T).hash_code() is guaranteed to return a unique size_t-typed value for every different type, making it ideal for our purposes.

It is also possible to have the types identified sequentially with some template magic, but we would like to have global type IDs, to allow for compatibility between the variant type instantiated with different sets of member types in a possible future expansion.

Destructor

We will now look at the implementation of the destructor. The destructor has to go through every member type and check if it’s ID matches the ID stored in the object. If this is the case, it has to cast the data to this member type and invoke its destructor.
We create an external routine called destroy in the helper class, so that we don’t have to specialize the main template:

template<typename F, typename... Ts>
struct variant_helper {
  /* ... */
  inline static void destroy(size_t id, void * data) 
  {
    if (id == typeid(F).hash_code())
      reinterpret_cast<F*>(data)->~F();
    else
      variant_helper<Ts...>::destroy(id, data);
  }
  /* ... */
};

template<typename F>
struct variant_helper<F>  {
  /* ... */
  inline static void destroy(size_t id, void * data) 
  {
    if (id == typeid(F).hash_code())
      reinterpret_cast<F*>(data)->~F();		
  }
  /* ... */
};

template<typename... Ts>
struct variant {
private:
  typedef variant_helper<Ts...> helper;

  size_t type_id;
  raw_data<helper::size> data;
public:	
  /* ... */
  ~variant() { helper::destroy(type_id, &data); }
  /* ... */
};

Initialization of objects

Contrary to Boost.Variant’s Never-Empty guarantee, our variant type will allow the uninitialized state – the “empty container” – because it greatly simplifies matters. Ergo, we need only make the default constructor:

template<typename... Ts>
struct variant {
  static inline size_t invalid_type() {
    return typeid(void).hash_code();
  }
  /* ... */
  variant() : type_id(invalid_type()) {	}
};

Despite what we outlined in the introduction, we will have two functions to access the member types – set() and get().
set() will perfectly forward all of its parameters directly to T‘s constructor, whereas get() will throw an error if we try to access the type that is not currently contained within.

template<typename Ts>
struct variant {
  /* ... */
  template<typename T, typename... Args>
  void variant::set(Args&&... args)
  {
    // We must first destroy what is currently contained within
    helper::destroy(type_id, &data);		

    new (&data) T(std::forward<Args>(args)...);
    type_id = typeid(T).hash_code();
  }
 

  template<typename T>
  T& get()
  {
    if (type_id == typeid(T).hash_code())
      return *reinterpret_cast<T*>(&data);
    else
      throw std::bad_cast();
  } 	
  /* ... */
}

Copy and move semantics

At this point, the variant type is already usable, but its functionality is severely limited since it does not implement move/copy semantics, so we cannot use it in STL containers. Actually, it is worse. The implicitely defined copy constructor will just copy the contents of data, so when both copies fall out of scope, the object therein contained will be finalized twice, which will probably lead to a crash. It is therefore imperative to either implement custom constructors/operators or mark the object as non-copyable/non-moveable.

The move constructor is very simple, since we only need to steal the resources and invalidate the old instance:

variant(variant<Ts...>&& old) : type_id(old.type_id), data(old.data)
{
  old.type_id = invalid_type();
} 

The copy constructor involves some more work, since it has to invoke the suitable copy constructor of the member type of the object contained in the original container.

template<typename F, typename... Ts>
struct variant_helper {
  /* ... */
  inline static void copy(size_t old_t, const void * old_v, void * new_v)
  {
    if (old_t == typeid(F).hash_code())
      new (new_v) F(*reinterpret_cast<const F*>(old_v));
    else
      variant_helper<Ts...>::copy(old_t, old_v, new_v);		
  }
};

template<typename F>
struct variant_helper<F>  {
  /* ... */
  inline static void copy(size_t old_t, const void * old_v, void * new_v)
  {
    if (old_t == typeid(F).hash_code())
      new (new_v) F(*reinterpret_cast<const F*>(old_v));
  }
};

struct variant {
  /* ... */
  variant(const variant<Ts...>& old) : type_id(old.type_id)
  {
    // We need to do a "deep" copy, that is - invoke the copy constructor of the contained type.
    helper::copy(old.type_id, &old.data, &data);
  }
  ...
}

The last thing we need are the corresponding operator= implementations, everything as standard and some helper functions:

variant<Ts...>& operator= (variant<Ts...>&& old)
{
  // We steal the data and invalidate the old value
  data = old.data;
  old.type_id = invalid_type();
	
  return *this;
}

variant<Ts...>& operator= (variant<Ts...> old)
{
  // Note the call-by-value above
  std::swap(data, old.data);
  std::swap(type_id, old.type_id);
		
  return *this;
}	

// ----------------------------------------- //

template<typename T>
void is() {
  return (type_id == typeid(T).hash_code());
}

void valid() {
  return (type_id != invalid_type());
}

Conclusion

This implementation does not use dynamic memory management/heap storage, so it should be quite efficient. It’s goal is to be simple to understand but may not be so robust as heavy-duty implementations, such as Boost.Variant. It uses fancy C++11 features, so it will probably not work on older compilers The full source code is available here.

41 Comments…

 Share your views
  1. This doesn’t take into account alignment. You should be using std::aligned_storage in place of raw_data.

  2. There are alignment issues. char buffer[size]; for placement new of T is inadequate. This is why we you see code only using placement new of T onto std::aligned_storage which has the right alignment for T. Look up std::aligned_storage (added in C++11), or boost::aligned_storage for more information.

  3. Your move constructor is not proper. Consider for example a type T that is a class that contains pointers to its other member elements.
    You will have to call the object’s move constructor instead of just copying raw data. If you simply copy the raw data, your now relocated object will contain invalid pointers.

    This goes for the move-assign, copy-construct and copy-assign methods as well.

    • Tibor Djurica Potpara October 13, 2013 at 19:32

      I updated the code to use proper move semantics, though this comes with an overhead, since it is much more effective to just copy the data. I wonder what is the actual occurrence of types with absolute pointers to their members.

      • Actually, there’s no reason why a move constructor in generic case would not be as fast as a memcpy (other than a suboptimal compiler that insists on e.g. copying field by field)…

        • Tibor Djurica Potpara October 14, 2013 at 16:27

          It has to perform the move constructor of the type stored within. To do so, it has to do at least one extra comparison, but yeah, I don’t think that this is a problem either. Variant types are just not without tradeoffs.

  4. Alessandro Vergani October 15, 2013 at 12:42

    In the article, the move operator= is missing the setting of the type_id member.

  5. I blog often and I genuinely thank you for your content.
    This article has really peaked my interest. I am going to
    take a note of your website and keep checking for new information about once per week.

    I subscribed to your RSS feed as well.

  6. Thanks for sharing your info. I really appreciate your efforts and I will
    be waiting for your next write ups thanks once again.

  7. Thanks for one’s marvelous posting! I actually enjoyed reading it, you’re a
    great author.I will ensure that I bookmark your blog and will eventually come back in the
    foreseeable future. I want to encourage that you continue your great work, have a nice morning!

  8. Thanks a bunch for sharing this with all of us you actually recognize what you’re speaking approximately!

    Bookmarked. Kindly also visit my site =).
    We could have a link alternate agreement among us

  9. I am genuinely glad to glance at this weblog posts which
    carries tons of helpful information, thanks for providing these kinds of information.

  10. What’s up, I read your blogs regularly. Your humoristic style is witty, keep doing what you’re doing!

  11. Please let me know if you’re looking for a article writer for your weblog.

    You have some really good articles and I think I would be
    a good asset. If you ever want to take some of the load off,
    I’d love to write some content for your blog in exchange for a link back to mine.
    Please shoot me an e-mail if interested. Kudos!

  12. Hey! I know this is sort of off-topic however I had to ask.

    Does operating a well-established blog such as yours require a massive
    amount work? I’m completely new to running a blog but I do
    write in my diary everyday. I’d like to start a blog so I will
    be able to share my experience and feelings online.

    Please let me know if you have any kind of recommendations or tips for brand new aspiring blog owners.

    Appreciate it!

  13. Hey there just wanted to give you a brief heads up and let you know a few
    of the pictures aren’t loading properly. I’m not sure why but I think its a linking
    issue. I’ve tried it in two different internet browsers and both show the same outcome.

  14. What’s Happening i am new to this, I stumbled upon this
    I’ve discovered It absolutely useful and it has aided me out loads.
    I’m hoping to give a contribution & help other customers like its aided
    me. Good job.

  15. Do you mind if I quote a few of your articles as long as I
    provide credit and sources back to your site? My blog site
    is in the very same area of interest as yours and my users
    would truly benefit from a lot of the information you
    present here. Please let me know if this ok with you.
    Many thanks!

  16. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make
    your point. You clearly know what youre talking about,
    why waste your intelligence on just posting videos to your weblog when you could be
    giving us something enlightening to read?

  17. If you wish for to improve your know-how just keep visiting this web page and be updated
    with the most up-to-date gossip posted here.

  18. I love these snow plus winter picture Victorian Christmas cards, not simply because I envy the particular snow on the floor.

  19. Did you love watching American Pie? Well, you will also love these
    types of similar movies that are such as American Quiche.
    Be prepared for a lot more laughing!

  20. Hello friends, its fantastic post concerning educationand fully explained, keep it
    uup all the time.

  21. Every weekend i used to go to see this web page, for the reason that i want enjoyment, for the reason that this this website conations truly fastidious funny material too.

  22. obviously like your website however you have to take
    a look at the spelling on several of your posts.
    A number of them are rife with spelling issues and I in finding it very troublesome to tell the truth on the other
    hand I’ll surely come back again.

  23. It enables you to install the 3rd-party programs. First, Mexican Jumping Beans are not beans
    at all. Be certain to adhere to the instructions precisely as they are offered.
    It might be that you have now brand name new 32GB iPod
    touch.

  24. I know this website provides quality based articles or reviews
    and extra material, is there any other web page which
    presents these information in quality?

  25. Greetings, There’s no doubt that your web site could possibly be having internet browser compatibility issues.
    When I take a look at your website in Safari, it looks fine however
    when opening in IE, it’s got some overlapping issues.
    I simply wanted to give you a quick heads up! Besides that, fantastic
    site!

  26. Hey there! I’m at work surfing around your blog from my new iphone 3gs!
    Just wanted to say I love reading your blog and look forward to all your posts!
    Keep up the superb work!

  27. HD Wallpapers Blog Provides High Quality in broad screen Comics HD
    Wall papers. We have chosen the list associated with best top 12
    Comics Pictures.

  28. Hi just wanted to give you a brief heads up and let you know a few of the images aren’t
    loading correctly. I’m not sure why but I think its a linking issue.
    I’ve tried it in two different internet browsers and both show the same outcome.

  29. I must thank you for the efforts you’ve put in writing this website.

    I’m hoping to see the same high-grade content by you in the future as well.
    In fact, your creative writing abilities has motivated me to get my own, personal blog now ;
    )

  30. Good day! I could have sworn I’ve been to this blog before but after going
    through many of the posts I realized it’s new to me.

    Anyways, I’m definitely delighted I found it and
    I’ll be book-marking it and checking back regularly!

  31. Greetings from Florida! I’m bored at work so I decided to check out your blog on my iphone during lunch break.
    I enjoy the info you provide here and can’t wait to take a look when I get
    home. I’m amazed at how fast your blog loaded
    on my phone .. I’m not even using WIFI, just 3G ..
    Anyways, great blog!

  32. Yes, it’s finally here, the processing technologies from the long term.
    By adding all applications you will love to jailbreak
    your iPad always. You can use tethered or untethered jailbreak techniques.

  33. Hmm is anyone else experiencing problems with the pictures
    on this blog loading? I’m trying to determine if its a problem on my end or
    if it’s the blog. Any suggestions would be greatly appreciated.

  34. Spot on with this write-up, I really believe this amazing
    site needs a lot more attention. I’ll probably be returning to read more,
    thanks for the information!

  35. I am not sure where you’re getting your information,
    but good topic. I needs to spend some time learning
    more or understanding more. Thanks for wonderful info I was looking for this information for my mission.

  36. Have you ever thought about adding a little bit more than just your articles?

    I mean, what you say is valuable and all. But just imagine if you added some great pictures or
    videos to give your posts more, “pop”! Your content is excellent but with
    images and clips, this website could undeniably be one of the very best in its field.
    Awesome blog!

  37. Appreciating the dedication you put into your website and detailed information you provide.
    It’s nice to come across a blog every once in a while that isn’t
    the same out of date rehashed information. Fantastic read!
    I’ve saved your site and I’m adding your RSS feeds to my Google account.

Leave a Comment

Your email address will not be published.