Enhanced alternative to 'std::set' or 'std::map'. More...

Enhanced alternative to 'std::set' or 'std::map'.

Author: H. Carter Edwards hcedw.nosp@m.ar@s.nosp@m.andia.nosp@m..gov

Date: November 2006

The 'Setv' alternative to the 'std::set' or 'std::map' template classes allows explicit memory management of the members of the container and provides a significantly reduced code-footprint for the implementation. Explicit memory management may be advantageous in complex data structures that have members with large memory requirements or pointers to members.

Acknowledgements:

Most all of the algorithms in this class were obtained from the Hewlett-Packard source for the Standard Template Library, thus the inclusion of Hewlett-Packard's copyright notice.

Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Hewlett-Packard Company makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.

Red-black tree class, designed for use in implementing STL associative containers (set, multiset, map, and multimap). The insertion and deletion algorithms are based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), except that

(1) the header cell is maintained with links not only to the root but also to the leftmost node of the tree, to enable constant time begin(), and to the rightmost node of the tree, to enable linear time performance when used with the generic set algorithms (set_union, etc.);

(2) when a node being deleted has two children its successor node is relinked into its place, rather than copied, so that the only iterators invalidated are those referring to the deleted node.