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 Essential Tools Module 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 (count) of items currently in the collection.t is the size of one item in the collection (which could be a pointer).M is the current size of the collection, in bytes (for example, M = N x t).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 a 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 differ radically among various implementations. However, it is generally true that a heap allocation (or deallocation) that translates to a system call is more expensive than most of the other constant costs. “Amortized” cost is averaged over the life of the collection. Any individual action may have a higher or lower cost than the amortized value.
