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. 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. Whenever an allocation is mentioned, you should be aware that memory allocation policies differ radically among various implementations. Any individual action may have a higher or lower cost than the amortized value. Resize only if told to.