On Aug 5, 2008, at 2:22 AM, Phil Bouchard wrote: [SNIP]

Right now shifted_ptr_test2.cpp works perfectly fine with the slightly adapted STL container to smart pointers and using special allocators needed to define all internal characteristics used by the container. We see in shifted_allocator:

template <typename T> class shifted_allocator { public: typedef shifted<T> value_type; typedef shifted_ptr<T> pointer; typedef const shifted_ptr<T> const_pointer; ... };

- value_type: being the real concrete type expected by the smart pointer - pointer: defines the node pointer used internaly by the container [TRUNCATE]

Isn't "const_pointer" supposed to be an analogue of "T const *"? Right now, you have it represent "T * const", which definitely isn't the same thing! -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:56F3BD3B-DAC3-43B1-96F5-4BB4A3919B10@woodhull.com... [...]

But to get there wouldn't you need to change the public interface of set/map? Right now it won't even admit it's holding a tree. Wouldn't you have to teach it how to reuse nodes rather than creating new ones? I also think there might be overlap issues between an inserted tree and its new siblings. For list, you *might* be able to keep the same interface, but the invariants would be much stranger if one list could modify another.

Well if we could have external access to the nodes themselves we could do a lot. I think this should be a task delegated to iterators. I do not wish to elaborate to much at this time because it is late and I would like demonstrating another useful example. The following doesn't work yet and I found another bug I need to correct but the idea is relatively easy to get. Here's an example on how we could write a "human brain kernel", which is all it basically really is: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/libs/smart_ptr/example/r...

In sum, I'm very interested in these data structures, I just wonder if they might be better served by new classes rather than modifications to STL. Your original application in garbage collection seems valid to me, although I am no allocator expert.

Everybody has their own preferences but personnaly I do not have strong beliefs in new classes. Functional programming is a very powerful option and nesting up these containers would be very extendible I think. But this should be up to the programmer to see his options. Thanks, -Phil

"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:EC4056C7-4D91-4591-A2CC-D909A6340FF6@woodhull.com... [...]

Do you mean, there would be special iterator types that mean "reuse these nodes" instead of "copy these"? Or do you have some other way of preserving the public interface of e.g. std::set while adding the shared node functionality?

I think having classes derived from nodes would be a great idea. I have improved the example I submitted yesterday with a new one. I haven't fixed the run time bug yet but once again the code is fairly easy to understand. I added some code making our brain learning and I am using a global map pointing to the neurons themselves. This is a great example in this scenario adn we can see how we could benefit from these nodes. Imagine the map uses our class called "map_node" as a template parameter for example. We could explicitly attach neurons with nodes and not suffering from all these temporary little nodes having pointer to neuron as data members we currently have. This way the map will refer to the same object allocated on the heap. Let's take a look at the following file: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/libs/smart_ptr/example/t... [...]

I haven't really considered ownership or GC (don't need it for my app, Dynagraph), so I imagine your techniques (or hopefully, library) could be useful for people with metagraphs who want automatic lifetime management.

Just for the record... I am not using garbage collection at all. Nothing is being collected and no periodic system slowdown is required. [...]

If I understand correctly, it's a kind of neural net and shifted_ptr would delete regions when they become detached?

Precisely, just disregard that deallocation problem and expect objects being destructed in real time. [...]

Agnostic here - whatever works best. I was assuming that you would have to make massive changes to the public interfaces of the STL containers; now I am not so sure that is true.

No, we can see some of them in the following sample patch file: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/bits/stl_list.h.patch [...]

What I am trying to understand is that your library seems to be about lifetime management, but then you are also talking about adding all this cool new functionality to the standard containers. Do you anticipate adding new methods to STL containers, or is the "external access to the nodes" via shifted_ptr itself? How would you express the command, "splice this subtree into another container"?

The first file I was previously refering to is an example of what I think would fit best; i.e. by defining our own nodes and using them as a container template parameter. "splice this subtree into another container" is exactly what I am looking for and I am very interested into searching only part of a tree, not the entire tree. Maybe by creating a new map constructor defining the beginning and the end of the new map using iterators, but in contrast to the actual one we don't want to duplicate the nodes. It should therefore be reasonnably fast.

If your library reflects a system of objects at runtime so that any pointers between them are traversable, then I think there might some interesting synergy with what I'm working on, which is about describing pointers between types at compile time.

I am not sure what you are referring to but hopefully you have a better overview of what it actually is and where it is going. STL support for smart pointers is imminent. Bests, -Phil

"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:EC4056C7-4D91-4591-A2CC-D909A6340FF6@woodhull.com... [...]

I think we are working on complementary problems having to do with better ways to manage systems of objects that point to each other. In the metagraph library, I am working with fusion and intrusive to build up objects that are e.g. nodes in graphs and also items in lists and also nodes in trees, all at the same time. Really the "is also" is what intrusive allows and I'm trying to describe these systems better using metagraph patterns, which are metadata graphs describing object types ("roles") and the other types they point to or contain ("relations").

Intrusive node pointers cannot be owners of the object referred to. If we include all the necessary node pointers according to the number of containers pointing to the node itself then we could take advantage of all the container properties combined at the same time: struct node : list_node, map_node, vector_node { char c_; node(char c = '') : c_(c) {} bool operator < ()... bool operator == ()... }; node elements[] = (node *) {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' ', 't', 'e', 's', 't'}; // e prefix here stands for "explicit": elist<node> l(element, element + sizeof(elements) / sizeof(* elements)); emap<node> m(element, element + sizeof(elements) / sizeof(* elements)); evector<node> v(element, element + sizeof(elements) / sizeof(* elements)); cout << v[6].c_ << endl; cout << m.find("a")->c_ << endl; Here the vector will have to support index fragmentation if we start inserting objects between consecutive ones: (l.begin() ++ ++)->insert('h'); [...]

What I am trying to understand is that your library seems to be about lifetime management, but then you are also talking about adding all this cool new functionality to the standard containers. Do you anticipate adding new methods to STL containers, or is the "external access to the nodes" via shifted_ptr itself? How would you express the command, "splice this subtree into another container"?

I am already adapting the current Gcc Libstdc++ containers to support smart pointers. All the details related to explicit node access haven't been discussed yet but any contributions to this are welcome. [...] Bests, -Phil

"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:A671761D-B76D-4C0C-86A6-592023FCFABC@woodhull.com... [...]

I think that the principles of ownership and the lifetime management system you are proposing could probably be applied to systems of intrusive containers, more quickly than a change to the c++ standard (perhaps via the metagraph library I'm working on ;).

Intrusive containers are very useful and shifted_ptr itself uses its own version of intrusive_list and intrusive_stack (which isn't present in Boost.Intrusive BTW). But even if ownership support isn't impossible adding for intrusive containers, the latter was not made for this (can refer to objects on the stack) and so are generic smart pointers not made for differenciating objects living on the stack or data segments with heap blocks. [...]

...

Here the vector will have to support index fragmentation if we start inserting objects between consecutive ones: (l.begin() ++ ++)->insert('h');

By "index fragmentation," do you mean std::vector should remap indices to accommodate any changes? That sounds really neat, but does that logic really belong there and not in some other class with different performance guarantees?

It cannot belong to std::vector only, but to the main supercontainer class linking all of them and supporting it if necessary. But I haven't implemented anything as such yet but the index fragmentation I'm talking about consists of mapping indices to range of iterators so that an insertion in the middle of a vector by the list handler is transparent to the vector and random access to the nodes still is a constant time operation in the average case scenario. For example I got: node elements[] = (node *) {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' ', 't', 'e', 's', 't'}; elist<node> l(element, element + sizeof(elements) / sizeof(* elements)); evector<node> v(element, element + sizeof(elements) / sizeof(* elements)); // Insert operation using the elist (-- l.end())->insert('.'); // The evector::operator [] (size_t p) would map ranges as such: if 15 -> return node '.' if 0 - 16 -> return node 'T' to 't' I think a huge container inside an application will always suffer from imperfections and this could be a decent alternative to the problem. A map mixed with a list, a vector mixed with a set or all four together offers an infinite set of properties. [...]

But at the same time I am really eager to see your redesign - it is such a dramatically different approach, and STL could surely be generalized better.

Well we now have exclusive problems we want to fix. We have: - Smart pointer support for STL (pointer wrappers are useful for some allocators) - Supercontainer with shared access to nodes The latter here would be reused code from the STL all mixed together. There is no C++ standard redesign here, simply a Gnu Libstdc++ code extension. [...] Thanks, -Phil

Here is a discussion I started with Gordon 2 weeks ago and I wanted to share globally because of its interesting features which aren't related to smart pointers: "I think a huge container inside an application will always suffer from imperfections and this could be a decent alternative to the problem. A map mixed with a list, a vector mixed with a set or all four together offers an infinite set of properties. Let's put it this way. All new "unordered" and multiset containers could easily be implemented as: 1) superc1st<double, list, vector> s1; 2) superc2nd<string, double, map, vector> s2; 3) superc2nd<string, double, map, map> s3; Where (explicit specializations for sake of example and please disregard missing "typename"s): 1) template <> class superc1st<double, list, vector> : public _list<0, void, double>, _vector<1, void, double> {...}; Here are examples of its usage: s1.push_back(5.7); s1[0] = 5.8; 2) template <> class superc2nd<string, double, map, vector> : public _map<0, string, double>::base, _vector<1, string, double>::base {...}; This one can be accessed as such: s2["Height"] = 6.3; // <-- O(log n) s2[10] = 5.9; // <-- O(1) 3) template <> class superc2nd<string, double, map, map> : public _map<0, string, double>::base, _map<1, string, double>::base {...}; To access 3) we could add indexed types we can cast the container to:s3.get<0>()["Age"] = 31; The underscored containers will be defined as: template <int I, typename T, typename U> struct _map : std::map<T, U> { typedef std::map<T, U> base; base & get<I>() { return * this; } // explicit function spec. won't work here (should be Ith type pack cast) }; And: template <int I, typename T, typename U> struct _vector : std::vector<U> { typedef std::vector<U> base; ... }; ... I think this is very easy to implement, cleaner and much more flexible (can use vectors and no container can be forgotten). My brain kernel example already needs something similar extensively..." Thanks, -Phil