boost::intrusive without using a vector?

[Opsive]

Hello,

I am trying to implement the scapegoat tree provided by the boost::intrusive library, and in the example code (http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/sg_set_multiset.html#intrusive.sg_set_multiset.sg_set_multiset_example), it first inserts the object into a vector and then into the scapegoat tree. Specifically, I am looking at the following part (modified some just to show the parts that I would be using):

typedef sg_set
< MyClass, compare<std::greater<MyClass> >, floating_point<false> > BaseSet;
typedef std::vector<MyClass>::iterator VectIt;

for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));

BaseSet baseset;

//Now insert them in the reverse order in the base hook sg_set
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
baseset.insert(*it);
}


In this code, it inserts an iterator in the scapegoat (baseset). What if I don't want to create the vector first? Is it possible to create a one object iterator? I don't want to create the vector first because I already have the object ready to go and be inserted, I figure that it is wasted storage/cpu cycles to first insert into a vector if the only purpose of that vector is then to be inserted into a different list.

Thanks,
Justin

[exterminator]

Ok, this is the first time I have went through the boost::intrusive library. Thanks for forcing me to do so. :)

Now your doubts:In this code, it inserts an iterator in the scapegoat (baseset).It is not an iterator being inserted. Note that, the iterator has been applied with the dereference operator. So, actually you are calling insert member function of the BaseSet with the actual object itself. Not a copy. Not an iterator. It holds the object itself. (Consider that the intrusive container holds a pointer to your element, for ease of understanding. May not be what actually is happening but something equivalent can only make it possible if you don't keep a copy). What if I don't want to create the vector first? Sure. Don't do it. Afterall, there would be a valid reason why you want to store an object in an boost intrusive container and not the standard STL containers. But the thing you should be careful about is object lifetimes. If any of a) your objects b) the instrusive container itself go out of scope (or their lifetime ends) then for a) you would have an intrusive container with an invalid member thus leading to problems with the container where it would try dereferencing the already destroyed object (for ex: reaching out to next node from a dead object or even trying to dereferencing this object from another living one - a crash at best) and for b) you would need to take care of objects, so that you don't have leaks or any other unwanted behavior got from living objects (in case their destructor had some meaningful/important stuff to do before they died out). Of course, this is considering you don't have the auto_unlink feature enabled (probably still you need to destroy the objects) for your container (I am not sure if this feature (auto_unlink-ing) is applicable to all boost intrusive containers or not, you should confirm with the documentation depending on if you do want to use it).
Is it possible to create a one object iterator?:) I don't understand the question. You don't create the object's iterator, but a container's. In the above code, the iterator is of the vector class, dereferencing which gives you the reference to the object held in the container itself. I think, with my previous comment clarifying "insert an iterator" should solve this doubt as well as I think this is a result of the previous confusion you had.I don't want to create the vector first because I already have the object ready to go and be inserted, I figure that it is wasted storage/cpu cycles to first insert into a vector if the only purpose of that vector is then to be inserted into a different list.Like I said, managing the object lifetime is completely your responsibility with those intrusive containers as they don't do lifetime management at all as the STL containers, for example. The store the object itself, not copies and hence you have to be careful. The documentation makes note of this several times, so I consider it can be a common pitfall to intrusive containers usage. The vector used in the example is just for illustration saying "imagine you had so many objects somewhere". In the example, that somewhere is the vector. You are free to elide that step (and in real code, of course you would not have it as it is you who has raised their hand to do the lifetime management themselves and not ask for help from anyone else. You are the expert, you know what it takes, how to do that, and how it was a performance issue and/or how you want to take control).

The only thing I was surprised about is why does he insert in reverse order. But after I looked at the example again from the link you gave, it seems that he is just doing that because he has got two example instrusive containers. And he just loops over the vector once and inserts into both containers and then when looping over the two containers individually, he moves to end with first one and then reverse iterates for the second one. Quite a pain than doing just a re-seed to the begin() iterator. Hopefully, there is nothing more to it.

Hope this helps.

[Opsive]

Thank you for the detailed response, it helped a ton.

Thanks again,
Justin

[anisiva]

Hi, I also came across the boost intrusive lists. I am using it to replace some of the roguewave libraries. However, I face some trouble in that.

I am using safelink (and not auto-unlink) which is the default option to link my objects.
I want to create a list first and then create the object and insert into the list as more often this is will be the real time case that I will face.

However, if I use safelink option, it does not allow me to create the list first and then the objects. It always has to be the objects first and then the list. Otherwise, it gives me a run time assertion failure.
I am not able to understand why. Is there any alternative to this?

Thanks!