on Tue Nov 25 2008, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:
<nod> Believe it or not vector<unordered_set<A>> is a viable container, even when many of those inner containers are empty. If the overhead(unordered_set<A>) can be 5 words instead of 9 words (or more), then the ability to fit a data structure into nearly half the space is a significant size *and* speed optimization (for some clients).
It is never the number of words that matter in shaving off the space overhead of a container. It is the percent difference in space overhead between an optimized and unoptimized implementation that matters. Because for the clients who care, they have a very large number of containers which statically have a small size(). If you can cut the overhead(container) by 25% or more, it is a big win.
One thing I've always wondered about this: in that case -- at least when you're not also trying to use the small object optimization -- why not always use a Pimpl idiom where an empty container (with no capacity) can be represented by a single null pointer?
It seems like you think compressed pair can only compress away one member, but IIUC you can chain them and then derive your hash table from that to compress as much as you like. Of course it would be nice to have a compressed_tuple that handles it all for us, but I thikn you _can_ do it.
I have high hopes that std::tuple will become the compressed_pair of the future. Technically, and especially with variadic template language support, it is not that hard to do (tuple is a pain no matter what without variadic template language support). Standards-wise, the current C++0X draft (N2798) does not outlaw, nor mandate, the empty member optimization for tuple,
Except that there is no "empty member optimization," right? Unless this is one of the langauge changes I've failed to notice (and there are a few), I think what you mean is that tuple is free to use derivation to take full advantage of the EBO, right?
and I hope to keep it that way. Recent straw polls on the LWG have been favorable to allowing the empty member optimization for std::tuple.
Until we get CWG to agree that the EMO exists, I doubt straw polls in LWG can make much difference ;-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com