Re: [boost] Intrusive containers: second iteration

From: frank_at_[hidden]
Date: 2005-04-29 12:01:04

Hi,

I'm currently developing some container libraries for my graduation thesis,
that has some similarity to this one. So some questions came up
in my stomach. First of all, what is this intrusive approach all about? 
As far as I understood the stored elements are not owned by the 
containers itself, but allocated by some other object. But why not
using a reference type and storing this in the usual non-instrusive
containers?

To depict that idea, I assembled a small example:

#include <iostream>
#include <set>
using namespace std;

template<class T>
class Ref
{
public:
        Ref(T* obj): obj(obj) {}
        inline operator const T&() const { return *obj; }
        inline bool operator<(const Ref<T>& b) const { return *obj < *b.obj; }
private:
        T* obj;
};

class MyRec
{
public:
        MyRec(int x, int y, int z): x(x), y(y), z(z) {}
        int x,y,z;
        inline bool operator<(const MyRec& b) const { return z < b.z; }
};

typedef Ref<MyRec> MyRef;

int main()
{
        MyRec a(0,1,2), b(3,4,5), c(6,7,8);
        typedef set<MyRef> MySet;
        MySet s1, s2;
        s1.insert(MyRef(&a));
        s1.insert(MyRef(&b));
        s1.insert(MyRef(&c));
        s2.insert(MyRef(&a));
        
        MySet::const_iterator i = s1.begin();
        while (i != s1.end())
        {
                const MyRec& r = *i; 
                cout << r.z << endl;
                ++i;
        }
        
        return 0;
}

My second question goes into data integrity.
I feel really bad, when I see the example.cpp where the
test class is inherited from imultiset_node_d. 
So the value of a object of type test is defined by x
and is accessibly from the user's side? I mean changing that
value from outside the underlying RB-tree implementation
would easily break it.

So it's all about being more efficient and being compatible
with existing algorithms that work on STL containers?
A point, my stomach feels good about;)

Best regards,
Frank.