Professional C++ by Marc Gregoire
Author:Marc Gregoire
Language: eng
Format: epub, pdf
ISBN: 9781118858134
Published: 2014-08-20T00:00:00+00:00
Summary of STL Containers
The following table summarizes the containers provided by the STL. It uses the big-O notation introduced in Chapter 4 to present the performance characteristics on a container of N elements. An N/A entry in the table means that the operation is not part of the container semantics.
CONTAINER CLASS NAME CONTAINER TYPE INSERTION PERFORMANCE DELETION PERFORMANCE LOOKUP PERFORMANCE
vector Sequential Amortized O(1) at end; O(N-p) for an insert at position p O(1) at end; O(N-p) for a delete at position p O(1)
When to Use: Need quick lookup. Don’t mind slower insertion/deletion. Whenever you would use a standard C-style array that should dynamically grow/shrink in size.
list Sequential O(1) once you are at the position where to insert the element O(1) once you are at the position where to delete the element O(N); Statistically O(N/2)
When to Use: Need quick insertion/deletion. Don’t mind slower lookup.
forward_list Sequential O(1) once you are at the position where to insert the element O(1) once you are at the position where to delete the element O(N); Statistically O(N/2)
When to Use: When you need the benefits of a list but require only forward iteration.
deque Sequential Amortized O(1) at beginning or end; O(min(N-p, p)) for an insert at position p O(1) at beginning or end; O(min(N-p, p)) for a delete at position p O(1)
When to Use: Not usually needed; use a vector or list instead.
array Sequential N/A N/A O(1)
When to Use: When you need a fixed-size array to replace a standard C-style array.
queue Container Adapter Depends on the underlying container; O(1) for list, amortized O(1) for deque Depends on the underlying container; O(1) for list and deque N/A
When to Use: When you want a FIFO structure
priority_queue Container Adapter Depends on the underlying container; amortized O(log(N )) for vector and deque Depends on the underlying container; O(log(N)) for vector and deque N/A
When to Use: When you want a queue with priority.
stack Container Adapter Depends on the underlying container; O(1) for list, amortized O(1) for vector and deque Depends on the underlying container; O(1) for list, vector and deque N/A
When to Use: When you want a FILO/LIFO structure.
set
multiset Sorted Associative O(log(N)) O(log(N)) O(log(N))
When to Use: When you want a sorted collection of elements with equal lookup, insertion, and deletion times.
map
multimap Sorted Associative O(log(N)) O(log(N)) O(log(N))
When to Use: When you want a sorted collection to associate keys with values with equal lookup, insertion, and deletion times.
unordered_map
unordered_multimap Unordered associative / hash table Average case O(1); worst case O(N) Average case O(1); worst case O(N) Average case O(1); worst case O(N)
When to Use: When you want to associate keys with values with equal lookup, insertion, and deletion times and don’t require the elements to be sorted. Performance can be better than with a normal map but that depends on the elements.
unordered_set
unordered_multiset Unordered associative / hash table Average case O(1); worst case O(N) Average case O(1); worst case O(N) Average case O(1); worst case O(N)
When to Use: When you want a collection of elements with equal lookup, insertion, and deletion times and don’t require the elements to be sorted.
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Hello! Python by Anthony Briggs(9928)
OCA Java SE 8 Programmer I Certification Guide by Mala Gupta(9804)
The Mikado Method by Ola Ellnestam Daniel Brolund(9787)
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(8310)
Sass and Compass in Action by Wynn Netherland Nathan Weizenbaum Chris Eppstein Brandon Mathis(7792)
Test-Driven iOS Development with Swift 4 by Dominik Hauser(7773)
Grails in Action by Glen Smith Peter Ledbrook(7705)
The Well-Grounded Java Developer by Benjamin J. Evans Martijn Verburg(7568)
Windows APT Warfare by Sheng-Hao Ma(6959)
Layered Design for Ruby on Rails Applications by Vladimir Dementyev(6690)
Blueprints Visual Scripting for Unreal Engine 5 - Third Edition by Marcos Romero & Brenden Sewell(6558)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(6426)
Kotlin in Action by Dmitry Jemerov(5076)
Hands-On Full-Stack Web Development with GraphQL and React by Sebastian Grebe(4323)
Solidity Programming Essentials by Ritesh Modi(4066)
Functional Programming in JavaScript by Mantyla Dan(4044)
WordPress Plugin Development Cookbook by Yannick Lefebvre(3860)
Unity 3D Game Development by Anthony Davis & Travis Baptiste & Russell Craig & Ryan Stunkel(3803)
The Ultimate iOS Interview Playbook by Avi Tsadok(3779)
