Alex Rivera | Logout

Are recursive types really the only way to build noncontinuous arbitrary-size data structures?

Asked 2012-08-24T16:40:42.117
8

I just noticed a question asking what recursive data types ("self-referential types") would be good for in C++ and I was tempted to boldly claim

It's the only way to construct data structures (more precisely containers) that can accept arbitrary large data collections without using continuous memory areas.

That is, if you had no random-access arrays, you would require some means of references (logically) to a type within that type (obviously, instead of having a MyClass* next member you could say void* next but that would still point to a MyClass object or a derived type).

However, I am careful with absolute statements -- just because I couldn't think of something doesn't mean it's not possible, so am I overlooking something? Are there data structures that are neither organised using mechanisms similar to linked lists / trees nor using continuous sequences exclusively?

Note: This is tagged both and as I'd be interested specifically in the C++ language but also in theoretical aspects.

c++ data-structures language-agnostic
Edit
Report

1 Answer

2

The problem is that the dynamic allocator itself is managing contiguous storage. Think about the "tape" used for a Turing Machine, or the Von Neumann architecture. So to seriously consider the problem, you would likely need to develop a new computing model and new computer architecture.

If you think disregarding the contiguous memory of the underlying machine is okay, I am sure a number of solutions are possible. The first that comes to my mind is that each node of the container is marked with an identifier that has no relation to its position in memory. Then, to find the associated node, all of memory is scanned until the identifier is found. This isn't even particularly inefficient if given enough computing elements in a parallel machine.

answered 2012-08-24T17:00:30.507

Your Answer