Re: [boost] [intrusive] Review

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2007-03-20 06:41:18

Quoting Ion Gaztañaga:

>> Notice that the Class parameters do not appear at the same place. After
>> removing the first template parameter from _member_hook, the traits
>> would be accessed by:
>>   _base_hook<Tag>::value_traits<Class>
>>   _member_hook<>::value_traits<Class, &Class::Hook>
>> Now the situation is uniform, the Class parameter always appear as the
>> first parameter of value_traits.
>
> The review manager, Joaquin pointed this issue in a pre-review he did.
> You are right, the member_hook does not need any template parameter. The
> only problem is that I don't know how to declare a pointer to member
> where both the parent class and the member are templates. I mean:
>
> template<class T, member_hook T::* P>
> class value_traits;
>
> compiles fine, but I just want to have one template parameter

This is not a good enough rationale for the current interface. I insist in the
need for moving the class parameter from the hook to the value traits, 
both for
efficiency and clarity.

>> Speaking of the interface, half of the template parameters of the
>> intrusive container are used for specifying the type of the variable
>> storing the container size. This does not need that many parameters, as
>> they don't provide orthogonal features. So just one is enough:
>>   template < class Traits, class Cmp, class SizeType = std::size_t >
>
> They are orthogonal. Even if you don't have a member size (non-constant
> member), the `size()` method must return a value and `count()` functions
> in associative containers must also return a size type.

I hadn't noticed that your functions size() and count() don't return a 
size_type
as defined by the standard. The standard says that the return type of these
functions must be large enough so that it can contain any positive 
value of the
pointer_type of the iterators of your containers.

Moreover, there is not much point in putting a short type as an integer return
type, as the value will generally go through a fixed register, which doesn't
care about the reduced size of the return type. It may even produce worst
binary code, as either the callee or the caller will have to explicitly 
discard
the upper bits.

So I don't think it makes much sense to change the return type of these
functions. And as consequence, the two template parameters are still not
orthogonal :).

>> In the hooks, the assignment operators failing when the destination node
>> is already linked feels wrong. I understand what the rationale for iset
>> could be: assignment may change ordering of nodes. But for ilist, there
>> is no ordering involved, so assignment should be allowed. And for iset,
>> it should fail only when the ordering is broken, but I don't think it is
>> feasible to verify this condition; so it might be sensible to allow it
>> there too.
>
> The problem is that a safe-mode hook must assert if something is not
> properly unlinked.

But it doesn't have to be properly unlinked for it to be perfectly safe and
meaningful. As a matter of fact, you want to be able to change an element of a
list; they are not supposed to be immutable. Your library doesn't allow a user
to do "*i = v" when i is an iterator of a list and v an unlinked value. This
really strikes me as wrong!

>> Concerning assign and copy of intrusive containers, I agree that it
>> makes little sense. But only if both containers have the same type. You
>> could provide template operators in the case types differ but
>> value_types are the same. Notice that I'm talking about doing the
>> equivalent of "set2(set1.begin(), set1.end())", so the cumbersome
>> clone_from does not work here.
>
> Sorry, I'm missing something here, could you elaborate a bit more? What
> do you mean with "same type" and "types differ but value_types are the
> same"?

Maybe it would be clearer with an example. The following pseudo-code is
something I want to be able to write.

struct T { hook1; hook2; data };
iset<T,hook1> set1;
iset<T,hook2> set2;
...;
set2 = set1;

Best regards,

Guillaume