44

最も効率的な方法ではないかもしれませんが、それは正しく移植可能ですか? 

int are_overlapping(const char *a, const char *b) {
  return (a + strlen(a) == b + strlen(b));
}

明確にするために：私が探しているのは、実際のコンテンツではなく、メモリ内のオーバーラップです。例えば： 

const char a[] = "string";
const char b[] = "another string";
are_overlapping(a, b); // should return 0
are_overlapping(a, a + 3); // should return 1
4

5 に答える 5

33

はい、あなたのコードは正しいです。2 つの文字列がサンプルの場所で終了する場合、それらは定義上重複しており、同じヌル ターミネータを共有しています。両方の文字列が同一であるか、一方が他方の部分文字列です。

プログラムに関するすべてが完全に明確に定義された動作であるため、標準に準拠したコンパイラを想定すると、完全に移植可能になるはずです。

標準の関連ビットは、6.5.9 等価演算子(強調鉱山) からのものです。

2 つのポインターが等しく比較されるのは、両方がヌル ポインターであり、両方が同じオブジェクト(オブジェクトおよびその先頭のサブオブジェクトへのポインターを含む) または関数へのポインターであり、両方が同じ配列の最後の要素の 1 つ後ろの要素へのポインターである場合のみです。 object、または 1 つは 1 つの配列オブジェクトの末尾を過ぎたものへのポインターであり、もう 1 つは別の配列オブジェクトの先頭へのポインターであり、アドレス空間内の最初の配列オブジェクトの直後にたまたま続きます。

于 2013-07-09T23:47:12.957 に答える
12

以前の投稿 (おそらくまもなく削除される予定) に対する zdan のコメントについて考えてみると、エンドポイントをチェックするだけで十分だという結論に達しました。

オーバーラップがある場合、ヌル ターミネータによって 2 つの文字列が区別されなくなります。いくつかの可能性を見てみましょう。

から始めると

a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",

W が \0 を上書きするため、HellWorld という 1 つの単語ができます。それらは同じエンドポイントで終了します。

どういうわけか同じ開始点に書き込む場合:

a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"

Jupiter という単語があり、同じエンドポイントがあります。

エンドポイントが同じでオーバーラップしない場合はありますか? すこし。

a = 0x1000000 "Four" and
b = 0x1000004 "".

それは同様に重複を与えるでしょう。

null で終了する文字列をメモリに書き込んでいると仮定すると、一致するエンドポイントがない場合にオーバーラップが発生することは考えられません。

したがって、簡単な答えは次のとおりです。はい、小切手で十分です。

于 2013-07-09T23:47:18.703 に答える
2

あなたの質問は特にC文字列に関するものであるため、おそらくユースケースには関係ありませんが、データにNULバイトが文字列に埋め込まれている場合、コードは機能しません。

char a[] = "abcd\0ABCD";
char *b = a + 5;

それ以外は、あなたの解決策は簡単で正しいです。ポインターの比較にのみ使用==しているため、標準に従って機能します（C11 6.5.9/6から）

2 つのポインターが等しく比較されるのは、両方がヌル ポインターであり、両方が同じオブジェクト (オブジェクトおよびその先頭のサブオブジェクトへのポインターを含む) または関数へのポインターであり、両方が同じ配列の最後の要素の 1 つ後ろを指すポインターである場合のみです。オブジェクト、または 1 つは 1 つの配列オブジェクトの末尾を過ぎたものへのポインターであり、もう 1 つは別の配列オブジェクトの先頭へのポインターであり、アドレス空間内の最初の配列オブジェクトの直後にたまたま続きます。

ただし、関係演算子はより厳密です (C11 6.5.8/5 以降)。

2 つのポインターを比較すると、結果は、指しているオブジェクトのアドレス空間内の相対位置によって異なります。オブジェクト型への 2 つのポインターが両方とも同じオブジェクトを指している場合、または両方が同じ配列オブジェクトの最後の要素の 1 つ後ろを指している場合、それらは等しいと比較されます。指しているオブジェクトが同じ集約オブジェクトのメンバーである場合、後で宣言された構造体メンバーへのポインターは、構造体で以前に宣言されたメンバーへのポインターよりも大きく、添字値が大きい配列要素へのポインターは、同じ配列の要素へのポインターよりも大きくなります。より低い添字値で。同じ共用体オブジェクトのメンバーへのすべてのポインターは等しいと比較されます。式 P が配列オブジェクトの要素を指し、式 Q が同じ配列オブジェクトの最後の要素を指す場合、

最後の文はキッカーです。

コードがオーバーラップの長さを 2 回計算する可能性があるという事実を例外とし、それを回避するための予防策を講じようとする人もいます。ただし、その計算を削減する効率は、反復ごとの追加のポインター比較によって相殺されるか、未定義または実装定義の動作を伴います。移植可能で準拠したソリューションが必要であると仮定すると、実際の平均利益はおそらくゼロであり、努力する価値はありません.

于 2013-07-10T02:35:25.113 に答える
1

はい、あなたのチェックは正しいですが、確かに最も効率的ではありません (「効率」が計算効率を意味する場合)。実装における明らかに直感的な非効率性は、文字列が実際にオーバーラップすると、呼び出しが共通部分を 2 回strlen反復するという事実に基づいています。

正式な効率のために、わずかに異なるアプローチを使用する場合があります

int are_overlapping(const char *a, const char *b) 
{
  if (a > b) /* or `(uintptr_t) a > (uintptr_t) b`, see note below! */
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  while (a != b && *a != '\0')
    ++a;

  return a == b;
}

このバージョンに関する重要な注意事項は、同じ配列を指していることが保証されていない 2 つのポインターの関係比較を実行することです。これは正式には未定義の動作につながります。これは、フラット メモリ モデルのシステムで実際に動作しますが、衒学的なコード レビュー担当者から批判を受ける可能性があります。この問題を正式に回避するには、uintptr_tリレーショナル比較を実行する前にポインターを に変換します。このようにして、未定義の動作は、フラット メモリ モデルを使用するほとんどの (すべてではないにしても) 従来の実装で、適切なセマンティクスを使用して実装定義の動作に変換されます。

このアプローチには、「二重カウント」の問題がありません。メモリ内の「前」にある文字列の重複しない部分のみを分析します。もちろん、実際には、このアプローチの利点は存在しないことが判明する可能性があります。strlenそれは、実装の品質と実際の入力のプロパティの両方に依存します。

たとえば、この状況では

const char *str = "Very very very long string, say 64K characters long......";

are_overlapped(str, str + 1);

私のバージョンは、あなたのバージョンよりもはるかに速くオーバーラップを検出します。私のバージョンはサイクルの 1 回の反復でそれを行いますが、あなたのバージョンは 2 * 64K の反復を費やします ( の単純な実装を想定strlen)。

疑わしいポインター比較の領域に飛び込むことにした場合は、上記のアイデアを次のように再実装することもできます。

int are_overlapping(const char *a, const char *b) 
{
  if (a > b)
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  return b <= a + strlen(a);
}

この実装は、反復ごとに追加のポインター比較を実行しません。そのために支払う代償は、早期に終了するのではなく、常に文字列の 1 つの終わりまで反復することです。それでも、呼び出しstrlenは 1 回だけなので、実装よりも効率的です。

于 2013-07-10T01:43:32.997 に答える