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(1)
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)

Viscose

Start here: STL Complexity Specifications. Then read through all the container types on that site, and look at the complexity requirements stated. Hope this helps! – Engenia

Can I have a copy of your working to study in my class ? – Typeface

A good summary of the STL operations is provided on page Standard C++ Containers. – Worms

@MartinYork That link is now dead. – Icarian

john-ahlgren.blogspot.com/2013/10/… Just have a look here :) – Surefire

What is O(n) for size()? on the first column of the table? :) I mean it's a bit contradictory with this: Always O(1): begin(), end(), empty(), size(), push_back() The following operations are always O(1) when they exist: from john-ahlgren's web-site – Chaffin

@NüsratNuriyev That is Big-O notation. It is a measure of complexity/size in relation to the source. O(n) means the size is related to the source size. O(1) means the size is constant and not related to source size. O(ln(n)) means the size is related to the log of the source size (ie much smaller than the source size). – Viscose

Thanks but I understand what is Big O :) why size() method is O(1) there: john-ahlgren.blogspot.com/2013/10/… and here is O(n), it's a type, that's what I am talking about. in all sites size method is O(1), beecause, probably, it's cached in the library's implementation – Chaffin

@NüsratNuriyev Probably a typo. I am pretty sure all containers have O(1) on size() method. Fixed. – Viscose

related: github.com/gibsjose/cpp-cheat-sheet/blob/master/… – Psalter

Answer 1

I found the nice resource Standard C++ Containers. Probably this is what you all looking for.

VECTOR

Constructors

vector<T> v;              Make an empty vector.                                     O(1)
vector<T> v(n);           Make a vector with N elements.                            O(n)
vector<T> v(n, value);    Make a vector with N elements, initialized to value.      O(n)
vector<T> 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.

Rattlepate

Answer 2

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.

Jaramillo

The information at cplusplus.com is out-of-date (and sometimes mistaken). Please refer people to en.cppreference.com/w/cpp/container instead. Every method of every container has its mandated complexity listed. – Background

Answer 3

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

Volz