Hi Samuel, Samuel Debionne wrote:

My first conclusion : Boost.Intrusive is an interesting library to me. Let see more in details.

Glad to hear it.

- What is your evaluation of the design? The use of hooks is user-firendly and I appreciate to be able to choose between member or base class hooks. Auto-unlink hooks are also intersting but I did not have a try. The instantation of a container was not a problem neither. In the other hand, I didn't not inderstand why the containers implements their own algorithm (reverse, remove_if, unique...) as member function. Are there any reasons not to use their STL counterparts ? Some of my comments overlay the documentation review, so see below.

Well, the aim of Intrusive was to offer the same interface as their STL counterparts. Unique is more efficiently implemented as a member function and if you find std::list::reverse useful, I'm pretty sure boost::intrusive::ilist::reverse will be useful too.

- What is your evaluation of the implementation? I didn't need to look at the inside of the library that much... which is a good sign for a end-user review. Just one question : iterators couldn't be implemented with iterator_facade ?

Good question. I wanted to minimize Boost.Intrusive dependencies, but I have no objection to use iterator_facade.

- What is your evaluation of the documentation? The overall documentation is fine. It is written with QuickBook. About the shape, I would put the usage before the concepts. And group "When to use" together with the usages.

Ok. Usage before concepts will make the documentation friendlier for a first-time reader.

The text describing the concept is not what I expected and remains a bit obscur. The concepts seems to be mixed with some implementation details. In my opinion, this part should define first the different nodes concepts (i.e. NodeSinglyLinked, NodeDoublyLinked...) that are the first template argument of the containers.

Ummm. I tried to do my best, but I agree that part can be improved.

The hooks are only helpers to make a class a model of these concepts. Value traits is a also a helper, a "hook selector/adaptor", for classes that model multiple nodes. They are not really concepts.

Well, the problem is that they are mentioned several times, so at least they should be defined.

As far as I understand, node algorithms are also an implementation detail that enable to share the basic mecanism of the container through several instantion of the same container with different types (static function). I would move this part to the design notes.

My intention was to offer the node algorithms as a public part of the library so that library writers in need of low-level node algorithms could find them in Intrusive. For example, algorithms for a red-black tree, which are not trivial to write. But if reviewers, consider this an implementation detail, I'm ready to remove it. The problem is that if a programmer wants to use Boost.Intrusive with his own "rare" nodes (as presented in the "Containers with custom ValueTraits" section) he needs to write the NodeTratis and ValueTraits. And these should be explained somewhere.

Did you consider using Boost.Concept to check the template parameter of the containers ?

No. But I will look at this. If this does not result in large compilation times or bigger code size, I'm for it. But I want to preserve Boost.Intrusive as lightweight as possible. My goal is that Boost.Intrusive should be one of the first libraries embedded C++ programmers look for.

Finally, the different container and iterators concepts should be defined (when they differ from STL, see bellow).

Ok. This is quite a big job and I would be interested in receiving feedback about "how" these concepts should be defined (another chapter, comparison with STL concepts...). Good comment, anyway.

In other places in the doc, some requirement (i.e. smart pointer requirement = TrivialIterator + get_pointer()) could be expressed as concept or refinement of existing boost or slt concepts.

Ok. Concepts are the key, I'm afraid ;-)

- What is your evaluation of the potential usefulness of the library? I find it usefull and a good complement to their STL counterparts. As the authors stated, I agree that this library is more a building block to build other more powerful, encapsulated containers. To be used carefully.

Thanks.

- Did you try to use the library? With what compiler? Did you have any problems? Yes. I used the library with msvc8. No I didn't have any problems with the library itself. But yes, I add some with its interaction with the STL. Intrusive containers claim to offer an STL-like interface which is not entirely correct.

I agree. The problem is what "STL-like" means. Obviously, the constness of the insertion objects is going to break some STL code. But you still have your iterators and all other algorithms. I agree that I should stress the problems we can have with insertion functions.

Here there are two options : either Intusive containers does not model the BackInsertionSequence concept and that should be written in the doc or/and some adapted insert iterator should be provided by the library.

Let's do both. Thanks for your example. So I'm afraid that intrusive won't match any STL concepts.

- Do you think the library should be accepted as a Boost library? Yes with minor corrections.

Thanks for you vote!

I would like to thank very much the authors for their great work. Hoping that it will help,

Sure. Thanks for the review.

Samuel

Regards, Ion

Kevin Sopp wrote:

Hi,

Hi Kevin,

...

- What is your evaluation of the design?

Outstanding, I think Ion really outdid himself with this one ;) intrusive lib has become much more than I had ever hoped for and it's really ready for primetime now.

Thanks.

It provides customizability at every imaginable point. Using node_traits and value_traits this can be done very cleanly, additionally one can choose between constant/linear time size() member function. The one thing that really struck my eye the first time I read the docs was that I could define the size type for the containers. I never really needed something other than std::size_t but I've read about embedded programmers that use 16 bit pointers for small collections and so only need a 16 bit size type. Of course with intrusive library you can use 16 bit pointers if you desire.

Customizability was a major goal. I wanted Intrusive to be useful not only to insert objects in containers, but also to write memory algorithms that need to store free chunks of memory in intrusive red-black trees. Even allow tricks like storing flags in the unused bits of a pointer used in node algorithms. The size type customization is also provided to ease the implementation of STL-like non-intrusive containers above intrusive containers. In STL-like containers, container::size_type is a typedef for allocator::size_type, which might not be std::size_t.

The one thing that still annoys me is the 'i' prefix. Really, now that everything is in the intrusive namespace I think it should be dropped. The first time I saw it, it reminded me of the 'I' prefix some people use for interface classes.

Ok. The question is if intrusive containers should be in the boost::intrusive namespace or they should be include in the first level boost:: namespace. If they remain in boost::intrusive, I will remove the i prefix if reviewers agree.

...

- What is your evaluation of the implementation? [snip]

A couple of things I noticed after examining the library again today:

[snip]

Thanks, I will add them.

...

- What is your evaluation of the documentation? [snip]

I agree with Samuel Debionne that the Concepts part can be improved. I really liked the summary at the end of the Concepts section. Maybe this should stay where it is (with one more/or a bit longer sentence for each concept) and then put the detailed description of the Concepts at the end of the documentation. Then the reader will know what the traits are for and can move on. Customizing the traits is more advanved and should be at the end.

Ok. I will need to rework all this stuff, so I think your proposal seems reasonable. Include the summary first to have the very basic definitions for the basic uses of the library. Include the full explanations before the advanced uses and custom nodes. Thanks.

...

- What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems?

Very useful, been waiting for this a long time. In fact I started to use it back in december to implement a cache system using the ihash_set now iunordered_set.

This was done to unify names with standard containers.

While this one required some boilerplate code to handle a resizable bucket array I was positively surprised that the two functions suggested_upper_bucket_count() and suggested_lower_bucket_count() were provided. The library lends you a helping hand wherever it can.

Basically, depending on the implementation, some numbers are better than others (some implementations use a dummy end bucket, others not). So I think that the implementation itself knows better than the user the optimized length of the bucket array. Some implementations might prefer power of two values instead of prime numbers. Glad to hear you find them useful.

It compiles cleanly on mingw/gcc4.1 and linux/gcc4.1.2. I stumbled upon a compiler error in mingw/gcc4.1: I declared a name tag for the hook in a class but upon instantiation gcc errors out with 'iunordered_set_base_hook<expression error>'. Putting the tag outside of the class remedied the situation. I haven't examined this behavior any further. I declare the value type that derives from the hook inside the class too, I think this could be the reason.

The old versions used a number to distinguish the hooks when more than a base hook was used. I recently changed that following Joaquin's good advices, because tags make tag collisions harder. Thanks for the report.

...

- Do you think the library should be accepted as a Boost library?

Without a doubt I think it should be accepted. I believe the code is easy to maintain and would be welcome to many programmers.

Thanks for you review and your vote ;-). I'd like to get suggestions and improvements from users to expand the library. Including more intrusive or pseudo-intrusive containers (avl trees, other hash implementations, non-circular lists and singly linked lists...) would be nice. I hope to include all the needed building blocks to make non-intrusive container implementations easier.

Kevin

Regards, Ion

Kevin Sopp wrote:

Hi Ion, I have another suggestion to make for boost::intrusive containers:

Add cbegin(), cend(), etc. member functions to retrieve a constant iterator from a non-constant container object.

As proposed in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1865.pdf

These are trivial to implement and I generally find them useful.

Good suggestion. Thanks, Ion

Hi Stjepan, Stjepan Rajko wrote:

...

- What is your evaluation of the documentation?

The general documentation, tutorials on different tasks and the examples are nicely organized and well written. After reading parts of the documentation, I was able to understand what the library was for, what its advantages and disadvantages are, and a good enough idea of how to use it.

The reference section is very detailed but hard to navigate. After going to the .hpp reference page, I had to figure out that I need to click on any of the class names for more information, and then faced a dump of all members. Some grouping of the member functions according to their use (even just using white space to separate them) would be nice. I really appreciated the complexity discussions.

The reference section was generated using Boost Quickbook/Boostbook/Doxygen toolkit, and I'm pretty it can be improved, but I don't know if what you are asking is possible. Maybe I should just write the reference myself instead of using the toolkit, but it's a lot of work to do if the reference is good enough. But reviewers have the last word.

Overview page:

Semantically, a Boost.Intrusivecontainer is similar -- space missing Boost.Intrusive<->container

Ok.

Presenting Boost.Intrusive containers page:

Non-raw pointers: If the wants to use smart pointers instead of raw pointers -- If the _user_(?) wants

Thanks.

Cloning Boost.Intrusive containers page:

The second parameter is an function object that will clone value_type objects returning a pointer to them. -- is _a_ function.

Ok.

Although, this sentence struck me as slightly confusing - perhaps something like "that will clone value_type objects and return a pointer to the clone."?

Ok.

The second parameter is an function object that will destroy value_type objects. -- is _a_ function object

Ok.

The word concepts seems to be getting more and more of a specific meaning in C++... I don't know whether there is another word that means the same thing as "concepts" but isn't "concepts", but if you can think of one it might be good.

I think concepts is fine.

std::pair< iterator, bool > insert(value_type & value) ;

Returns: If the value is not already present inserts it and returns a pair containing the iterator to the new value and true. If the value is already present returns a pair containing an iterator to the already present value and false.

-- I don't think this is quite correct. The behavior I observed is that the value is inserted if there are no elements equivalent to it in the set, according to the comparison function. Not quite the same as "if the value is not already present", I think.

Ok. With intrusive containers "tehere is no equivalent value" should be better, because the value itself could be already inserted in the container.

...

- What is your evaluation of the potential usefulness of the library?

Very useful. I really appreciate the possibilites that it presents and the associated advantages, as per the documentation.

Thanks!

...

And finally, every review should answer this question: - Do you think the library should be accepted as a Boost library?

Yes. Really nice work!

Good vote! Regards, Ion