• it contains another object, of any of the types specified in its parameter list. templates can generate a lot of compile time type information, code and data, but a thing they can't create is new names for things. variant can't, therefore, contain a union, because we'd have to create a union field for each of the types, and fields have to be named, and metaprogramming can't name things. so, ironically, the standard discriminated union container is not, in fact, a discriminated union (unlike say, array which is a wrapper for a C array, vector which is a wrapper for a dynamically sized C array, string, etc.). what we need, instead, is a blob (like say, a char array) of the appropriate size and alignment to contain any of the possible types. type_traits includes just such a blob type, aligned_union. pity because of all the things variant requires, this was the only one I already knew how to write
  
• as a discriminated union, it contains a discriminant. this will simply be a field of type size_t that identifies which of the possible types is currently active
  
• default-constructibility is not a requirement (I won't implement it), but destructibility is. variant's destructor, like many other of its methods, needs to be polymorphic: depending on what type it currently contains, it must call the appropriate destructor. this is a bitch and a half to implement, but at least we'll only have to do it once and reuse it everywhere. we need a generic, internal static (non-instance) method, that we'll call destruct, which calls the destructor of an arbitrary object passed as its argument (yes, this is legal. and yes, it's unsafe). we then need a method, that we'll call visit, that takes a reference to a function-like object as its sole argument, that we'll call visitor. the visitor must have an overloaded call operator that can take all the possible types the variant could contain. you'd think you could just pass the generic destruct method, but you can't: unspecialized template functions are not things that exist, they are far too abstract to be passed around as values. not that an overloaded function is much better: an overloaded function, without some information to pick a specific overload, is a very abstract entity that can't be passed as an argument to visit, either. what's both generic and concrete enough, tough, is a generic lambda:
  

  C++ code:

  // I decided to call mine either, instead of variant
  ~either()
  {
  	visit([](auto&& value){
  		// no need to use forward, for once
  		destruct(value);
  	});
  }
  

  destruct is trivial and I won't discuss it. visit is, hoo boy. visit is first and foremost a runtime dispatcher: it switches on the union discriminator, and calls the appropriate overload of the visitor. another thing templates can't do (at least not trivially) is generating switch statements. you can't make arrays of lambdas, either, for stupid reasons, so we'll have to make an array of function pointers... that actually point to stateless lambdas. barf. elements of arrays all have the same type, so our stateless lambdas will have a prototype like void(Visitor&& v, void *raw_value); internally, they'll each contain a cast of raw_value to the appropriate type, and a call to the visitor. each of these little dispatchers will be generated by a generic factory method like this:
  

  C++ code:

  // VoidT instead of plain void so that const void can be used for const methods
  template<class Visitor, class T, class VoidT>
  static auto make_dispatcher() -> void(*)(Visitor&&, VoidT *)
  {
  	return [](Visitor&& v, VoidT *raw_object) -> void
  	{
  		std::forward<Visitor>(v)(*static_cast<T *>(raw_object));
  	};
  }
  

  we put all these little dispatchers in an array, select the dispatcher indexed by the current value of the discriminator, and we call it passing it the visitor, through forwarding, and a raw pointer to our internal aligned_union. the cast in the dispatcher "doesn't do anything" (not 100% correct), it just changes the type of the argument to select the right overload/specialization of the visitor. and yes, given N possible types of the variant and M possible visitor types, this will generate M tables of N pointers. they may be inlined, they may be not, who knows. but the visit method, once you dehumanize yourself and face to runtime polymorphism, isn't that hard, conceptually
  
• ... what's a little harder is giving visit a meaningful return type instead of void! luckily, C++ has the basic block for this as the common_type metafunction. we have to simulate calling all possible overloads of the visitor: metafunction result_of resolves a single overload, we just have to apply it to the list of the variant's possible types to map them to a list of visitor return types. then we reduce the list of return types with common_type:
  

  C++ code:

  template<class Visitor>
  auto visit(Visitor&& v) -> std::common_type_t<std::result_of_t<Visitor(Types)>...>
  { // ...
  

  as usual with c++ metaprogramming, easy, readable code like this is almost guaranteed to be subtly wrong. we'll see
  what does "common type" mean anyway? it's defined as the type of a ternary conditional operator expression. in C, the two branches of the ternary operator can have completely different types, which is scary and enables horrible hacks. c++ is much more restrictive and will only let you use different types if they're related somehow, eg. if the true branch evaluates to a long and the false to an int, the expression evaluates to a long. basically it's as if visit was a big chain of ternary conditionals: discriminator == 0 ? visit(type_0) : discriminator == 1 ? visit(type_1) etc.
  
• a variant can be copied from another variant of the same kind if and only if all types it can contain are copyable. the standard library provides metafunction is_copy_constructible to check whether a type is copy constructible. in c++17 we'll check whether a variant can be copied like this: (... && is_copy_constructible<Types>::value...) - this calls is_copy_constructible on each type in Types, maps the list of types to a list of booleans, and then reduces to a single boolean by folding the list two-by-two with the logical and operator. c++14 can map, but it can't reduce, so we'll need a function like this:
  

  C++ code:

  template<class HeadT>
  constexpr auto&& fold_and(HeadT&& head)
  {
  	return std::forward<HeadT>(head);
  }
  
  template<class HeadT, class... TailT>
  constexpr auto fold_and(HeadT&& head, TailT&&... tail)
  {
  	return std::forward<HeadT>(head) && fold_and(std::forward<TailT>(tail)...);
  }
  

  (it can't be simply called and because it's a reserved word, an alternate spelling of &&). thus the existence of the copy constructor will be guarded with enable_if_t<fold_and(is_copy_constructible<Types>::value...), /*etc.*/>. enable_if_t is a disgusting loving hack and it's a disgrace that the language has to resort to hacks of its overload resolution algorithm to perform pattern matching, instead of using a switch-like syntax
  the body of the constructor will be based, like the destructor, on the visit method. we'll use placement new to build a copy of the current value of the variant to be copied in-place, in our internal aligned_variant
  

  C++ code:

  // the enable_if_t horror has been omitted for simplicity (and piety)
  either(const either& other): m_index(other.m_index)
  {
  	other.visit([this](auto&& other_value) {
  		using value_type = std::remove_reference_t<decltype(other)>;
  		new(&m_storage) value_type(other_value);
  	});
  }
  

  reminder that placement new is horribly unsafe (and really hard to find in a code audit!)
  
• same for the move constructor, except using is_move_constructible and invoking the move constructor(s)
  

hackbunny fucked around with this message at 01:50 on Dec 1, 2016