abstract containers: does such a thing exist, conceptually?

From: Piotr Sawuk (piotr5_at_unet.univie.ac.at)
Date: 12/26/04 

Date: 26 Dec 2004 02:00:28 GMT

Mainly I'm curious about languages other than c++, and what concepts
similar to c++'s "list" they do have to offer. The standard pattern
is obvious: A list is something which takes care of pointers to which
data is appended, so that removal of one such node does lead to linking
of the previous node's pointer to the next node and the other way
around. Does any programming-language or lib offer the re-use of the
code implementing that pattern? In my experience c++'s STL does not.

I'm planning to write a c++-template-class which is supposed to work
exactly like a STL-container, except that data contained therein does
not neccessarily need to be owned by the base-class alone. What STL is
missing is extensibility and code-reuse of its List-class, and that's
what I wish to add. My idea is to implement each list-node as a struct
of one fix-sized array of node-pointers and the actual data, and to
add template-parameters to the actual list-template which define the
iteration-behaviour of the list -- but I also could implement a node
as a class derived from another node thereby extending that node's
behaviour by the additional pointers. Those iteration-classes also
need to be asked about the removal-behaviour of the stored objects,
so that the user could derive his own objects by inheriting from
this class and adding some container or stream of his own choice
whithin which the list-nodes will get stored. The purpose is:

1)vector of nodes: Depending on which iterator does get used the
new objects get appended to the vector or replace some stored
object or existing objects get cross-linked somewhere within
the list or combinations of those 3 possibilities. The list's
iterators could have the ability to traverse the whole vector,
or they could form (maybe even circular) sub-lists within the
vector. Removing through a list-iterator could either remove
the object within the vector too, or it could merely remove
some links between those object-nodes and leave the vector
untouched. Adding or removing through one iterator could also
trigger adding- or removing-operations of other iterators...

2)graph = list of lists: The same as above but with its own allocator
and object-storage, except that there needs to exist an iterator
which does walk through all nodes. Even though each node does only
have a fixed amount of links to other nodes, there is no limitation
of the amount of possible sub-lists within that graph. Whenever a
node gets added the user somehow needs to inform the compiler which
other nodes should get connected to it. Note that unlike to a real
graph here the edges do have a "direction" in addition to the actual
edge-direction already provided by the pointer. The nodes do have an
array and not a set of pointers to other nodes, thereby each such
pointer does have a number! The iterators could have derived objects
which act exactly like their parents except that at some points of
the iteration other iterators than the type used for input could get
returned while stepping through them (for example a deque would then
simply be a list of arrays where sometimes the iterator does jump
inside of the array-data and start acting as an array-iterator, and
sometimes that array-iterator does again yield the list-iterator as
its next element). The idea is that the whole iterator-programming
should be done through templates without the need to write any line
of code in most cases, and if neccessary the code should get written
into a so-called iterator-traits class which could get re-used lateron
for completely different iterators...

So, did anyone ever hear of such a thing? Apart from the apparent
use of a traits-class, is there any kind of pattern or something
I could use for that project? Is there any Open-Source project
making heavy use of writing programs from within template-parameters,
so that I could learn more about the possibilities lying therein?
How could I platform-independantly translate a node containing
another node as its object into a node with a pointer-array which
does have access to all those pointers? Is it possible to create
a super-class which contains an union of 2 equal-sized objects
and transfers calls to those object's common methods to the actual
method apropriate for the currently stored object? Does there exist
a programming-language where this would be possible? What other
languages apart of c++ do offer statical (compile-time) OOP of
program-instructions (just like c++'s bind-template), thereby
allowing for an implementation of my idea in those languages? 

-- 
Better send the eMails to netscape.net, as to
evade useless burthening of my provider's /dev/null...
before complaining because of my rudeness, read
http://www.unet.univie.ac.at/~a9702387/en/adl/liar-faq.txt
and killfile me...
P

Relevant Pages

  • Re: question about True values
    ... Not all empty objects have zero length, or even a length at all. ... example, iterators. ... lists, but the "if a:" doesn't work for them, so it's moot. ...
    (comp.lang.python)
  • Re: Lists and back() Question.
    ... > linked lists, I assumed endwould return NULL. ... Is there an open source STL I ... Iterators are abstractions of pointers. ... Iterators can become invalid when the container changes. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Effective STL Item 4 (size() vs. empty())
    ... >> Any other practical obstacle you have been encountering? ... The Osize leads to an Osplice ... source and destination lists are the same, ... to be able to keep iterators to specific items. ...
    (comp.lang.cpp)
  • Re: Pointer To A Vector Elements While Still Adding
    ... No. list iterators (and you really should be using iterators, not pointers, ... Well that's a problem for vectors, but not for lists. ... lists do not (each node stores the address of the ...
    (comp.lang.cpp)
  • Re: very strange pthread problem
    ... The worker threads need access to a class member function or two. ... STL vector so each index into the vector points to the list of pointers ... it's just storing the pointers to the STL lists and the vector ... Then I moved the whole thing to a single cpu Linux ...
    (comp.programming.threads)
Loading