c++ - null で終了する文字列の根拠は何ですか?

Question

私は C と C++ が大好きですが、null で終わる文字列の選択には頭を悩ませずにはいられません。

• C より前に存在していた長さの接頭辞付き (つまり Pascal) 文字列
• 長さのプレフィックス付き文字列は、一定時間の長さの検索を可能にすることで、いくつかのアルゴリズムを高速化します。
• 長さのプレフィックス付き文字列を使用すると、バッファ オーバーラン エラーが発生しにくくなります。
• 32 ビット マシンでも、文字列が使用可能なメモリのサイズになるようにすると、長さのプレフィックス付き文字列は、null で終了する文字列よりも 3 バイトだけ広くなります。16 ビット マシンでは、これは 1 バイトです。64 ビット マシンでは、文字列の長さの制限として 4GB が合理的ですが、それをマシン ワードのサイズまで拡張したい場合でも、64 ビット マシンには通常十分なメモリがあり、余分な 7 バイトが null 引数のようになります。元の C 標準が (メモリの点で) 非常に貧弱なマシン向けに作成されたことは知っていますが、効率の議論は私をここで売り込むものではありません。
• 他のほとんどすべての言語 (つまり、Perl、Pascal、Python、Java、C# など) は、長さのプレフィックス付き文字列を使用します。これらの言語は通常、文字列操作のベンチマークで C よりも優れています。
• C++ はテンプレートを使用してこれを少し修正しましたstd::basic_stringが、null で終了する文字列を期待するプレーンな文字配列は依然として普及しています。ヒープ割り当てが必要なため、これも不完全です。
• ヌルで終了する文字列は、文字列に存在できない文字 (つまり、ヌル) を予約する必要がありますが、長さの接頭辞が付いた文字列には、埋め込まれたヌルを含めることができます。

これらのことのいくつかは C よりも最近明らかになったので、C がそれらを知らなかったのは理にかなっています。ただし、いくつかは C が登場する前に単純なものでした。明らかに優れた長さの接頭辞ではなく、ヌルで終了する文字列が選択されたのはなぜですか?

編集: 上記の効率化ポイントについて、いくつかの事実を尋ねた(そして、私が既に提供したものを好まなかった) ため、それらはいくつかのことに由来します:

• null で終了する文字列を使用した連結には、O(n + m) 時間の計算量が必要です。多くの場合、長さのプレフィックスには O(m) しか必要ありません。
• null で終了する文字列を使用した長さには、O(n) 時間の計算量が必要です。長さのプレフィックスは O(1) です。
• 長さと連結は、最も一般的な文字列操作です。null で終了する文字列の方が効率的である場合がいくつかありますが、その頻度ははるかに低くなります。

以下の回答から、null で終了する文字列の方が効率的である場合がいくつかあります。

• 文字列の先頭を切り取り、それを何らかのメソッドに渡す必要がある場合。長さの接頭辞はおそらく整列規則に従う必要があるため、元の文字列を破棄することが許可されていても、長さの接頭辞を使用して一定の時間でこれを行うことはできません。
• 文字列を 1 文字ずつループしているだけの場合、CPU レジスタを保存できる場合があります。これは、文字列を動的に割り当てていない場合にのみ機能することに注意してください (文字列を解放する必要があるため、保存した CPU レジスタを使用して、もともと malloc と友人から取得したポインターを保持する必要があります)。

上記のいずれも、長さと連結ほど一般的ではありません。

以下の回答には、もう1つ主張されています。

• 弦の端を切り落とす必要があります

しかし、これは正しくありません。null で終了し、プレフィックス付きの長さの文字列の時間は同じです。(null で終了する文字列は、新しい末尾にしたい場所に null を貼り付けるだけで、長さプレフィックスはプレフィックスから減算するだけです。)

Answer 1

馬の口から

BCPL、B、または C のいずれも、言語で文字データを強力にサポートしていません。それぞれ、整数のベクトルのように文字列を扱い、いくつかの規則によって一般的な規則を補足します。BCPL と B の両方で、文字列リテラルは、セルにパックされた文字列の文字で初期化された静的領域のアドレスを示します。BCPL では、パックされた最初のバイトに文字列の文字数が含まれます。B ではカウントがなく、文字列は B が綴った特殊文字で終了します *e。この変更は、8 ビットまたは 9 ビット スロットにカウントを保持することによって引き起こされる文字列の長さの制限を回避するために部分的に行われました。

_{Dennis M Ritchie、C 言語の開発}

Answer 2

C には、言語の一部として文字列がありません。C の「文字列」は、char への単なるポインタです。だから多分あなたは間違った質問をしている.

「文字列型を除外する理由は何ですか」の方が適切かもしれません。それに対して、C はオブジェクト指向言語ではなく、基本的な値型しかないことを指摘しておきます。文字列は、何らかの方法で他の型の値を組み合わせて実装する必要がある高レベルの概念です。C は、より低いレベルの抽象化です。

以下の荒れ狂うスコールに照らして：

これがばかげた、または悪い質問だと言っているわけではないこと、または文字列を表現する C の方法が最良の選択であると言っているわけではないことを指摘したいだけです。Cには文字列をデータ型としてバイト配列と区別するメカニズムがないという事実を考慮に入れると、質問がより簡潔になることを明確にしようとしています。今日のコンピュータの処理能力とメモリ能力を考慮すると、これが最良の選択でしょうか? おそらくそうではありません。しかし、後知恵は常に20/20であり、そのすべてです:)

Answer 3

質問はLength Prefixed Strings (LPS)vsのzero terminated strings (SZ)ものとして尋ねられますが、ほとんどの場合、長さの接頭辞付き文字列の利点が明らかになります。それは圧倒的に思えるかもしれませんが、正直に言うと、LPSの欠点とSZの利点も考慮する必要があります。

私が理解しているように、この質問は、「ゼロ終端文字列の利点は何ですか？」という偏った方法として理解されることさえあります。

ゼロ終端文字列の利点（私は見る）：

• 非常に単純で、言語に新しい概念を導入する必要はありません。char配列/charポインターで実行できます。
• コア言語には、二重引用符の間の何かを一連の文字（実際には一連のバイト）に変換するための最小限の構文糖が含まれています。場合によっては、テキストとはまったく関係のないものを初期化するために使用できます。たとえば、xpm画像ファイル形式は、文字列としてエンコードされた画像データを含む有効なCソースです。
• ちなみに、文字列リテラルにゼロを入れることができます。コンパイラは、リテラルの最後にもう1つ追加するだけです"this\0is\0valid\0C"。文字列ですか？または4つの弦？またはバイトの束...
• フラットな実装、非表示の間接参照、非表示の整数はありません。
• 隠れたメモリ割り当ては含まれていません（strdupのようないくつかの悪名高い非標準関数は割り当てを実行しますが、それは主に問題の原因です）。
• 小規模または大規模なハードウェアに特定の問題はありません（8ビットマイクロコントローラーで32ビットプレフィックス長を管理する負担、または文字列サイズを256バイト未満に制限する制限を想像してください。これは私が以前Turbo Pascalで実際に抱えていた問題でした）。
• 文字列操作の実装は、ほんの一握りの非常に単純なライブラリ関数です。
• 文字列の主な用途に効率的：既知の開始から順番に読み取られる一定のテキスト（主にユーザーへのメッセージ）。
• 終了ゼロは必須ではなく、バイトの束のように文字を操作するために必要なすべてのツールが利用可能です。Cで配列の初期化を実行する場合、NULターミネータを回避することもできます。適切なサイズを設定するだけです。char a[3] = "foo";は有効なC（C ++ではない）であり、aに最後のゼロを入れません。
• stdin、stdoutのような本質的な長さを持たない「ファイル」を含む、「すべてがファイルである」というUNIXの観点と一貫性があります。オープン読み取りおよび書き込みプリミティブは非常に低いレベルで実装されていることを覚えておく必要があります。これらはライブラリ呼び出しではなく、システム呼び出しです。また、同じAPIがバイナリファイルまたはテキストファイルに使用されます。ファイル読み取りプリミティブは、バッファアドレスとサイズを取得し、新しいサイズを返します。また、文字列をバッファとして使用して書き込むことができます。別の種類の文字列表現を使用すると、出力するバッファとしてリテラル文字列を簡単に使用できないことを意味します。または、にキャストするときに非常に奇妙な動作をさせる必要がありますchar*。つまり、文字列のアドレスを返すのではなく、実際のデータを返します。
• ファイルから読み取ったテキストデータをインプレースで操作するのは非常に簡単で、バッファを無駄にコピーする必要はありません。適切な場所にゼロを挿入するだけです（最近のCでは、二重引用符で囲まれた文字列は現在、変更不可能なデータに保持されているconst char配列であるため、実際にはそうではありません）セグメント）。
• 任意のサイズのいくつかのint値を前に付けると、配置の問題が発生します。最初の長さは整列する必要がありますが、文字データに対してそれを行う理由はありません（また、文字列の整列を強制すると、文字列をバイトの束として扱うときに問題が発生します）。
• 長さは、定数リテラル文字列（sizeof）のコンパイル時に既知です。では、なぜ誰かがそれを実際のデータの前にメモリに保存したいのでしょうか？
• Cが（ほぼ）他のすべての人と同じように行っているように、文字列はcharの配列として表示されます。配列の長さはCによって管理されないため、文字列に対しても論理的な長さは管理されません。唯一驚くべきことは、最後に0項目が追加されていることですが、二重引用符で囲まれた文字列を入力する場合、これはコア言語レベルにすぎません。ユーザーは、長さを渡す文字列操作関数を完全に呼び出すことができます。あるいは、代わりに単純なmemcopyを使用することもできます。SZは単なる施設です。他のほとんどの言語では、配列の長さが管理されますが、文字列の場合も同じです。
• とにかく現代では、1バイトの文字セットでは不十分であり、文字数がバイト数と大きく異なるエンコードされたUnicode文字列を処理する必要があることがよくあります。これは、ユーザーがおそらく「サイズだけ」だけでなく、他の情報も必要とすることを意味します。長さを保つことは、これらの他の有用な情報に関して何も使用しません（特にそれらを保存するための自然な場所はありません）。

とは言うものの、標準のC文字列が実際に非効率的であるというまれなケースでは文句を言う必要はありません。Libsが利用可能です。その傾向に従えば、標準Cには正規表現サポート関数が含まれていないことに不満を言う必要があります...しかし、その目的で使用できるライブラリがあるため、実際には誰もがそれが実際の問題ではないことを知っています。したがって、文字列操作の効率が必要な場合は、bstringのようなライブラリを使用してみませんか？またはC++文字列でさえ？

編集：私は最近D文字列を調べました。選択されたソリューションがサイズプレフィックスでもゼロターミネーションでもないことを確認するのは非常に興味深いことです。Cの場合と同様に、二重引用符で囲まれたリテラル文字列は、不変のchar配列の省略形であり、言語には、（不変のchar配列）を意味するstringキーワードもあります。

しかし、DアレイはCアレイよりもはるかに豊富です。静的配列の場合、実行時に長さがわかっているため、長さを格納する必要はありません。コンパイラはコンパイル時にそれを持っています。動的配列の場合、長さは利用可能ですが、Dのドキュメントにはそれが保持される場所が記載されていません。私たちが知っている限りでは、コンパイラーはそれをいくつかのレジスターに保持するか、文字データから遠く離れて格納されているいくつかの変数に保持するかを選択できます。

通常のchar配列または非リテラル文字列では、最後のゼロがないため、プログラマーはDからC関数を呼び出したい場合は、それ自体を配置する必要があります。ただし、リテラル文字列の特定のケースでは、Dコンパイラーは依然としてゼロを配置します。各文字列の終わり（C文字列に簡単にキャストしてC関数の呼び出しを簡単にするため？）、ただしこのゼロは文字列の一部ではありません（Dは文字列サイズにカウントしません）。

私を少しがっかりさせた唯一のことは、文字列がutf-8であることになっていることですが、マルチバイト文字を使用している場合でも、長さは明らかにバイト数を返します（少なくとも私のコンパイラgdcでは当てはまります）。それがコンパイラのバグなのか、それとも目的によるものなのかは私にはわかりません。（OK、私はおそらく何が起こったのかを知っています。ソースがutf-8を使用していると言うには、最初に愚かなバイト順マークを付ける必要があります。特にUTFの場合、エディターがそれを行っていないことを知っているので、愚かなことを書きます。 8はASCII互換であると思われます）。

Answer 4

私は、それには歴史的な理由があり、ウィキペディアでこれを見つけたと思います：

C (およびその派生言語) が開発された当時、メモリは非常に限られていたため、文字列の長さを格納するためにわずか 1 バイトのオーバーヘッドを使用することは魅力的でした。当時唯一の一般的な代替手段は、通常 "Pascal 文字列" と呼ばれていました (BASIC の初期のバージョンでも使用されていました) は、先頭のバイトを使用して文字列の長さを格納していました。これにより、文字列に NUL を含めることができ、長さの検出に 1 回のメモリ アクセス (O(1) (定数) 時間) のみが必要になります。しかし、1 バイトは長さを 255 に制限します。この長さの制限は、C 文字列の問題よりもはるかに制限的であったため、一般的に C 文字列が勝ちました。

Answer 5

Calaveraの言う通りですが、人々は彼の主張を理解していないようですので、いくつかのコード例を提供します。

まず、C とは何かを考えてみましょう。単純な言語で、すべてのコードがかなり直接的に機械語に翻訳されています。すべての型はレジスタとスタックに収まり、オペレーティング システムや大きなランタイム ライブラリを実行する必要はありません。今日に至るまで競争相手になる可能性すらありません）。

C にorstringのような型がある場合、それはレジスタまたはスタックに収まらない型になり、何らかの方法で処理するために (すべてのサポート インフラストラクチャと共に) メモリ割り当てが必要になります。これらはすべて、C の基本原則に反します。intchar

したがって、C の文字列は次のようになります。

char s*;

したがって、これが長さの接頭辞であると仮定しましょう。2 つの文字列を連結するコードを書きましょう。

char* concat(char* s1, char* s2)
{
    /* What? What is the type of the length of the string? */
    int l1 = *(int*) s1;
    /* How much? How much must I skip? */
    char *s1s = s1 + sizeof(int);
    int l2 = *(int*) s2;
    char *s2s = s2 + sizeof(int);
    int l3 = l1 + l2;
    char *s3 = (char*) malloc(l3 + sizeof(int));
    char *s3s = s3 + sizeof(int);
    memcpy(s3s, s1s, l1);
    memcpy(s3s + l1, s2s, l2);
    *(int*) s3 = l3;
    return s3;
}

もう 1 つの方法は、構造体を使用して文字列を定義することです。

struct {
  int len; /* cannot be left implementation-defined */
  char* buf;
}

この時点で、すべての文字列操作で 2 つの割り当てを行う必要があります。これは、実際にはライブラリを介して処理を行うことを意味します。

面白いことに...そのような構造体はCに存在します! それらは、ユーザー処理への日常の表示メッセージには使用されません。

したがって、Calavera が指摘していることは次のとおりです。C には文字列型はありません。それを使って何かをするには、ポインタを取り、それを 2 つの異なる型へのポインタとしてデコードする必要があります。その後、文字列のサイズが非常に重要になり、「実装定義」のままにしておくことはできません。

現在、Cはいずれにしてもメモリを処理できmem、ライブラリ内の関数 (in<string.h>でさえも!) は、メモリをポインタとサイズのペアとして処理するために必要なすべてのツールを提供します。Cのいわゆる「文字列」 は、テキスト端末用のオペレーティング システムを作成するコンテキストでメッセージを表示するという 1 つの目的のために作成されました。そのためには、null 終了で十分です。

Answer 6

strlen明らかに、パフォーマンスと安全性のために、ストリングを繰り返し実行したり、同等のものを実行したりするのではなく、ストリングを操作している間、ストリングの長さを維持する必要があります。ただし、文字列の内容の直前の固定位置に長さを格納することは、非常に悪い設計です。JörgenがSanjitの回答に対するコメントで指摘したように、文字列の末尾を文字列として扱うことはできません。たとえば、新しいメモリを割り当てないと、多くの一般的な操作が不可能になります（失敗path_to_filenameやfilename_to_extensionエラー処理の可能性があります）。 。そしてもちろん、文字列の長さフィールドが何バイトを占めるべきかについて誰も同意できないという問題があります（多くの悪い「パスカル文字列」

長さを格納するかどうか、どこに、どのように格納するかをプログラマーが選択できるようにするCの設計は、はるかに柔軟で強力です。しかしもちろん、プログラマーは賢くなければなりません。Cは、クラッシュしたり、停止したり、敵を根絶したりするプログラムで愚かさを罰します。

Answer 7

任意の言語のアセンブリガットを考慮すると、怠惰、レジスタの倹約、および移植性、特にアセンブリよりも 1 ステップ上の C を考慮します (したがって、多くのアセンブリのレガシー コードを継承します)。null char は ASCII 時代には役に立たないので、同意するでしょう (おそらく EOF 制御 char と同じくらい良いでしょう)。

疑似コードで見てみましょう

function readString(string) // 1 parameter: 1 register or 1 stact entries
    pointer=addressOf(string) 
    while(string[pointer]!=CONTROL_CHAR) do
        read(string[pointer])
        increment pointer

合計1レジスタ使用

ケース 2

 function readString(length,string) // 2 parameters: 2 register used or 2 stack entries
     pointer=addressOf(string) 
     while(length>0) do 
         read(string[pointer])
         increment pointer
         decrement length

合計 2 レジスタを使用

当時は近視眼的に見えるかもしれませんが、コードとレジスターの倹約を考えると (当時は PREMIUM でした。ご存知のように、パンチ カードを使用します)。したがって、（プロセッサの速度をkHzでカウントできる場合）高速であるため、この「ハック」は非常に優れており、レジスタレスプロセッサに簡単に移植できました。

議論のために、2つの一般的な文字列操作を実装します

stringLength(string)
     pointer=addressOf(string)
     while(string[pointer]!=CONTROL_CHAR) do
         increment pointer
     return pointer-addressOf(string)

複雑さ O(n) ほとんどの場合、PASCAL 文字列は O(1) です。これは、文字列の長さが文字列構造の先頭にあるためです (これは、この操作を前の段階で実行する必要があることも意味します)。

concatString(string1,string2)
     length1=stringLength(string1)
     length2=stringLength(string2)
     string3=allocate(string1+string2)
     pointer1=addressOf(string1)
     pointer3=addressOf(string3)
     while(string1[pointer1]!=CONTROL_CHAR) do
         string3[pointer3]=string1[pointer1]
         increment pointer3
         increment pointer1
     pointer2=addressOf(string2)
     while(string2[pointer2]!=CONTROL_CHAR) do
         string3[pointer3]=string2[pointer2]
         increment pointer3
         increment pointer1
     return string3

複雑さ O(n) と文字列の長さを前に追加しても、操作の複雑さは変わりませんが、時間が3分の1になることは認めます。

一方、PASCAL 文字列を使用する場合、レジスタの長さとビット エンディアンを考慮して API を再設計する必要があります。長さが 1 バイト (8 ビット)、そしてより長い文字列 (16 ビット -> なんでも) が必要な場合は、コードの 1 つのレイヤーのアーキテクチャを考慮する必要があります。これは、より長い文字列が必要な場合、ほとんどの場合、互換性のない文字列 API を意味します。

例：

1 つのファイルは、先頭に追加された文字列 API を使用して 8 ビット コンピューターで書き込まれ、たとえば 32 ビット コンピューターで読み取る必要があります。遅延プログラムは、4 バイトが文字列の長さであると見なし、その大量のメモリを割り当てます。次に、そのバイト数を読み取ろうとします。もう 1 つのケースは、x86 (ビッグ エンディアン) への PPC 32 バイト文字列の読み取り (リトル エンディアン) です。1 バイト長 (0x00000001) は 16777216 (0x0100000) になり、1 バイト文字列を読み取るには 16 MB になります。もちろん、人々は 1 つの標準に同意する必要があると言うでしょうが、16 ビットの Unicode でさえ、ほとんどエンディアンとビッグ エンディアンがありません。

もちろん、C にも問題はありますが、ここで提起された問題の影響はほとんどありません。

Answer 8

多くの点で、C は原始的でした。そして、私はそれが大好きでした。

これはアセンブリ言語よりも一歩上の言語であり、記述と保守がはるかに簡単な言語でほぼ同じパフォーマンスを提供します。

null ターミネータは単純で、言語による特別なサポートは必要ありません。

振り返ってみると、それほど便利ではないようです。しかし、私は 80 年代にアセンブリ言語を使用していましたが、当時は非常に便利に思えました。ソフトウェアは絶えず進化しており、プラットフォームとツールはますます洗練されていると思います。

Answer 9

C が Pascal の方法で文字列を実装し、長さのプレフィックスを付けたと仮定すると、7 文字の長さの文字列は 3 文字の文字列と同じデータ型ですか? 答えが「はい」の場合、前者を後者に割り当てると、コンパイラはどのようなコードを生成する必要がありますか? 文字列を切り捨てるか、自動的にサイズ変更するか? サイズを変更した場合、スレッドセーフにするためにその操作をロックで保護する必要がありますか? C アプローチ側は、好むと好まざるとにかかわらず、これらすべての問題を解決しました :)

Answer 10

どういうわけか、この質問は、C では長さがプレフィックスされた文字列をサポートしていないことを意味するものだと理解しました。次の例は、少なくとも、次のような構成を使用して、コンパイル時に文字列の長さがカウントされる独自の C 文字列ライブラリを開始できることを示しています。

#define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) })

typedef struct { int n; char * p; } prefix_str_t;

int main() {
    prefix_str_t string1, string2;

    string1 = PREFIX_STR("Hello!");
    string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)");

    printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */
    printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */

    return 0;
}

charただし、その文字列ポインターを具体的に解放するタイミングと、静的に割り当てられる (リテラル配列)タイミングに注意する必要があるため、これには問題はありません。

編集：質問に対するより直接的な答えとして、私の見解は、これはCが必要に応じて（コンパイル時定数として）文字列の長さを利用できるようにする方法であり、使用したい場合でもメモリのオーバーヘッドはありません。ポインターとゼロ終端のみ。

もちろん、標準ライブラリは一般に文字列の長さを引数として取りませんchar * s = "abc"。また、私の例が示すように、長さの抽出は のように簡単なコードではないため、ゼロで終わる文字列を使用することが推奨される方法のようです。

Answer 11

「32ビットマシンでも、文字列が利用可能なメモリのサイズになるようにすると、長さのプレフィックス付き文字列は、nullで終了する文字列よりも3バイトだけ広くなります。」

まず、短い文字列の場合、余分な 3 バイトがかなりのオーバーヘッドになる可能性があります。特に、長さ 0 の文字列は 4 倍のメモリを消費するようになりました。一部のユーザーは 64 ビット マシンを使用しているため、長さ 0 の文字列を格納するために 8 バイトが必要か、プラットフォームがサポートする最長の文字列を文字列形式で処理できないかのいずれかです。

対処すべき調整の問題もあるかもしれません。「solo\0second\0\0four\0five\0\0seventh」のように、7 つの文字列を含むメモリ ブロックがあるとします。2 番目の文字列はオフセット 5 から始まります。ハードウェアでは、32 ビット整数を 4 の倍数のアドレスに配置する必要がある場合があるため、パディングを追加する必要があり、オーバーヘッドがさらに増加し​​ます。それに比べて、C 表現は非常にメモリ効率が良いです。(メモリー効率は良好です。たとえば、キャッシュのパフォーマンスに役立ちます。)

Answer 12

まだ言及されていない 1 つのポイント: C が設計されたとき、「char」が 8 ビットではないマシンが多数ありました (今日でも、8 ビットでない DSP プラットフォームがあります)。文字列に長さの接頭辞を付けることにした場合、何文字分の長さの接頭辞を使用する必要がありますか? 2 を使用すると、8 ビットの文字と 32 ビットのアドレス空間を持つマシンの文字列の長さに人為的な制限が課せられ、16 ビットの文字と 16 ビットのアドレス空間を持つマシンではスペースが浪費されます。

任意の長さの文字列を効率的に格納できるようにしたい場合、および 'char' が常に 8 ビットである場合、速度とコード サイズがいくらか犠牲になるため、スキームを偶数で始まる文字列と定義できます。 N は N/2 バイトの長さであり、奇数値 N と偶数値 M (逆方向に読む) で始まる文字列は ((N-1) + M*char_max)/2 のようになり、任意のバッファを必要とします。文字列を保持するために一定量のスペースを提供すると主張する場合、そのスペースの前に最大長を処理するのに十分なバイト数を許可する必要があります。ただし、文字列の長さを保持するために必要な「char」の数は CPU アーキテクチャによって異なるため、「char」が常に 8 ビットであるとは限らないため、このようなスキームは複雑になります。

Answer 13

NULL 終端により、高速なポインター ベースの操作が可能になります。

Answer 14

C を取り巻く多くの設計上の決定は、C が最初に実装されたとき、パラメーターの受け渡しがやや高価だったという事実に起因しています。たとえば、

void add_element_to_next(arr, offset)
  char[] arr;
  int offset;
{
  arr[offset] += arr[offset+1];
}

char array[40];

void test()
{
  for (i=0; i<39; i++)
    add_element_to_next(array, i);
}

対

void add_element_to_next(ptr)
  char *p;
{
  p[0]+=p[1];
}

char array[40];

void test()
{
  int i;
  for (i=0; i<39; i++)
    add_element_to_next(arr+i);
}

後者は、2 つではなく 1 つのパラメーターを渡すだけで済むため、わずかに安価でした (したがって、優先されます)。呼び出されるメソッドが配列のベース アドレスもその中のインデックスも知る必要がない場合、2 つの値を組み合わせて単一のポインターを渡す方が、値を個別に渡すよりも安価です。

C が文字列の長さをエンコードできる合理的な方法はたくさんありますが、それまでに発明されたアプローチには、文字列の一部を処理して文字列のベース アドレスを受け取り、目的のインデックスを 2 つの個別のパラメーターとして指定します。ゼロバイトターミネーションを使用することで、その要件を回避することが可能になりました。今日のマシンでは他のアプローチの方が優れていますが (最新のコンパイラはパラメーターをレジスターに渡すことが多く、memcpy は strcpy() と同等の方法ではできない方法で最適化できます)、十分な数の製品コードがゼロバイトで終了する文字列を使用しているため、他のものに変更するのは困難です。

PS--一部の操作でのわずかな速度の低下と、長い文字列でのわずかな余分なオーバーヘッドと引き換えに、文字列を操作するメソッドに、文字列への直接ポインター、境界チェックされた文字列バッファー、または別の文字列の部分文字列を識別するデータ構造。「strcat」のような関数は、[現代の構文] のように見えます。

void strcat(unsigned char *dest, unsigned char *src)
{
  struct STRING_INFO d,s;
  str_size_t copy_length;

  get_string_info(&d, dest);
  get_string_info(&s, src);
  if (d.si_buff_size > d.si_length) // Destination is resizable buffer
  {
    copy_length = d.si_buff_size - d.si_length;
    if (s.src_length < copy_length)
      copy_length = s.src_length;
    memcpy(d.buff + d.si_length, s.buff, copy_length);
    d.si_length += copy_length;
    update_string_length(&d);
  }
}

K&R strcat メソッドより少し大きいですが、K&R メソッドではサポートされていない境界チェックをサポートします。さらに、現在の方法とは異なり、任意の部分文字列を簡単に連結できます。

/* Concatenate 10th through 24th characters from src to dest */

void catpart(unsigned char *dest, unsigned char *src)
{
  struct SUBSTRING_INFO *inf;
  src = temp_substring(&inf, src, 10, 24);
  strcat(dest, src);
}

temp_substring によって返される文字列の有効期間は、sとsrcのいずれか短い方によって制限されることに注意してください (これが、メソッドinfを渡す必要がある理由です。ローカルの場合、メソッドが返されたときに終了します)。

メモリ コストに関しては、最大 64 バイトの文字列とバッファには 1 バイトのオーバーヘッドがあります (ゼロで終わる文字列と同じ)。文字列が長いほど、わずかに多くなります (2 バイト間のオーバーヘッドの許容量と必要な最大量は、時間とスペースのトレードオフになります)。長さ/モード バイトの特別な値は、文字列関数にフラグ バイト、ポインタ、およびバッファ長を含む構造体が与えられたことを示すために使用されます (その後、他の文字列に任意にインデックスを付けることができます)。

もちろん、K&R はそのようなものを実装していませんでしたが、それはおそらく、今日でも多くの言語が貧弱に見える領域である文字列処理に多くの労力を費やしたくなかったためです。

Answer 15

必ずしも理論的根拠ではないが、長さエンコードの対比

1. 動的な長さのエンコーディングの特定の形式は、メモリに関する限り、静的な長さのエンコーディングよりも優れていますが、それはすべて使用法に依存します。証拠としてUTF-8を見てください。これは基本的に、単一の文字をエンコードするための拡張可能な文字配列です。これは、拡張バイトごとに 1 ビットを使用します。NUL ターミネーションは 8 ビットを使用します。長さプレフィックスは、64 ビットを使用することで、合理的に無限長とも呼ぶことができると思います。余分なビットのケースにヒットする頻度が決定要因です。非常に大きな文字列は 1 つだけですか? 使用しているビットが 8 ビットか 64 ビットかは誰が気にしますか? 多くの小さな文字列 (つまり、英単語の文字列)? 次に、プレフィックスのコストが大きな割合を占めます。

2. 時間の節約を可能にする長さプレフィックス文字列は現実のものではありません。提供されたデータの長さを提供する必要があるかどうか、コンパイル時にカウントするか、文字列としてエンコードする必要がある動的データを実際に提供するかどうか。これらのサイズは、アルゴリズムのある時点で計算されます。null で終了する文字列のサイズを格納する別の変数を提供できます。これにより、時間の節約に関する比較は意味がありません。最後に余分なNULがあるだけです...しかし、長さのエンコードにそのNULが含まれていない場合、文字通り2つの間に違いはありません。アルゴリズムの変更はまったく必要ありません。コンパイラ/ランタイムにそれを行わせるのではなく、自分で手動で設計する必要がある単なるプレパスです。C は、ほとんどの場合、手動で処理を行うものです。

3. オプションの length-prefix はセールス ポイントです。アルゴリズムにその追加情報が常に必要なわけではないため、すべての文字列に対してそれを行う必要があるため、事前計算と計算の時間が O(n) を下回ることはありません。(つまり、ハードウェア乱数ジェネレーター 1-128。「無限の文字列」から引き出すことができます。文字を非常に高速にしか生成しないとしましょう。したがって、文字列の長さは常に変化します。しかし、データの使用方法はおそらく気にしません。私が持っているランダムなバイトがたくさんあります. リクエスト後すぐに次の利用可能な未使用バイトを取得したいだけです. デバイスで待機している可能性があります. しかし、事前に読み取られた文字のバッファを持つこともできます. 長さの比較は次のとおりです.不必要な計算の無駄です。null チェックの方が効率的です。)

4. 長さプレフィックスはバッファ オーバーフローに対する適切なガードですか? ライブラリ関数と実装の適切な使用法も同様です。不正な形式のデータを渡すとどうなりますか? 私のバッファの長さは 2 バイトですが、関数には 7 であると伝えています。例: gets()が既知のデータで使用されることを意図していた場合、コンパイルされたバッファとmalloc()をテストする内部バッファ チェックがあった可能性があります。呼び出しても仕様に従います。不明なSTDINが不明なバッファに到達するためのパイプとして使用されることを意図していた場合、長さの引数が無意味であることを意味するバッファサイズを明らかに知ることはできません。カナリアチェックのようなものが必要です。さらに言えば、一部のストリームと入力に長さのプレフィックスを付けることはできません。つまり、長さチェックはアルゴリズムに組み込む必要があり、タイピング システムの魔法の部分ではありません。TL;DR NUL 終了が安全である必要はありませんでした。

5. counter-counter point:バイナリでは NUL 終了が厄介です。ここで長さプレフィックスを実行するか、何らかの方法で NUL バイトを変換する必要があります: エスケープコード、範囲の再マッピングなど...もちろん、メモリ使用量/情報の削減/バイトあたりの操作数の増加を意味します。ここでは、長さプレフィックスがほとんどの場合、戦争に勝ちます。変換の唯一の利点は、長さプレフィックス文字列をカバーするために追加の関数を記述する必要がないことです。つまり、より最適化された sub-O(n) ルーチンでは、コードを追加しなくても、それらを O(n) の同等物として自動的に機能させることができます。欠点はもちろん、NUL の重い文字列で使用した場合の時間/メモリ/圧縮の無駄です。バイナリ データを操作するために最終的に複製するライブラリの量によっては、長さプレフィックス文字列のみを使用することが理にかなっている場合があります。つまり、長さプレフィックス文字列でも同じことができます... -1 の長さは NUL で終了することを意味し、長さで終了する内部で NUL で終了する文字列を使用できます。

6. 連結: "O(n+m) vs O(m)"連結後の文字列の全長として m を参照していると想定しています-on を文字列 1 に再割り当てする必要がある場合はどうすればよいでしょうか?)。そして、n は、事前計算のために行う必要がなくなった操作の神話的な量であると想定しています。もしそうなら、答えは簡単です: 事前計算です。もしも再割り当てする必要がないように常に十分なメモリがあると主張しています。これがbig-O表記の基礎です。答えはさらに簡単です。文字列1の終わりに割り当てられたメモリでバイナリ検索を行います。明らかに大きな再割り当てについて心配しないように、文字列 1 の後に無限ゼロの見本を追加します。そこで、n を log(n) に簡単に取得し、ほとんど試しませんでした。log(n) は、実際のコンピューターでは基本的に 64 の大きさしかないことを思い出してください。これは、本質的に O(m) である O(64+m) と言うようなものです。(そして、そのロジックは、今日使用されている実際のデータ構造の実行時分析で使用されています。それは私の頭の上ででたらめではありません。)

7. Concat()/Len()_再び: 結果をメモします。簡単。可能/必要な場合は、すべての計算を事前計算に変換します。これはアルゴリズムの決定です。これは、言語の強制的な制約ではありません。

8. 文字列サフィックスの受け渡しは、NUL ターミネーションを使用すると簡単/可能です。length-prefix の実装方法によっては、元の文字列を破壊する可能性があり、不可能な場合もあります。O(1) の代わりに O(n) をコピーして渡す必要があります。

9. 引数の受け渡し/逆参照は、長さプレフィックスよりも NUL で終了する方が少なくなります。明らかに、渡す情報が少ないためです。長さが必要ない場合、これによりフットプリントが大幅に節約され、最適化が可能になります。

10. あなたはだますことができます。それは本当にただのポインターです。文字列として読み取らなければならないと誰が言いましたか? 単一の文字またはフロートとして読み取りたい場合はどうなりますか? 反対に、float を文字列として読み取りたい場合はどうすればよいでしょうか。注意すれば、NUL 終了でこれを行うことができます。length-prefix でこれを行うことはできません。これは通常、ポインターとは明らかに異なるデータ型です。ほとんどの場合、文字列をバイト単位で作成して長さを取得する必要があります。もちろん、フロート全体のようなものが必要な場合(おそらく内部に NUL がある場合) は、とにかくバイト単位で読み取る必要がありますが、詳細は決定する必要があります。

TL;DRバイナリ データを使用していますか? いいえの場合、NUL 終了によりアルゴリズムの自由度が高まります。はいの場合、コード量と速度/メモリ/圧縮が主な関心事です。2 つのアプローチのブレンドまたはメモ化が最適な場合があります。

Answer 16

このブログ投稿のJoel Spolsky によると、

これは、UNIX と C プログラミング言語が発明された PDP-7 マイクロプロセッサが ASCIZ 文字列型を持っていたためです。ASCIZ は、「最後に Z (ゼロ) がある ASCII」を意味します。

ここで他のすべての回答を見た後、これが真実であったとしても、それはCがヌルで終わる「文字列」を持つ理由の一部にすぎないと確信しています。その投稿は、文字列のような単純なものが実際には非常に難しいことを明らかにしています。