RE: [Algorithms] fundamentally better containers
Brought to you by:
vexxed72
From: Bretton W. <bre...@mi...> - 2001-07-30 16:50:08
|
> malloc()/realloc() has, except now the container is in charge of > determining > how much slop to use, rather than the memory allocator(*). One could argue > that the container knows more than the allocator about how much slop might > be needed. The ideal amount of "slop" for unknown circumstances is to double the size of the buffer each time you need to grow. Allocator performance is then log n. The last STL implementation I actually slogged through (not a recommended practice for the weak of heart) did this up to a point. I see lots of "grow by size m" algorithms in practice, which is linear, but may save you some memory, especially as the vector gets large. > Also, while binary search on a sorted array is fast, insertion is really > slow, and the map<> template is guaranteed to have O(n log n) insertions, > deletions and searches. If you need a binary sorted array, the STL I believe that Charles was referring to the cache coherent behavior of sorted arrays, and not strictly limiting himself to the complexity of the algorithm. Insertion sort is still pretty fast in this situation, although I would hesitate on large arrays. -- Noz Moe King (aka Bretton Wade)=20 |