Sign in to follow this  
MyFirstThought

Intrusive Containers and STL

Recommended Posts

Hello - This is my first post and it's a big one but I'm hoping you guys have the answer I'm looking for! :) I've read with interest the EASTL document that was released last year, and while it is an interesting document, there is one thing that confuses me. The document talks about 'Intrusive Containers' and describes them as
Quote:
Intrusive containers are containers whereby the user provides the nodes and thus no memory is allocated and cache behavior is improved during container manipulations. Another benefit is that elements can be removed from containers without referencing the container (i.e. without calling container member functions). This is useful for when a class hands out element pointers to clients which the client will eventually hand back. Another benefit of intrusive containers is that is they doesn't require elements to be copyable, and sometimes element copying is not possible.
I've looked into Intrusive Data Structures and as far as I can see, they mean containers that contain references to the next/previous at part of the object type (so intrusive_list<CMyObject> would have CMyObject::next and CMyObject::previous and the relevant set functions). That much is clear, but what I don't understand is the "no memory is allocated" part. Doesn't the list still have to allocate the memory to store what is being added, or do you pass a pointer to a heap and it uses that (but isn't that what allocators are for?). Or, does the object get passed and only a reference is kept (so you have a large set of objects that you pass to it, but those objects have to be in memory for all eternity for the container to use?). One link (I can't seem to find it anymore) mentioned that an intrusive list should be inherited from, but that makes no sense to me (especially if it wanted to be STL like...). I assume how it works is the reason why there is no intrusive_vector or intrusive_deque.... Any ideas? J

Share this post


Link to post
Share on other sites
It's a terminology thing; your thinking isn't incorrect. In a regular (extrusive) STL container, one considers the container itself as primal; an item in the container exists only for the purpose of being in the container. It's in the container when it's born, when it dies, and everywhere in between. Because of this, it makes sense to think of node allocation and list insertion as the same operation.

In contrast, with an intrusive container, an object can join and leave a container at will. An object may start out unattached, then later join with a container. Because the memory has already been allocated, the manipulation itself is technically allocation-free.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this