Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-20 13:23:29

Hi Dave,

Dave Harris wrote:
> In-Reply-To: <45F5011E.8484B515_at_[hidden]>
> joaquin_at_[hidden] wrote (abridged):
>> The review of Ion Gaztañagas's Intrusive library begins today
> I have spent half an hour reading the documentation. Overall I like it. I
> have some questions and comments.
> Is there any reason why Destroyers must destroy? It seems to me you could
> have a Destroyer which pushed the value onto another list. Is that right?
> If so, is it a reasonable thing to do? If so, perhaps "Destroyer" is not
> the best name. I'd suggest "Sink" instead.

No, there is no reason for this. You can do whatever you want with them,
you can even recycle the nodes to another intrusive containers, as long
as the operation is nothrow. Sink sounds good but now I need a name for

clear and_destroy --> clear_and_???
erase_and_destroy --> erase_and_???

> Could remove_and_destroy take a default Destroyer argument that deleted
> the value?

Well, functions can't have default template parameters, and you have
remove() that does nothing but unlink the node. What should be the
default? operator delete()? I don't think adding a default should be

> I hate the name "current" for the function that turns a value into an
> iterator. I'd prefer "to_iterator" or "as_iterator" or similar. "Current"
> just doesn't seem relevant to what it does, and the core thing it does is
> not indicated by that name.

Other reviewers agree with you. iterator_from or iterator_to have been

> Did you consider having pop_back() return a reference to the value popped?
> As I understand it, the usual reasons why this a bad thing don't apply
> here; returning a reference cannot throw, and the value referred to isn't
> deleted.

Well, my intention was to maintain the STL interface, although I knew
the value was still valid after being erased. I don't think back() +
pop_back() is in practice slower than your proposed alternative.

> Did you consider making it easier to use as a replacement for list<value*>
> ? The semantics are already close, but the intrusive lists use references
> where the non-intrusive ones use pointers. I can see me having to edit out
> a lot of asterixes in my existing code.

I understand that maybe replacing code using list<value*> is not an easy
task, but I prefer to stick to the STL interface.

> I was going to ask whether it would have been a good idea to allow a value
> type to be in several lists of the same type, but the more I think about
> it the more I agree that requiring the lists to be different types is
> best.

Well, you can't store an object in two intrusive lists at the same time
with the same type, because both lists would be using the same hook. The
types of both lists are different because each one uses a different
hook, and that should be defined at compilation time to achieve maximum

> I agree with Tom Brinkman that the introduction page of the documentation
> could do more to motivate the library. The core idea of using memory in
> the value type to store container-specific data, which is what makes the
> container "intrusive", needs to be mentioned earlier.


> I was pleased to see you mention the typical size overheads for values and
> containers. It seemed to me that the overhead for containers was a bit
> buried. I'd recommend you draw up a little comparison table which listed
> typical overheads for each type of container - hopefully including a good
> implementation of std containers if that's not too controversial.

Well, comparing sizes of STL containers is a bit misleading, because how
many bytes are we supposed to use in memory bookeeping if we use
standard allocators? Should I compare ilist<> versus std::list<T> or
versus std::list<T> + std::list<T*>? I will think about this.

> I would also like to see some speed measurements comparing std with
> intrusive lists and vectors. Obviously user's milage will vary, but given
> that performance is a major motivation for using this library I'd like to
> see at least some empirical indication that it can be faster.

Yes. I will try to make some simple use cases (insertions, erasures,
sorting, etc...).

> Regardless of the above I vote that Intrusive be accepted as a boost
> library.


> -- Dave Harris, Nottingham, UK.



Boost list run by bdawes at, gregod at, cpdaniel at, john at