* First, a few points that need to be addressed, or at least commented upon, in my opinion. 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. 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 > Then you specialize your containers, so that the size is not stored when the type is void. If you think void is not descriptive enough, you can replace it with a dummy type called no_constant_time_size, or whatever. 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. 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. Especially since you already provide an optimized lower_bound function, which can be used without creating the value. 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? 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. 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. 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. Typo in advanced_lookups_insertions.html, "a name it's enough". * Now for the review itself. - What is your evaluation of the design? The concept of intrusive containers is sound, and the library is really generic. Some bits of the interface may require a bit of tuning (see the first two points above). - What is your evaluation of the implementation? The implementation looks good. I especially appreciated the fact that the default classes were relying on void* to reduce code duplication. - 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. - What is your evaluation of the potential usefulness of the library? It can be extremely useful for some algorithms, when elements have only one owner but you want them to be part of several structures. - Did you try to use the library? With what compiler? Did you have any problems? I exercised the library by building a non-intrusive multiset upon it. I compiled with GCC 4.1. The implementation was a bit slower than the original std::multiset, but nothing too worrying. I didn't encounter any problem: thanks to the intrusive library, the implementation was straightforward. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? In-depth study. - 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. - 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. Best regards, Guillaume
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
Ion Gaztañaga wrote:
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.
There is none. There's no such thing as implicit template parameters. Each parameter must be explicitly specified. P is a non-type template parameter; it takes a constant value, not a type. The constant value is a pointer-to-member. (Typically an offset inside a class, but of course that's implementation-dependent.) A pointer-to-member needs a class it points into. In your case, which class is it? You only have T there, so the compiler looks for a type called T. Not finding one, it throws an error. If there was an implicit template parameter there, that would make the code extremely fragile: as long as no type T is defined at the point of the template declaration, the template has two parameters - probably the compiler would, not finding a type T, assume it's an implicit template parameter. If at any point in time a type T is made visible to the template declaration, the meaning suddenly changes. This is of course unacceptable. And it works the other way, too. Consider: struct FooBarZoot { ... }; template <int FoobarZoot::* P> class Oops { ... }; How many template parameters does Oops have? That's right, two, because FoobarZoot is different from FooBarZoot and thus an implicit template parameter. The error message would be very helpful, too. As you can see, it's imperative that every template parameter is specified explicitly. Sebastian Redl
AMDG Sebastian Redl <sebastian.redl <at> getdesigned.at> writes:
Ion Gaztañaga wrote:
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.
There is none. There's no such thing as implicit template parameters. Each parameter must be explicitly specified.
It's possible but ugly using macros. template<class MemberPointer, MemberPointer P> class value_traits; #define BOOST_INTRUSIVE_VALUE_TRAITS(member_pointer) \ value_traits<BOOST_TYPEOF(member_pointer),member_pointer> member_hook_t::BOOST_INTRUSIVE_VALUE_TRAITS(&T::hook) In Christ, Steven Watanabe
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
Guillaume Melquiond wrote:
Quoting Ion Gaztañaga:
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.
I'm not trying to justify the current interface. I just wanted to say that two parameters will be needed. It's clear that the hook shouldn't have a template parameter because we are generating unnecessary code. Thanks for pointing this out.
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.
The standard also allows allocator::size_type to be any type, so if I want to support building STL containers above Intrusive, I must somehow allow specifying the size_type for Intrusive.
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!
"*i = v" is convincing. You can still achieve this if you define operator=() for a value_type, not calling hook::operator=(). However, I agree that that compiler generated assigment operator should allow "*i = v". So I will make hook assigment a no-op, to maintain the value linked in the container. This will make ordered containers a bit unsafer, but you can't have everything ;-)
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;
If sets are different types, operator= has no sense in my opinion, because it should destroy old values and there is no function to do so. To me, only a move assignment/construction (in C++0x) would make sense: set2 = std::move(set1); which would be equivalent to a "set2.swap(set1)" (no value is destroyed). But intrusive containers are non-copyable and non-assignable and I want to emphasize this with the interface. A matter of taste, I guess.
Best regards,
Guillaume
Thanks again, Ion
Quoting Ion Gaztañaga:
The standard also allows allocator::size_type to be any type, so if I want to support building STL containers above Intrusive, I must somehow allow specifying the size_type for Intrusive.
Would returning std::size_t prevent somebody from building STL containers above Intrusive? If the allocator::size_type is so strange that you cannot convert a std::size_t to or from it, I'm not sure a common STL library would be able to use this allocator for its containers anyway. Perhaps I'm missing something.
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;
If sets are different types, operator= has no sense in my opinion,
They are only different because of the intrusiveness. They really are both sets with the same type T and the same ordering std::less<T>. So from a std::set point of view, they have the exact same type and it makes sense to have an assignment operator from one to the other. The code can already be correctly compiled if you write instead: set2.clear(); set2.insert(set1.begin(), set1.end()); But the insert operation is highly inefficient here, as the whole red-black tree is built from scratch for set2, with lots of balancing, although in the end it could have the exact same structure as the one from set1. Best regards, Guillaume
Dear all, this being my a first post/review, I hope that it is not too "stupid" ;-). I have been using this library since last October (actually the latest version of Olaf Krzikalla that wast uploaded by Ion Gaztañaga in the Vault around that time) in our Finite Element code. I mainly used the iset/imultiset containers of that version to somehow emulate an intrusive map: unfortunately as during looking-up phases I had to create a whole dummy ojbect initialized with the key searched for to be able to use the imultiset::find method; I decided to implement an intrusive map (imap) modifying the red-black tree implementation that comes with the library, something like: template<typename Key, typename Access, typename KeyExtractor, typename Compare = std::less<Key>, bool clear_on_dtor = true> class imap : boost::noncopyable { public: // typedef private: // select the type of the tree (red-black or avl) // depending on the type of the tree hook (i.e. rb_node, avl_node) // for instance, a user class UserClass to be used into 2 imap (one using // a rb_tree, the other an avl_tree) is defined as // class UserClass : public imap_node_d<Tag, unlink_dtor, rbtree_node>, public imap_node_d<Tag, unlink_dtor, avltree_node> typedef typename itree_dispatcher<Key, Access, KeyExtractor, Compare, typename Access::itree_node >::value_type tree_type; tree_type m_tree; // the actual tree structure // etc ... }; borrowing the keyExtractor concept from the Boost.MultiIndex library. (being a "baby" in the library/template world, I kind of follow existing boost libraries design). I am happy to see that with this new version of the library, I can directly use the iset container taking advantage of the find(key, comp) method ;-). Also, the iset container instantiation is simpler as the Compare operator actually combines the comparison operator and the key extractor. It may be help full in the example about the iset/imultiset container that the two container uses different type (currently they both use MyClass int_ data member as key), and make use of the iset/imultiset::find(key, comp) method. - What is your evaluation of the design? I am not qualified enough to say much about it, except that it was easy to use: creating a container was easy, even with legacy classes. The use of node and value traits really make customization easy. As for performance oriented code, I like the presence of insert_check and insert_commit methods of the associative intrusive containers. I always feel that similar methods were missing from the STL associative containers. - What is your evaluation of the implementation? It is well above my standard ;-). It is well documented and it was quite easy to navigate through the code. - What is your evaluation of the potential usefulness of the library? I find it useful. I agree that this is a kind of "low-level" library and you have to be aware of what you are doing with it, but it may be worth it in some cases. - Did you try to use the library? With what compiler? Did you have any problems? Yes. I used the library with gcc 4.1 and intel icc 9.1 under linux. I didn't have any problems with the library. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I have been using the previous version of this library for a couple of months now. Even though, this new version have been quite upgraded, it was quite easy to plug it into our code (creating an intrusive map as a wrapper around iset went smoothly). - Are you knowledgeable about the problem domain? I am no expert on containers, but as a user in the HPC community, I well aware of problems like data locality and cache trashing. - Do you think the library should be accepted as a Boost library? Yes. I will definitively use it; and as an other review wrote, I will maintained my own copy, it is not ... I really would like to thank very much the authors for their great work. Best regards, Henri. -- Institute for Computational & Mathematical Engineering Stanford University http://icme.stanford.edu P.S.: when I implemented the tree methods, I also ran into the problem of having a constant time size method and allowing the node to unlink itself from the tree (by calling either node::unlink() or the destructor operator). Looking at the original unlink_and_rebalance() method in the rb_node class of Olaf Krzikalla's implementation: void rbtree_node::unlink_and_rebalance() { rbtree_node* h = this->parent(); if (h != 0) { // this node is linked // go up the tree until the header node while (!is_header (h)) h = h->parent(); this->remove (*h); // h is the header node } } I figured that the node that unlinks itself knows "implicitly" from which tree it actually unlinks itself: rbtree_node::unlink_and_rebalance() starts from the node and goes up the tree until it reaches the tree's header node. So to allow both nodes to unlink themselves with a constant time map/tree size() method, the tree nodes counter can be actually be embeded into the tree's header node which is derived from the rb_node class; and uses a cast in the rbtree_node::unlink_and_rebalance() method. More precisely, something likes that: class rbtree_node { public: void unlink_and_rebalance(); // see below // other needed methods private: //All needed data member: parent pointer, color, etc ... }; class rb_header : public rbtree_node { #ifdef DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE public: rb_header() : rbtree_node(0) { } // rbtree_node(0) makes a header node size_t node_count() const { } void incr_node_count(ssize_t n) { } #else public: rb_header() : rbtree_node(0), m_node_count(0) { } size_t node_count() const { return m_node_count; } void incr_node_count(ssize_t n) { m_node_count += n; } private: size_t m_node_count; #endif }; inline void rbtree_node::unlink_and_rebalance() { rbtree_node* h = this->parent(); if (h != 0) { // this node is linked // go up the tree until the header node while (!is_header (h)) h = h->parent(); this->remove (*h); // h is the header node static_cast<rb_header*>(h)->incr_node_count(-1); } } template<typename Key, typename Access, typename KeyExtractor, typename Compare> class iRb_tree { public: // typedef ... private: // private typedef // data member rb_header m_header; // node counter embeded into it if DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE is not defined key_compare m_key_compare; key_extractor m_key_extractor; // some methods that use the nodes'count embeded into the header node iterator insert(link_ptr y, const_value_ref val, bool link_left) { link_ptr z(node(val)); tree_node::link_and_balance(z, y, link_left, m_header); m_header.incr_node_count(+1); return iterator(z); } public: size_type size() const { #ifndef DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE return m_header.node_count(); #else return std::distance(begin(), end()); #endif } // etc ... }; I am not sure if this applicable with the new intrusive library that uses "generalized pointer"; but if it is, it may allow to have both constant time size method and auto-unlink node in intrusive containers that use an rb tree (or avl tree) as underlaying implementation.
Hi Henri, Henri Bavestrello wrote:
unfortunately as during looking-up phases I had to create a whole dummy ojbect initialized with the key searched for to be able to use the imultiset::find method; I decided to implement an intrusive map (imap) modifying the red-black tree implementation that comes with the library, something like:
[snip] I am happy to see that with this new version of the library, I can directly use the iset container taking advantage of the find(key, comp) method ;-). Also, the iset container instantiation is simpler as the Compare operator actually combines the comparison operator and the key extractor.
These new comparison/search functions were added for this and to make possible building map-like non-intrusive containers, where just the key part is used to search the data. I would be interested in the avl code you have used in your example. It would be nice to have avl_tree_algorithms in the library, and we could even make an intrusive associative container based on that tree. Contributions are welcome ;-)
It may be help full in the example about the iset/imultiset container that the two container uses different type (currently they both use MyClass int_ data member as key), and make use of the iset/imultiset::find(key, comp) method.
Those advanced functions are explained in the next section, so I don't if including them in the previous example would be logical. I'll think about it.
- Are you knowledgeable about the problem domain? I am no expert on containers, but as a user in the HPC community, I well aware of problems like data locality and cache trashing.
Any suggestion from HPC people is well received ;-)
- Do you think the library should be accepted as a Boost library? Yes. I will definitively use it; and as an other review wrote, I will maintained my own copy, it is not ...
Thanks for your vote. I hope we can continue improving Intrusive for HPC needs.
Best regards, Henri.
Regards, Ion
participants (5)
-
Guillaume Melquiond -
Henri Bavestrello -
Ion Gaztañaga -
Sebastian Redl -
Steven Watanabe