On Feb 20, 2005, at 10:21 AM, JOAQUIN LOPEZ MU?Z wrote:
1.4. Usual implementations use one pointer per bucket, whereas Boost.MultiIndex has two pointers per bucket. This addresses potential> performance problems of insert() and erase() under low load conditions, as discussed in http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf issue 6.14. Is this convenient?
Well it's not unreasonable, you need what you need.
BTW, have you read the committee's resolution to this issue? It doesn't make any sense to me (Bill Wade's concern, OTOH, seems very rasonable.)
Imho the committee's resolution is quite logical. The hash containers exist for one reason: As an optimized solution, in both memory consumption and speed, compared to the tree-based containers. The speed department especially concerns lookup, insert and erase (in that order), but not iteration (there are other containers which optimize iteration, vector being the extreme example). The coder who carefully tunes his hash function and loading will be rewarded with significant optimization. The coder who doesn't, may be presented with a solution that performs worse than the tree-based containers, and is better off sticking with the O(Log N) solution. Imho, the committee should do absolutely nothing to penalize the coder who has carefully tuned his hash function and loading, either in memory consumption nor speed. Of course if hash container writers would like to add safeguards which may also add such overhead, I see little rationale for the committee to object to that either. Doubling the per element storage overhead for a perfect distribution with a loading of 1 is a serious hit in the memory consumption department, and may well lead to a performance hit due to more L2 cache misses. Adding bidirectional iteration, again at the cost of doubling the per element overhead in a well tuned application makes little sense to me. The container is unordered. When you iterate in the forward direction, you access the elements in a generally unpredictable, unordered order. What motivation is there (motivation high enough to double per element overhead), to iterate in the reverse of the generally unpredictable, unordered order? Again, I have no wish for the committee to outlaw such hash containers. But I strongly feel that neither should they outlaw the more traditional hash container design which favors uncompromising performance when everything is tuned just right. -Howard