Replying to deba:
I think, the performance improvements of the static maps cannot be significant in any real applications.
They really can be. Just think of a graph which is used by some algorithms, say by just one Dfs, one Dijkstra, and one MinCostArborescense?`. This means we already have 11 nodemaps and 2 arcmaps attached to the graph, not counting the input of these algs. It means the same amount of virtual function calls at each node/arc addition/deletion.
In addition, one solution have to be enough for the concurrent map addition problem,
I try to argue that it isn't.
and I suggest to use only the locking mechanism. It has more advantages:
- This works always when the static map concept works.
- The user should not care about which map should be used in a place.
In fact, he should. If Dijsktra used static map, it was thread-safe out-of-box (because e.g. ListGraph?+static maps were thread-safe). With the locking approach, the default tools were not thread-safe by default, but you have to use a specialized version of the tools.
In my opinion this is the more important reason to choose the locking approach. I think if a user want to write an algorithm for a single threaded program, then he may use normal maps (non static). If he want to reuse the algorithm in a multithreaded program, then he have to intrusively modify his old code.
I consider the following use-case: the user wants to run 8 instances of Dijkstra on the same graph. She don't write any shared data thus don't want to care about locking.
- I think, the implementation of lock based solution is easier also.
It depends if you count with the development and maintenance of the various lock implementations. If you do, than implementing the lock model is far more complex.
