Ist std :: string size () ein O (1) Betrieb?

Question

Ist std :: string size () ein O (1) -Operation?

Die Umsetzung der STL Ich bin mit der man in VC gebaut ++

Answer 1

Wenn Sie sich fragen, ob MSVC Implementierung von string :: size () konstante Komplexität hat, dann ist die Antwort ja ist. Aber Don Wakefield Tabelle 65 in 23.1 der C ++ Standard-erwähnt, wo es sagt, dass sollte die Komplexität der size() folge in ‚Anmerkung A‘ gesagt. Hinweis A sagt:

  

Diese Einträge markiert ‚‚(Anmerkung A)‘‘   konstante Komplexität soll.

Doch das bedeutet nicht, dass diese Einträge ist konstante Komplexität haben. Standards verwenden sehr spezifische Terminologie, und „sollte“ bedeutet, dass es nicht zwingend notwendig ist.

‚Anmerkung A‘ wurde dem Standard hinzugefügt speziell diejenigen zu beruhigen, die die size() glaubte sollte lineare Komplexität haben darf, damit es nicht notwendig wäre, um die Größe zu halten, wenn die Behälter verändert wurden.

So können Sie nicht auf size() mit konstanter Komplexität verlassen können, aber ich bin ehrlich gesagt nicht sicher, ob es irgendwelche Implementierungen, die keine konstante string::size() haben.

Answer 2

Hier ist eine einfache Möglichkeit, diese Frage für msvc zu beantworten ++.

einige Codes in einem Projekt schreiben:

string happy;
happy.size();

HiLight den .Size Aufruf der rechte Maustaste, um Definition gehen.

Auf meinem installieren (vs2005sp1) diese schickt mich zu xstring: 1635, die wie folgt aussieht:

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

So sieht es aus wie die Zeichenfolge ein Element namens _Mysize, und es ist nur, dass die Rückkehr.

Mit anderen Worten, dies ist ein O (1) Umsetzung.

Answer 3

Ja, std :: string :: size () ist O (1).

Answer 4

Siehe Tabelle 65 in Abschnitt 23.1 des Standard. „A.size ()“ als „(Anmerkung A)“ aufgeführt, die besagt, dass „Diese Einträge ... sollte konstant Komplexität haben“.

Abschnitt 21.3 besagt, dass Zeichenketten an die Anforderungen einer Folge (23.1) entsprechen, ipso facto, Größe () konstant Zeit.

Answer 5

Für eine Zeichenfolge, die size() Betrieb hat als konstant für alle String-Implementierungen, die nicht verwenden Seile ⁽¹⁾ . Es gibt keine explizite Anforderung in der Norm, die den Betrieb erfordert O(1) werden, in der Nähe ist die allgemeine Anforderung, dass size() sollte konstante Zeit sein, aber das läßt Raum für andere Komplexität Maßnahme.

Warum muss es O (1)?

Dies ergibt sich aus der Tatsache, dass die Größe nicht von den Inhalt der Zeichenfolge selbst berechnet werden. Während in C Sie einen NUL Terminator verwenden Sie das Ende der Zeichenfolge, in C ++ NUL ist genauso gültig wie jedes andere Zeichen in der Zeichenfolge zu bestimmen. Da die Größe der Zeichenfolge kann nicht aus dem Inhalt berechnet werden ⁽²⁾ , muss es von außen behandelt werden, unabhängig von der tatsächlichen Größe des Strings.

⁽¹⁾ C ++ 03-Standard ermöglicht eine Implementierung verwenden Seile als Implementierung für Streicher, aber die Tatsache ist, dass keines der aktuellen Implementierungen des Standards Bibliotheken verwenden sie.

⁽²⁾ Wenn die Implementierung Seile verwendet, könnte der Betrieb von der Größe abhängt mittels der Anzahl von Blöcken, aus denen das Seil konstruiert wurde, wenn die Blöcke durch eine verknüpfte Liste verknüpft wurden, oder ähnliche konstruieren, oder wenn sie unterschiedliche Größen haben durften. Aber Seile sind nicht in jeder Standard-Bibliothek-Implementierung verwendet, die ich kenne.

Answer 6

Die Leistung wird von der STL garantiert mindestens O (N) für Behälter, aber viele Container mit std :: string seinem dies als O implementieren kann (1) und wird. Normalerweise wird es entweder zurückgeben eine einfache Variable oder etwas tun, wie _end -. _Begin und zurück, dass

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

So ist es schließlich so sein könnte, aber man kann nie sicher sein.