ajb@spamcop.net writes:
The best implementation is the one that matches the characteristics of your application/data the closest.
Of course, it's usually not obvious what those characteristics are in advance.
There is a data-structure benchmarking kit called "auburn" http://www.cs.york.ac.uk/fp/auburn sadly no longer actively maintained. One of the things it can do is to generate "datatype usage graphs" (dugs) for any given abstract datatype. These record information like the relative proportions of appends,reads,writes, etc. in a particular usage scenario. A series of competing implementations of the abstract datatype can be benchmarked against a series of randomly generated dugs. Furthermore, auburn has an automated decision procedure for deciding which implementation would be best for your application, based on the previous benchmarking. Regards, Malcolm