HP Integrity NonStop J-Series - Manual (Page 301)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Time and Space Considerations
This section presents a very approximate analysis and comparison of the time and space
requirements for a variety of common operations on different specific collections and collection
families. We've presented the information as a set of tables that lists the operation, the time cost
and the space cost. Any applicable comments appear at the bottom of the table. A key to the
abbreviations used in the tables appears at the bottom of each page.
As you read these analyses, keep in mind that various processors, operating systems,
compilation optimizations, and many other factors will affect the exact values. The point of
these tables is to provide you with some idea of how the behaviors of the various collections
will compare, all other things being equal. For more details on algorithm complexity, refer to
Knuth, Sedgewick, or any number of other books.
Because many of the Tools.h++ collections have essentially similar interfaces, it is easy to
experiment and discover what effect a different choice of collection will have on your program.
For each of the following tables:
N is the number of items in the collection; ●
M is the current size of the collection; ●
t is the size of the item being stored (possibly a pointer); ●
i is the size of an integer; ●
p is the size of a pointer ●
C is a "constant value". ●
Time costs for each pointer dereference, copy, destroy, allocate, or comparison are
considered equal. ●
Container overhead is as space cost that consists of two terms. The left term is the size of
an empty container, while the right term shows the added cost for N items. ●
Space cost is indicated both for insertions and deletions. Space cost that is marked
"(recovered)" indicates that the space has been handed back to the heap allocator. ●
Whenever an allocation is mentioned, you should be aware that memory allocation policies