Guillaume Melquiond wrote:
* First, a few points that need to be addressed, or at least commented upon, in my opinion.
Here we go.
The member hooks are parametrized by the class name, and I can't see why it is needed. As the matter of fact, the base hooks don't need the type, so the member hooks should not either. In my opinion, it is just a waste of compile time and of executable space (think run-time or debug type information). Moreover, it would make the interface simpler and remove a discrepancy between base and member hooks. This is current situation: _base_hook<Tag>::value_traits<Class> _member_hook<Class>::value_traits<&Class::Hook> 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: 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 template<member_hook T::* P> class value_traits; This is a compilation error. Can C++ deduce both the parent class and the pointer to member? I don't see any reason that should forbid this, but I can find the right syntax.
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.
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. That's why it's called safe-mode hook. If you have a class that implements a trivial assignment operator, then if the hook is linked, you have two options: -> the assignment is a no-op (the node is still linked). -> the assignment asserts. A user can implement a operator= for the node that does not call hook's operator= if he wants to just ignore the assertion. But an "assignment" for a hook has no sense: two "safe" hooks can't be linked in the same position in a container. The same happens for auto-unlink hooks, because they have safe-mode properties. Do you think this assertion is going to be more problematic? I thought this assertion would help users detect programming errors.
Concerning the advanced insertion functions, I'm not sure if they are really useful. It seems to me like the insert_check/commit functions for iset are just redundant with the usual way of doing it in the STL: calling lower_bound, checking the iterator, and then hinting the insertion into the set.
The are useful, believe me! First of all, lower_bound + insert with hint is not optimal, since insert with hint must check if the hint is correct, so it must execute two comparisons. Second, insert_commit is a no-throw function, which is an important property insert with hint does not have, because the comparison functor can throw. Apart from that, unordered associative containers have not lower_bound, and insert with hint has the same cost as insert without hint. I would remove the insert with hint function for unordered containers, I wanted to maintain TR1 unordered containers' interface.
About auto-unlink hooks, you say that they must be used carefully because "removing the object is thread-unsafe". I'm not sure to understand what you mean. Even for manual-unlink, it is unsafe to remove an object if several threads are using the same container. So is there a particular reason to mention it here?
Yes it's unsafe, but a manual-unlink is, well... manual. So you know when you are calling it and you can wrap it with a mutex. A destructor of a base or member class is not explicitly called, and you can't wrap it with a mutex unless you wrap the the destructor of the whole object.
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"?
The ilist class provides an assign_and_destroy function. The name is misleading, as the function will destroy the old elements and then assign new elements. In comparison, all the other _and_destroy functions delete the elements acted upon, while assign_and_destroy deletes unrelated elements. Perhaps, this function could be removed, as it does nothing more than just clear_and_destroy then assign.
I just added "...and_destroy" functions to all functions that erase elemnets, but perhaps you are right that assign and destroy does not offer anything and the name should perhaps be "destroy_and_assign". I don't have any problem to erase it.
The irbtree class is a nice thing to have, so it shouldn't be hidden as a detail, especially as its interface is similar to the ones of the other containers.
I find it useful, but I didn't know if reviewers would find it also useful. For example, I've implemented Boost.Interprocess containers using a tree class, which is based on irbtree. It's an multiple value container that has functions that can check for duplicates. This class would be a new associative container category similar to "Multiple Sorted Associative Container", but offering unique insertion functions.
Typo in advanced_lookups_insertions.html, "a name it's enough".
Thanks.
- What is your evaluation of the documentation?
It contains all the needed information, but it is a bit complicated to get at it. In particular, the class references should be directly accessible from the main page. The introduction could also benefit from explaining what an intrusive container is and why to use it.
Ok.
- Are you knowledgeable about the problem domain?
My code is a heavy user of intrusive lists. I never went as far as building an intrusive set though, but I do have some use for it.
Glad to hear it.
- Do you think the library should be accepted as a Boost library?
Yes, I vote for inclusion. But I would really like the two details I mentioned about the interface to be solved before it is engraved in stone.
Thanks for the vote. I'm waiting your comments! Best, Ion