Quali sono le garanzie di complessità dei contenitori standard?

Apparentemente 😉 i contenitori standard forniscono qualche forma di garanzia.

Che tipo di garanzie e quali sono esattamente le differenze tra i diversi tipi di contenitori?

Lavorando dalla pagina SGI (su STL ) ho trovato questo:

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) 

Ho trovato la bella risorsa Contenitori standard di C ++ . Probabilmente questo è quello che tutti voi cercate.

VETTORE

Costruttori

 vector v; Make an empty vector. O(1) vector v(n); Make a vector with N elements. O(n) vector v(n, value); Make a vector with N elements, initialized to value. O(n) vector v(begin, end); Make a vector and copy the elements from begin to end. O(n) 

di accesso

 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) 

modificatori

 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) 

Per altri contenitori, fare riferimento alla pagina.

Non sono a conoscenza di qualcosa di simile a un singolo tavolo che ti consente di confrontarli tutti in un colpo d’occhio (non sono sicuro che un tavolo simile sarebbe addirittura fattibile).

Ovviamente il documento standard ISO enumera dettagliatamente i requisiti di complessità, a volte in varie tabelle piuttosto leggibili, altre volte in punti elenco meno leggibili per ciascun metodo specifico.

Anche il riferimento alla libreria STL all’indirizzo http://www.cplusplus.com/reference/stl/ fornisce i requisiti di complessità laddove appropriato.