What are the complexity guarantees of the standard containers

Question

Apparently  -  the standard containers provide some form of guarantees   What type of guarantees and what exactly are the differences between the different types of container   Working from the SGI page  about STL  I have come up with this   Container Types                   Container      Forward Container         Reverse Container             Random Access Container     Sequence         Front Insert Sequence         Back  Insert Sequence     Associative Container         Simple   Associative Container         Pair     Associative Container         Sorted   Associative Container         Multiple Associative Container  Container Types mapped to Standard Containers                                                std  vector     Sequence    Back        Sequence                    Forward Reverse Random Container std  deque      Sequence    Front Back  Sequence                    Forward Reverse Random Container std  list       Sequence    Front Back  Sequence                    Forward Reverse Container std  set        Sorted Simple Unique    Associative Container       Forward Container std  map        Sorted Pair Unique      Associative Container       Forward Container std  multiset   Sorted Simple Multiple  Associative Container       Forward Container std  multimap   Sorted Pair Multiple    Associative Container       Forward Container   Container Guarantees                                                                                                           Simp                                                                                   or                           For   Rev  Rand        Front  Back  Assoc        Sort   Mult                     Cont  Cont  Cont Cont  Sequ  Sequ   Sequ  Cont         Cont   Cont  Copy    Const       O n  Fill    Const                              O n  begin               O 1  end                 O 1  rbegin                          O 1  rend                            O 1  front                                      O 1  push front                                       O 1  pop front                                        O 1  push back                                               O 1  pop back                                                O 1  Insert                                                                            O ln n   Insert  fill                               O n  Insert  range                              O n                                    O kln n  n  size                O n  swap                O 1  erase key                                                     O ln n   erase element                                                 O 1  erase range                                                   O ln n  S  count                                                         O log n  k  find                                                          O ln n   equal range                                                   O ln n   Lower Bound Upper Bound                                                    O ln n   Equality                  O n  InEquality                O n  Element Access                       O 1

User · Answer

I m not aware of anything like a single table that lets you compare all of them in at one glance  I m not sure such a table would even be feasible    Of course the ISO standard document enumerates the complexity requirements in detail  sometimes in various rather readable tables  other times in less readable bullet points for each specific method   Also the STL library reference at http   www cplusplus com reference stl  provides the complexity requirements where appropriate

User · Answer

Another quick lookup table is available at this github page  Note   This does not consider all the containers such as  unordered map etc  but is still great to look at  It is just a cleaner version of this

User · Answer

Another quick lookup table is available at this github page  Note   This does not consider all the containers such as  unordered map etc  but is still great to look at  It is just a cleaner version of this

User · Answer

I m not aware of anything like a single table that lets you compare all of them in at one glance  I m not sure such a table would even be feasible    Of course the ISO standard document enumerates the complexity requirements in detail  sometimes in various rather readable tables  other times in less readable bullet points for each specific method   Also the STL library reference at http   www cplusplus com reference stl  provides the complexity requirements where appropriate

User · Answer

I m not aware of anything like a single table that lets you compare all of them in at one glance  I m not sure such a table would even be feasible    Of course the ISO standard document enumerates the complexity requirements in detail  sometimes in various rather readable tables  other times in less readable bullet points for each specific method   Also the STL library reference at http   www cplusplus com reference stl  provides the complexity requirements where appropriate

User · Answer

I m not aware of anything like a single table that lets you compare all of them in at one glance  I m not sure such a table would even be feasible    Of course the ISO standard document enumerates the complexity requirements in detail  sometimes in various rather readable tables  other times in less readable bullet points for each specific method   Also the STL library reference at http   www cplusplus com reference stl  provides the complexity requirements where appropriate

User · Answer

I found the nice resource Standard C   Containers  Probably this is what you all looking for   VECTOR  Constructors  vector lt T gt  v               Make an empty vector                                      O 1  vector lt T gt  v n             Make a vector with N elements                             O n  vector lt T gt  v n  value      Make a vector with N elements  initialized to value       O n  vector lt T gt  v begin  end    Make a vector and copy the elements from begin to end     O n    Accessors  v i           Return  or set  the I th element                         O 1  v at i        Return  or set  the I th element  with bounds checking   O 1  v size        Return current number of elements                        O 1  v empty       Return true if vector is empty                           O 1  v begin       Return random access iterator to start                   O 1  v end         Return random access iterator to end                     O 1  v front       Return the first element                                 O 1  v back        Return the last element                                  O 1  v capacity    Return maximum number of elements                        O 1    Modifiers  v push back value          Add value to end                                                 O 1   amortized  v insert iterator  value   Insert value at the position indexed by iterator                 O n  v pop back                 Remove value from end                                            O 1  v assign begin  end        Clear the container and copy in the elements from begin to end   O n  v erase iterator           Erase value indexed by iterator                                  O n  v erase begin  end         Erase the elements from begin to end                             O n    For other containers  refer to the page

User · Answer

I found the nice resource Standard C   Containers  Probably this is what you all looking for   VECTOR  Constructors  vector lt T gt  v               Make an empty vector                                      O 1  vector lt T gt  v n             Make a vector with N elements                             O n  vector lt T gt  v n  value      Make a vector with N elements  initialized to value       O n  vector lt T gt  v begin  end    Make a vector and copy the elements from begin to end     O n    Accessors  v i           Return  or set  the I th element                         O 1  v at i        Return  or set  the I th element  with bounds checking   O 1  v size        Return current number of elements                        O 1  v empty       Return true if vector is empty                           O 1  v begin       Return random access iterator to start                   O 1  v end         Return random access iterator to end                     O 1  v front       Return the first element                                 O 1  v back        Return the last element                                  O 1  v capacity    Return maximum number of elements                        O 1    Modifiers  v push back value          Add value to end                                                 O 1   amortized  v insert iterator  value   Insert value at the position indexed by iterator                 O n  v pop back                 Remove value from end                                            O 1  v assign begin  end        Clear the container and copy in the elements from begin to end   O n  v erase iterator           Erase value indexed by iterator                                  O n  v erase begin  end         Erase the elements from begin to end                             O n    For other containers  refer to the page

[c++] What are the complexity guarantees of the standard containers?

Examples related to c++

Examples related to stl

Examples related to containers

Examples related to big-o