2

I'm dealing with a templated key/value storage class that requires both a key and value type, and stores them internally as a std::pair. However, I found a case where I want to store only a key and still take advantage of this class's indexing. I would need to completely refactor this thing to deal with only a key and not a key/value pair (or waste lots of space), so I was wondering if there's a way to make a std::pair object take an empty struct (or something else), and only take up the same amount of space as the other type in the pair.

I tried it with this:

struct EmptyStruct
{
};

And ran this:

typedef std::pair<int, EmptyStruct> TestPair;
std::cout << sizeof(TestPair) << " vs " << sizeof(int) << "\n";

But got this output:

8 vs 4

In VC++ 2012 in "Release" mode with optimizations enabled, including /O1 "Minimize size".

Is there a way to make a struct be considered "sizeless" in the context of a std::pair?

user173342
  • 1,820
  • 1
  • 19
  • 45
  • You could also tackle this in the opposite direction, factor out the storage class and offer two interfaces, one with (key,value), the other with just (key). This is the common approach in standard library implementations, where `std::map` and `std::set` use the same underlying balanced tree implementation, each with a different `value_type` and comparator. – David Rodríguez - dribeas Dec 04 '12 at 17:17
  • Note that "Minimize size" will **not** change the size of the objects, it only affects the size of the generated **code**. The space optimizations inside types must be done at the library level. – David Rodríguez - dribeas Dec 04 '12 at 17:23
  • 1
    As I alluded to on ChrisW's answered, you can try using `std::tuple` instead, which is allowed to remove the space needed for empty types. This is up to the quality of implementaiton, though. Because VS2012 doesn't officially have variadic templates (but check out the [Nov 2012 CTP](http://www.microsoft.com/en-us/download/details.aspx?id=35515)!), its `std::tuple` implementation is very heavily invested in, yet. – GManNickG Dec 04 '12 at 17:26

4 Answers4

7

You cannot do that with std::pair, but with Boost compressed_pair.

Before you set out to write your own fully-conforming pair template with compression, be aware that this is harder than it looks.

pmr
  • 58,701
  • 10
  • 113
  • 156
4

Is there a way to make a struct be considered "sizeless" in the context of a std::pair?

No: because separate instances of a class must have distinct/distinguishable addresses ... so there's a minimum (non-zero) size.

ChrisW
  • 54,973
  • 13
  • 116
  • 224
  • That's *true*, but I'm reading the question as "could an implementation of `std::pair/std::tuple` give no overhead for empty class-types?" and the answer is yes, I think. Using empty base optimization, it should be possible to do so (I recall Howard Hinnant giving a demonstration implementation, IIRC.) – GManNickG Dec 04 '12 at 17:10
  • @GManNickG AFAIK libstdcpp performs empty object optimizations for `tuple`, but I have never seen it for pair. – pmr Dec 04 '12 at 17:14
  • @GManNickG: It is interesting that you bring up `std::tuple`, in that case the standard allows (IIRC) this optimization, but in the case of a `std::pair` that is not an option. – David Rodríguez - dribeas Dec 04 '12 at 17:15
  • @pmr (And David): Er, right. I'm being a bit silly saying `std::pair` would do it, aren't I? :) – GManNickG Dec 04 '12 at 17:15
  • @GManNickG Is the only thing that is missing to allow it member functions instead of direct member access? – pmr Dec 04 '12 at 17:17
  • 2
    For reference, [this is what I was referring to when I mentioned the EBO for tuple](http://stackoverflow.com/a/9643480/87234). @pmr: Some level of indirection is needed, yeah. But `std::pair::first` and `std::pair::second` refer to members directly, so the empty class has to exist somewhere (taking space). – GManNickG Dec 04 '12 at 17:23
1

There’s no way to do that with std::pair but it’s rather easy to create your own structure – compressed_pair which does that: just specialise the template if either of the types is empty to just hold one member.

There’s a library – SeqAn – which has such a type.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
1

You may specialize pair to not actually store value, if the second type is EmptyStruct

RiaD
  • 46,822
  • 11
  • 79
  • 123