Saving a map

[Michael]

Hi, I have a map and I want to save it to disk. What is the most efficient
method of doing this?
As i understand it, maps are stored as a binary tree. Is it balanced or is
this implementation dependant?
My first thoughts were to iterate through all the entries and just output
the string and number to a text file, but when its read in again, if it's
balanced then its going to have to do an awful lot of rebalancing as items
are re-added!
Regards

Michael

typedef unsigned long int BigNumber;
map<string,BigNumber> wordList;

 

[Ian]

Hi, I have a map and I want to save it to disk. What is the most efficient
method of doing this?
As i understand it, maps are stored as a binary tree. Is it balanced or is
this implementation dependant?
My first thoughts were to iterate through all the entries and just output
the string and number to a text file, but when its read in again, if it's
balanced then its going to have to do an awful lot of rebalancing as items
are re-added!

So what? I'm sure your processor is faster than your drive.

If you iterate through the map, the contents will be in sorted order.

Do the simplest thing that can possibly work.

Ian

 

[Phil Staite]

As Ian says, do it simple first. Don't prematurely optimize - you don't
even know (do you?) if the rebalancing on loading (from sorted keys)
will be a factor. As Ian says, disk IO will probably be much slower
than your CPU... If you don't *know* it is a problem, don't try to fix
it. Profile first.

If load time does become a factor, you could try something like
iterating through the map, saving off your string keys to a vector.
Perform a random shuffle on the vector, then iterate through it, saving
the string and the looked-up value from the map. However, with the
extra expense of copying N strings, shuffling N strings, then doing N
lookups on the map to get the keys... I'd have a hard time believing
that could be more efficient than letting the tree rebalance itself.

 

[Jesper Madsen]

If there is a problem with speed, I would fix it when loading the data
instead. Reading the data as one big chunk, accepting them as being sorted.
Then do an algorithm that would help with the balancing e.g. setting the top
of the tree first, and then throw in the rest, but do not overengineer....