home *** CD-ROM | disk | FTP | other *** search
/ Borland Programmer's Resource / Borland_Programmers_Resource_CD_1995.iso / code / stl / read.me < prev    next >
Encoding:
Text File  |  1995-05-19  |  4.9 KB  |  94 lines
  1. NOTICE:
  2.  
  3. (1) STL is the container, iterator, algorithm part of the C++ standard 
  4.     library, it is not the complete standard library. (I/O streams, strings,
  5.     etc. are not included in this package.)
  6.  
  7. (2) Minor changes to the STL is expected during the completion of the standard.
  8.  
  9. (3) The allocator files (defalloc.h, faralloc.h, hugalloc.h, lngalloc.h and
  10.     neralloc.h) in the package are sample files. They are not designed for
  11.     any specific machine and compiler system. For example, the assumption that
  12.     type size_t and type ptrdiff_t used in the default allocator are of the 
  13.     same size, it is not true with Borland compiler. Each compiler vendor 
  14.     has to supply their own allocation files to support the machine models 
  15.     they deal with.
  16.  
  17.  
  18. This release (dated February 7, 1995) is a bug fix release with noticeable
  19. changes in associative container implementation. A change note is attached at
  20. the end of this file.
  21.  
  22. The postscript files of the document doc.ps and docbar.ps (with change bars
  23. from the previous version) should print on both US letter and A4 page sizes.
  24.  
  25. The code difference from the previous version (December 6, 1994) is in
  26. file files.dif.
  27.  
  28. -------------------------------------------------------------------------
  29. --- by D. Musser (musser@cs.rpi.edu)
  30.  
  31.      Changes to the HP implementation of STL associative containers
  32.  
  33. The purpose of these changes is to improve the performance of certain
  34. operations on STL associative containers.  Empirical tests of the
  35. performance have been made in all cases and they mostly confirm that
  36. times are improved, although in one case (the find operation, see
  37. item 3) the tests are ambiguous and more testing should be done.  The
  38. revisions to the internal class rb_tree affect the corresponding
  39. operations in all of the user-level associative classes (set,
  40. multiset, map, multimap).  The files affected are tree.h, set.h,
  41. multiset.h, and projectn.h.
  42.  
  43. 1. The copy constructor and operator= for class rb_tree are revised to
  44. use a private function __copy that does a structural copy rather than
  45. creating the new tree using insertions.  This substantially speeds up copying
  46. and assignment since no comparisons or tree balancing need to be done.
  47.  
  48. 2. The erase operation for rb_tree now checks for the case that the
  49. entire tree is being erased, and in that case does the erasure by a
  50. simple pre-order traversal of the tree.  This speeds up erasure since
  51. there is no need for any of the tree balancing that happens when nodes
  52. are erased one by one.
  53.  
  54. 3. The search operations, find, lower_bound, and upper_bound, in
  55. rb_tree have been revised. The find operation searches all the way
  56. down to a leaf node, using a single comparison at each level of the
  57. tree.  Formerly it used two comparisons on each level at which the
  58. first comparison was false.  The old algorithm was simple and would
  59. detect a match with fewer comparisons in some cases, because the match
  60. was detected at an interior node, but the average number of
  61. comparisons is lower with the revised algorithm.  However the new
  62. algorithm has to climb back up in the tree and the overhead of doing
  63. so offsets some of the savings from doing fewer comparisons.  The
  64. revised algorithm is now basically the same as is used (and was
  65. already used) in lower_bound and upper_bound.  The algorithms for
  66. lower_bound and upper_bound have also been revised slightly, to
  67. eliminate one extra comparison they were doing.
  68.  
  69. 4. The algorithm for insert(const value_type&) is similarly revised to
  70. search all the way down to a leaf node using a single comparison at
  71. each level; the old algorithm was similar to the old algorithm for
  72. find.  The new algorithm is similar to that of upper_bound.  Basing it
  73. on upper_bound rather than lower_bound results in a stability property
  74. when associative containers are used to sort (by starting with an
  75. empty container, inserting values, then traversing through the
  76. container with an iterator): items that compare equal keep the
  77. relative order in which they were inserted.
  78.  
  79. 5. The set and multiset implementations are revised to eliminate the need
  80. to use singleton<const Key> as their value_type.  Using singleton worked
  81. correctly but had the performance drawback of an extra call to the
  82. copy constructor for type Key when creating a singleton<const Key>
  83. value.  In the new version the value type is just Key, and changes to
  84. Key via *i = ...  are prevented by defining both iterator and
  85. const_iterator as the const_iterator type for the underlying red-black
  86. tree class.  This requires a few type coercions, but actually fewer
  87. than when singleton was used.  Thanks to Fabrice Clerc for pointing
  88. out the copy-constructor problem with singleton.  (Mr. Clerc also
  89. points out that there is a related problem with map and multimap
  90. caused by using pair<const Key, T> as value_type, but so far I don't
  91. see a way of avoiding the problem without changing the interface to
  92. include an insert operation with separate Key and Value arguments.)
  93.  
  94.