Quelle est la complexité de la fonction membre std::ssortingng::substr
? Est-ce défini par standard ou par implémentation?
Une implémentation naïve serait O (k) où k est la longueur de la sous-chaîne résultante. std :: ssortingng ne supporte pas la copie sur écriture. Si vous voulez des opérations de sous-chaîne O (1), utilisez une structure de données telle qu’une corde .
La norme C ++ 11 ne définit pas les caractéristiques de performance de substr
, que ce soit dans 21.4.7.8 ou ailleurs. En pratique, vous pouvez presque certainement vous attendre à une performance de O(n)
, n
étant la longueur du résultat.
C’est tout ce que la norme a à dire à ce sujet:
n3242, 21.4.7.8
- Requiert:
pos <= size()
out_of_range
:out_of_range
sipos > size()
- Effets: Détermine la longueur
rlen
de la chaîne à copier en tant que plus petit den
et desize() - pos
- Retourne:
basic_ssortingng
.(data()+pos,rlen)
Donc, la réponse serait non, la complexité n’est pas définie.
EDIT: corrigé selon n3242, pos> taille non pos> = taille