이것이 메모리에서 2개의 c-string이 중복되는지 확인하는 정확하고 휴대 가능한 방법입니까?

이것이 메모리에서 2개의 c-string이 중복되는지 확인하는 정확하고 휴대 가능한 방법입니까?

가장 효율적인 방법은 아닐 수도 있지만, 정확하고 휴대가 가능한가요?

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

네, 코드가 맞습니다.두 문자열이 샘플 위치에서 끝나는 경우 정의에 따라 중복됩니다. 두 문자열은 동일한 null 터미네이터를 공유합니다.두 문자열이 동일하거나 한 문자열이 다른 문자열의 하위 문자열입니다.

프로그램에 대한 모든 것은 완벽하게 정의된 동작이므로 표준 준수 컴파일러를 가정하면 완벽하게 휴대할 수 있습니다.

표준의 관련 비트는 6.5.9 동등 연산자(광산 강조)의 비트입니다.

두 포인터는 둘 다 null 포인터일 경우에만 동일하게 비교되며, 둘 다 동일한 객체에 대한 포인터이거나 함수에 대한 포인터이며, 둘 다 동일한 배열 객체의 마지막 요소에 대한 포인터입니다.또는 하나는 하나의 배열 개체의 끝을 지나 하나의 배열 개체에 대한 포인터이고 다른 하나는 주소 공간에서 첫 번째 배열 개체를 바로 따르는 다른 배열 개체의 시작에 대한 포인터입니다.

제 이전 게시물에 대한 zdan의 코멘트(아마도 곧 삭제될 것입니다)를 생각하면, 저는 엔드포인트를 확인하는 것으로 충분하다는 결론에 도달했습니다.

겹치는 부분이 있으면 Null 종료자가 두 문자열을 구분하지 못하게 합니다.몇 가지 가능성을 살펴보겠습니다.

시작할 경우

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

한 마디만 하실 겁니다W가 \0을 덮어쓰므로 HellWorld.동일한 끝점에서 종료됩니다.

어떤 식으로든 동일한 시작점에 글을 쓴다면,

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

당신은 목성이라는 단어를 갖게 될 것이고, 같은 종점을 갖게 될 것입니다.

엔드포인트가 같고 중복되지 않을 수 있는 경우가 있습니까?약간.

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

그것은 또한 중복될 것입니다.

메모리에 null로 종료된 문자열을 쓴다고 가정하면 일치하는 끝점이 없는 중복되는 시간은 생각할 수 없습니다.

즉, 간단한 대답은 다음과 같습니다.네, 수표로 충분합니다.

특히 C 문자열에 대한 질문이므로 사용 사례와 관련이 없을 수 있지만, 데이터에 NUL 바이트가 포함된 경우 코드가 작동하지 않습니다.

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

그 외에는 솔루션이 직접적이고 정확합니다.당신은 오직 사용하기 때문에 그것은 작동합니다.== 비교를 ( (C116.5.9/6부터).

두 포인터는 둘 다 null 포인터일 경우에만 동일하게 비교되며, 둘 다 동일한 객체에 대한 포인터이거나 함수에 대한 포인터이며, 둘 다 동일한 배열 객체의 마지막 요소에 대한 포인터입니다.또는 하나는 하나의 배열 개체의 끝을 지나 하나의 배열 개체에 대한 포인터이고 다른 하나는 주소 공간에서 첫 번째 배열 개체를 바로 따르는 다른 배열 개체의 시작에 대한 포인터입니다.

그러나 관계 연산자는 더 엄격합니다(C116.5.8/5부터).

두 포인터를 비교할 때 결과는 가리키는 개체의 주소 공간에 있는 상대적인 위치에 따라 달라집니다.개체 유형에 대한 두 포인터가 모두 동일한 개체를 가리키거나 두 포인터가 동일한 배열 개체의 마지막 요소를 지난 두 포인터를 가리키면 동일하게 비교됩니다.가리키는 개체가 동일한 집계 개체의 멤버인 경우 나중에 선언된 구조체 멤버에 대한 포인터는 구조체의 이전에 선언된 멤버에 대한 포인터보다 크고, 첨자 값이 큰 배열 요소에 대한 포인터는 첨자 값이 낮은 동일한 배열의 요소에 대한 포인터보다 큽니다.동일한 유니온 개체의 멤버에 대한 모든 포인터가 동일하게 비교됩니다.표현식 P가 배열 개체의 요소를 가리키고 표현식 Q가 동일한 배열 개체의 마지막 요소를 가리킬 경우 포인터 표현식 Q+1은 P보다 큰 값을 비교합니다.다른 모든 경우에는 동작이 정의되지 않습니다.

마지막 문장은 키커입니다.

일부는 코드가 중복되는 길이를 두 번 계산할 수 있다는 점을 고려하지 않고 이를 방지하기 위한 예방 조치를 시도했습니다.그러나 컴퓨팅을 줄이는 효율성은 반복당 추가 포인터 비교로 상쇄되거나 정의되지 않은 동작 또는 구현 정의된 동작을 수반합니다.호환되는 휴대용 솔루션을 원한다고 가정하면 실제 평균 이득은 0이 될 가능성이 높으며, 노력할 가치도 없습니다.

이 솔루션은 여전히 최악의 경우에도 동일한 성능을 제공하지만 히트에 최적화되어 있으므로 두 문자열을 모두 구문 분석할 필요는 없습니다.

char * temp_a = a;
char * temp_b = b;

while (*temp_a != '\0') {

    if (temp_a++ == b) 
        return 1;

}

// check for b being an empty string
if (temp_a == b) return 1;

/* but if b was larger, we aren't done, so you have to try from b now */
while (*temp_b != '\0') {
    if (temp_b++ == a)
        return 1;
}

/* don't need the a==b check again here

return 0;

분명히, C에서는 포인터 평등(부등식이 아닌)만 이동할 수 있습니다. 그래서 다음 솔루션은 이동할 수 없습니다. 아래의 모든 것은 제가 알기 전의 것입니다.

솔루션은 유효하지만, 왜 두 번째 문자열에서 strlen을 계산합니까?한 문자열의 시작점과 끝점을 알고 다른 문자열이 두 문자열 사이에 있는지 확인합니다(포함).두 번째 문자열을 통한 패스 저장 - O(M+N)에서 O(M)로

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
length = strlen(lower_addr_string)
return higher_addr_string >= lower_addr_string && higher_addr_string <= lower_addr_string + length;

또는 문자열을 직접 구문 분석합니다.

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
while(*lower_addr_string != '\0') {
    if (lower_addr_string == higher_addr_string)
        return 1;
    ++lower_addr_string;
}
/* check the last character */
if (lower_addr_string == higher_addr_string)
    return 1;
return 0;

예, 검사는 정확하지만 가장 효율적인 검사는 아닙니다("효율성"을 의미하는 경우).구현의 명백한 직관적인 비효율성은 문자열이 실제로 중복될 때,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;
}

이 버전에 대한 중요한 참고 사항은 동일한 배열을 가리키는 것이 보장되지 않는 두 포인터의 관계적 비교를 수행하므로 공식적으로 정의되지 않은 동작이 발생한다는 것입니다.이는 플랫 메모리 모델을 사용하는 시스템에서 실제로 작동하지만 현학적인 코드 검토자로부터 비판을 받을 수 있습니다.이 문제를 공식적으로 해결하기 위해 포인터를 다음으로 변환할 수 있습니다.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);
}

이 구현은 각 반복에 대해 추가 포인터 비교를 수행하지 않습니다.우리가 그 대가로 지불하는 것은 그것이 일찍 끝나는 대신 항상 한 줄의 끝까지 반복된다는 것입니다.하지만 여전히 구현보다 더 효율적입니다.strlen단 한 번

언급URL : https://stackoverflow.com/questions/17559977/is-this-a-correct-and-portable-way-of-checking-if-2-c-strings-overlap-in-memory