CODEWITHSUNDEEP
c++linked-list
doron
doron

Reputation: 28932

An inline stl type list manager

Lets say I have an std::vector<MyObject>

Now from time to time I will need to add and remove some of these objects to and from a list. I could use a stl container list std::list<MyObject*> or even std::vector<MyObject*> for the list.

However this will require quite a lot of allocating and deallocating of memory if this lists change often.

What I normally do is define MyObject like:

class MyObject 
{
    stuff;
    MyObject* next;
};

And then hand link the objects into a linked list and unlink the objects as requires. This however does mean that I am hand coding a linked list whenever I want to do this which could be error prone.

What I would ideally like is something like:

class MyObject : public SomeListItem<MyObject> 
{
    stuff;
};

Where together with some management a SomeList<MyObject> class, the logic of my list is take care of. This should happen without any memory allocation since the linking pointers already exist in MyObject.

Does such a container exist in std or boost?

Edit The problem is during the course of my algorithm, I constantly create and destroy numerous lists of pre-existing objects. Using a next pointer embedded into my objects means I can use these list with zero need to allocate memory.

std::list or slist require memory allocation and this creates an unacceptable overhead.

Upvotes: 0

Views: 103

Answers (1)

John Zwinck
John Zwinck

Reputation: 249502

You are looking for exactly Boost Intrusive, which offers linked lists and other containers. It works pretty much exactly like you described--you can inherit from its base class and then link your objects together in a container. Of course there's more to it than that, lots more features, it's Boost after all.

Upvotes: 2

Related Questions