Avoid prev/next pointers on a really big list?

Aug 28, 2012 at 4:09pm
I want a std::list<Node> with 10(at least) to 4000000000(at ambitious) elements.
sizeof(Node)=24.

Standard allocator works with one new per element, and prev_element, next_element pointers per element.
I don't know, for every allocation, if new implementantion waste memory bytes for internal reasons, but 2 pointers per element is a big waste of memory.

One more restriction is that Node* will be referenced from other (many) structures (so a vector which reallocates is a little bit mess).

Because I don't want to delete, 'gui-deleted' elements for UNDO reasons, I want to create my allocator with bigger allocated blocks:

I think something like a modified list of fixed length arrays of Node. Forward and backward pointers of list will only apply on fixed length arrays. Not on elements inside them.

Your opinion?
Aug 28, 2012 at 5:11pm
I want a std::list<Node> with 10(at least) to 4000000000(at ambitious) elements.
sizeof(Node)=24.


4 billion bytes is about 3.7 gigs. Times that by the size of your node, and you'll see that you don't have enough RAM to do that.

std::list takes care of the Node part for you, so all you need to give it is the object itself. You could also have the std::list store pointers to your object to reduce the amount of the stack that you use.
Aug 28, 2012 at 5:59pm
Maybe a disc based random access db such as Berkeley DB

http://en.wikipedia.org/wiki/Berkeley_DB

or sqlite

http://www.sqlite.org/

might be the way to go?
Topic archived. No new replies allowed.