Thread: Dynamic storage class?

Stacks are highly dynamic. You can insert and remove nodes at will, but stacks are horrible for random access.
Dynamic arrays are great for random access, but inserting or removing a node requires moving a whole lot of data.
Hash tables are also good for random access, but it's not quite like a normal array. If you delete a node, it doesn't automatically 'collapse' the index.

So I'm wondering if there's any sort of class / library available which has a nice balance between dynamicness and random access.

The STL Vector?
http://www.cprogramming.com/tutorial/stl/vector.html

There's going to be some overhead when doing deletions that aren't at the end, but as far I know it's not that bad and is certainly easy to use.

[edit]
3 mins

I'm not exactly sure what Vectors are, but what I can find and understand about them:
Are vectors simply like dynamic arrays, except they allocate in certain size blocks of memory? ex. It allocates in 4k blocks of memory so it's not constantly reallocating? Or is there more to it than that?

It's hard to say what my specific use is, as I won't really use it, I have a different reason for asking:
Currently, I have a concept for data storage. It's dynamic like a stack, but also has a fast random access rate. Inserting and deleting nodes would be no slower than inserting a node into a dynamic array with 10 elements. And if you have 100,000 nodes, it would take, on average, about 40 steps to access any node.
So why do I ask? I just want to be sure nothing like it exists already before I start on it. It will be pretty complicated and a lot of work...

> It will be pretty complicated and a lot of work...
Which is probably why such a beast doesn't exist in wild. Sure you could do it, but it would always have poorer performance compared to the specific data structures which are more tuned to the specific task at hand.

B-Trees are VERY close to the concept I have in mind. One problem though: When you delete an element in a B-Tree, it doesn't seem to collapse the index. In another words, if you delete element '11', it's just an empty slot. It's not like a dynamic array where it will move all the data backwards when you delete an element.
The concept I had in mind is very close to the B-Tree algorithm, except mine will actually collapse the index when you delete an element.

... Please correct me if I'm wrong though.

I read about B-Trees at this link: http://www.semaphorecorp.com/btp/algo.html

Take that concept, but make one major change:
Each node in the tree holds the base of the index. ex: [ 72 84 . .]
My concept doesn't do that though. Mine holds the number of elements in that node instead.
To search for an element, you add the number of elements in each node. Once the number of elements is greater than the index, you know which node your element is in.
When you insert a node, simply insert it at the proper location. Then you go back to each node in the tree, and add +1 to the number of elements.
When you remove a node, you basically do the same, except subtract -1 to the number of elements in each node.

In the end, you get something dynamic like a stack, but with a much faster random access rate.

1)...except mine will actually collapse the index when you delete an element.

2)When you insert a node, simply insert it at the proper location. Then you go back to each node in the tree, and add +1 to the number of elements.

3) When you remove a node, you basically do the same, except subtract -1 to the number of elements in each node.

In the end, you get something dynamic like a stack, but with a much faster random access rate.

You may get faster random access, but with the adjusting you want to do to the other nodes, how is the overall process going to be faster?

I think you could implement an indexed list that could be faster and simpler