Complexity of Some STL Container Operations
"Element insertion and removal" refers to insertion and removal of a single element.
std::vector
- element access by position index: constant time
- element insertion and removal at end position: amortized constant time
- element insertion and removal at any other position: proportional to current size, on average
std::list
- element access by position in sequence: proportional to distance of element from head node
- element insertion and removal at any position: constant time
std::deque
- element access by position index: constant time
- element insertion and removal at begin position: amortized constant time
- element insertion and removal at end position: amortized constant time
- element insertion and removal at any other position: proportional to current size, on average
std::set
- element lookup with std::set::find: proportional to log(N), where N is the current size
- element insertion and removal: proportional to log(N), where N is the current size
std::map
- key lookup with std::map::find: proportional to log(N), where N is the current size
- key-value pair insertion and removal: proportional to log(N), where N is the current size
