unordered set design modification

[Jonathan Wakely]

On 21 October 2012 20:43, François Dumont wrote:
> On 10/21/2012 06:21 PM, Jonathan Wakely wrote:
>>
>> On 20 October 2012 22:07, François Dumont  wrote:
>>>
>>> Hi
>>>
>>>      Following remarks in PR 53067 regarding design of unordered
>>> containers
>>
>> Which remarks specifically?
>>
>> My understanding was that Paolo's suggestion to redesign things was to
>> avoid public inheritance, which we now do anyway.
>>
>>> here is a patch to prefer aggregation to inheritance with _Hashtable. I
>>> hope
>>> it is what you had in mind Jonathan. If so I will do the same for
>>> unordered_[multi]map.
>>
>> Are you referring to my comments in the "hashtable local iterator"
>> thread last December?  Because IIRC my concern was about deriving from
>> the user-supplied Hash and Pred types and this new patch doesn't alter
>> that.  What is the advantage of this new patch?
>>
>> (Apologies if I'm forgetting some other suggestion of mine.)
>>
>> I think my concerns about deriving from user-supplied types are
>> addressed by using the EBO helper (which prevents deriving from types
>> with virtual functions, as the vptr makes the class non-empty) and by
>> using private inheritance.
>>
> This patch is coming from this remark:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52942#c4
>
> You should be careful when you do remarks, they can have a strong impact ;-)

Ah yes, that comment.

As hinted at there, I was concerned about inheriting virtual
functions, but that's avoided by the EBO helper.

And I still think that using std::tuple would have avoided all the
issues with inheritance and kept the advantages of the EBO. That would
be too big a redesign now though.

> I fully agree with this remark just because for me encapsulation is a very
> important concept and aggregation offers better encapsulation than
> inheritance. This way unordered containers will expose only Standard
> methods. It doesn't fix any known issue at the moment even if this clean
> design would have avoid the 53067 issue.

It doesn't expose any non-standard members now that we use private
inheritance.  I do think composition is better than inheritance, but
I'm concerned about more churn to that code, it would be nice if it
settled down soon!

But since we still need to exploit the EBO for the node allocator, I
guess the code still needs to change anyway, so I'm ok with your
patch.  Using the EBO for empty allocators reduces
sizeof(unordered_set<int>) from 64 to 56, although it obviously
changes the layout of the class in an incompatible way. It's
unfortunate the allocator is the first member.

Some comments on the comments:

+       *  @param __n  Minimal initial number of bucket.

Should be "buckets"

+       *  @param  __x  An %unordere_set of identical element and allocator

"unordered_set"

+       *  The newly-created %unordered_set contains the exact contents of @a x.

Should be "__x" not "x".  This comment won't always be true once we
add C++11 allocator support, but we can fix the comment when that
happens.

+       *  All the elements of @a __x are copied, but unlike the copy
+       *  constructor, the allocator object is not copied.

This might not be true either, depending on the allocator.

+       *  This function fills a %unordered_set with copies of the elements in

"an" not "a"

+      ///  Returns the allocator object with which the %unordered_set was
+      ///  constructed.

In C++11 allocators can be replaced after construction.

+       *  Insertion requires atmortized constant time.

"amortized" (in several places)

+       *  This function only makes sense for unordered_multisets; for
+       *  unordered_set the result will either be 0 (not present) or 1
+       *  (present).

I don't like these "only makes sense" comments, but I realise they're
just copied from std:set so nevermind.

+       * @brief  Returns the number of element in a given bucket.

"elements"

The same issues occur in the unordered_multiset comments.

Unless Paolo has any other comments about the patch then it's OK with
the comment fixes.

Thanks!