¿Cuáles son las garantías de complejidad de los contenedores estándar?

Question

Al parecer ;-) los contenedores estándar proporcionan alguna forma de garantías.

¿Qué tipo de garantías y cuáles son exactamente las diferencias entre los diferentes tipos de contenedores?

Trabajando desde the SGI page (alrededor STL) que han llegado con esto:

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 Seuqence     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) 

Answer 1

de inicio aquí: STL Complexity Specifications. Luego lea todos los tipos de contenedores en ese sitio y observe los requisitos de complejidad establecidos.

Espero que esto ayude!

Answer 2

No conozco nada como una sola tabla que te permita compararlas todas de una vez (no estoy seguro de que una tabla así sea factible).

Por supuesto, el documento estándar ISO enumera los requisitos de complejidad en detalle, a veces en varias tablas bastante legibles, otras veces en viñetas menos legibles para cada método específico.

También la referencia de la biblioteca STL en http://www.cplusplus.com/reference/stl/ proporciona los requisitos de complejidad cuando corresponde.

Answer 3

Se proporciona un buen resumen de las operaciones de STL en la página Standard C++ Containers.

Answer 4

Encontré el buen recurso Standard C++ Containers. Probablemente esto es lo que todos ustedes buscan.

VECTOR

Constructores

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) 

de acceso de

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) 

Modificadores

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) 

Para otros contenedores, consulte la página.