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

set associative container c++

Question

Aparentemente ;-) 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 la página de SGI (sobre STL ) he encontrado 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  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)

Answer 1

Comience aquí: Especificaciones de Complejidad STL . Luego lea todos los tipos de contenedores en ese sitio y observe los requisitos de complejidad establecidos.

¡Espero que esto ayude!

Answer 2

Encontré el buen recurso Estándar C ++ Contenedores . 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)

Accesorios

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.

Answer 3

No conozco nada como una sola tabla que te permita compararlos todos 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.

Además, la referencia de la biblioteca STL en http://www.cplusplus.com/reference/stl/ proporciona los requisitos de complejidad cuando corresponde.

Answer 4

Se proporciona un buen resumen de las operaciones de STL en la página Contenedores estándar de C ++ .