5
So che lo standard specifica che è per i vettori, ma per quanto riguarda le stringhe?In C++, la complessità ammortizzata di std :: string :: push_back() O (1)?
A
risposta
5
Sì, è tempo di ammortamento costante. Vedere la tabella a pagina 101 716 of this document:
Tabella 101 elenca le operazioni che vengono forniti per alcuni tipi di contenitori di sequenza ma non altri. Un'implementazione deve fornire queste operazioni per tutti i tipi di contenitori mostrati nella colonna "container" e li deve implementare in modo da ottenere un tempo costante ammortizzato.
Operation | Description | Container
---------------+----------------------+----------------------------------
a.push_back(t) | Appends a copy of t. | basic_string, deque, list, vector
Problemi correlati
- 1. La complessità ammortizzata in parole povere?
- 2. C++ std :: complessità unordered_map
- 3. Complessità di std :: find_end come Big-O
- 4. Complessità di std :: conteggio
- 5. std :: forward_list e std :: :: forward_list push_back
- 6. Complessità di std :: list :: splice e altri contenitori di elenchi
- 7. Perché la complessità spaziale di questo algoritmo è O (1)
- 8. È std :: string :: npos == -1 sempre vero?
- 9. prestazioni std :: strstr vs. std :: string :: trovare
- 10. vector C++ push_back
- 11. C++ stringa :: trovare la complessità
- 12. C++ std :: string su booleano
- 13. Converti float in std :: string in C++
- 14. Cython C++ e std :: string
- 15. Ottieni byte da std :: string in C++
- 16. Usando sprintf con std :: string in C++
- 17. C++ .NET converti System :: String in std :: string
- 18. Come trasformare System :: String^in std :: string?
- 19. È consentito std :: vector :: push_back di lanciare per qualsiasi ragione diversa dalla riallocazione o costruzione fallita?
- 20. Differenza tra std: string e std :: string
- 21. std :: string o std :: vector per conservare i dati grezzi
- 22. C++ 11 rappresentazione std :: string interna (libstdC++)
- 23. complessità ciclomatica = 1 + affermazioni #if?
- 24. nessuna funzione di corrispondenza per la chiamata a std :: vector <std::tuple> push_back
- 25. Confrontando carattere letterale di std :: string in C++
- 26. Ottieni il tipo da std :: string, C++
- 27. C++ È uno std :: string un contenitore?
- 28. Algoritmo per l'eliminazione di un elemento in una sola lista collegata con O (1) la complessità
- 29. Come ottenere la cancellazione O (1) da una lista std ::
- 30. Definire std :: string in C++ senza caratteri di escape
Certo, ma io non ho accesso allo standard in questo momento, da qui la domanda. – Ari