Define struct with minimum size

Question

I want to define a struct, e.g. type, such that sizeof(type) is no less than some value.

Motivation:

I have a vector std::vector<type> and I will remove some elements from it. Also, I have saved the indexes of some elements to other places, thus I want just mark it as not used and reuse it in the future. This leads me to save the next available position as a list in erased positions. As a result, sizeof(type) should be no less than sizeof(size_t) and type should be properly aligned as well.

Possible Solutions:

1. boost::variant<type, size_t>

   This has two problems from my point of view. If I use boost::get<type>, the performance will decrease significantly. If I use boost::apply_visitor, the syntax would be weird and the performance also decreases according to my profile.

2. union{type t; size_t s;}

   This of course works except for two shortfalls. Firstly, the syntax to refer the member of type would be more messy. Secondly, I have to define constructor, copy constructor, etc. for this union.

3. Extend type by char[sizeof(size_t) - sizeof(type)]

   This almost fulfills my requirements. However, this risks of zero length array which is not supported by the c++ standard and possibly wrong alignment.

Since I won't use type as size_t often, I'd like to just ensure I can use reinterpret_cast<size_t> when needed.

Complements

After reading the comments, I think the best solution for my problem should be boost::variant. But I am still wondering is there a way to combine the benefits of solution 2 and 3, i.e.

a. I can access members of type without changes.

b. Get the guarantee that reinterpret_cast<size_t> works.

Answer 1

You can mitigate the concerns about solution 3 with something like:

struct data
{
  // ...
};

template<class T, bool> class pad_;
template<class T> class pad_<T, true> { char dummy[sizeof(T) - sizeof(data)]; };
template<class T> class pad_<T, false> {};

template<class T> using pad = pad_<T, (sizeof(T) > sizeof(data))>;

class type : public data, pad<size_t>
{
  // ...
};

This code:

• assumes empty base optimization so that pad could be completely optimized out from type layout when sizeof(data) >= sizeof(size_t)
• hasn't the risk of zero length array

Answer 2

Though this being an interesting problem the design itself seams questionable.

1. When inserting a new element items marked unused are considered first before growing the vector. It means that the relative order of items is unpredictable. If that's being acceptable you could have just used a vector of (smart) pointers.

   Typically a vector is inefficient when removing items from the middle. Since the order doesn't matter it is possible to swap the element being removed with the last element and pop the last element.

2. All elements are of the same size; allocating them using a pool could be faster then using the system allocator.

   A pool basically allocates memory in big chunks and hands out smaller chunks on request. A pool usually stores the free list in yet unallocated chunks to track available memory (the same very idea described in the question). There are some good implementations readily available (from Boost and other sources).

3. Concerning the original design it is cumbersome to enumerate elements in the vector since real elements are mixed with "holes", the logic is going to be obfuscated with additional checks.

Probably there is some sold reasoning behind the original design; unfortunately @user1535111 is not telling the details.