Может быть, не самый эффективный способ, но он правильный и портативный?
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
Да, ваш код верен. Если две строки заканчиваются на месте выборки, они по определению перекрываются - они имеют один и тот же нулевой ограничитель. Либо обе строки одинаковы, либо одна подстрока другой.
Все, что касается вашей программы, - это совершенно четкое поведение, поэтому, принимая компиляторы, совместимые со стандартами, оно должно быть совершенно портативным.
Соответствующий бит в стандарте от 6.5.9 Операторы равенства (основное внимание):
Два указателя сравнивают равные, если и только если оба являются нулевыми указателями, оба являются указателями на один и тот же объект (включая указатель на объект и подобъект в начале ) или функция, оба являются указателями на один из последних элементов одного и того же объекта массива, или один - указатель на один конец конца одного объекта массива, а другой - указатель на начало другой объект массива, который происходит сразу после первого объекта массива в адресном пространстве.
Размышляя о комментариях zdan к моему предыдущему сообщению (который, вероятно, вскоре будет удален), я пришел к выводу, что проверка конечных точек достаточно.
Если существует какое-либо перекрытие, нулевой ограничитель сделает две строки не различными. Давайте посмотрим на некоторые возможности.
Если вы начинаете с
a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",
у вас будет одно слово: HellWorld, так как W перезапишет \0. Они заканчивались бы в той же конечной точке.
Если вы каким-то образом напишите в ту же отправную точку:
a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"
У вас будет слово Юпитер и будет иметь ту же конечную точку.
Есть ли случай, когда вы можете иметь одну и ту же конечную точку и не иметь перекрытия? Вид.
a = 0x1000000 "Four" and
b = 0x1000004 "".
Это также даст перекрытие.
Я не могу думать, что когда-нибудь у вас будет перекрытие, где у вас не будет соответствующих конечных точек - предполагается, что вы записываете в конец строки с нулевым завершением.
Итак, короткий ответ: Да, ваш чек достаточно.
Вероятно, это не относится к вашему варианту использования, так как ваш вопрос касается только C-строк, но код не будет работать в том случае, если данные имеют встроенные NUL-байты в строках.
char a[] = "abcd\0ABCD";
char *b = a + 5;
Кроме этого, ваше решение прямолинейно и правильно. Он работает, поскольку вы используете == для сравнения указателей и в соответствии со стандартом (от C11 6.5.9/6)
Два указателя сравнивают одинаковые, если и только если оба являются нулевыми указателями, оба являются указателями на один и тот же объект (включая указатель на объект и подобъект в начале) или функцию, оба являются указателями на один из последних элементов один и тот же объект массива, или один - указатель на один конец конца одного объекта массива, а другой - указатель на начало другого объекта массива, который происходит сразу после первого объекта массива в адресном пространстве.
Однако реляционные операторы более строгие (из C11 6.5.8/5):
При сравнении двух указателей результат зависит от относительных местоположений в адресном пространстве объектов, на которые указывает. Если два указателя на типы объектов указывают на один и тот же объект или оба указывают один за последним элементом одного и того же объекта массива, они сравнивают равные. Если объекты, на которые указывают, являются членами одного и того же совокупного объекта, указатели на элементы структуры, объявленные позже, сравниваются больше, чем указатели на элементы, объявленные ранее в структуре, а указатели на элементы массива с большими значениями индекса сравниваются больше, чем указатели на элементы одного и того же массива с нижними значениями индекса. Все указатели на члены одного и того же объекта объединения сравниваются одинаково. Если выражение P указывает на элемент объекта массива, а выражение Q указывает на последний элемент одного и того же объекта массива, выражение указателя Q + 1 сравнивается больше P. Во всех остальных случаях поведение undefined.
Последнее предложение - это кикер.
Некоторые из них сделали исключение из того, что ваш код может дважды вычислить длину перекрытия и попытался принять меры предосторожности, чтобы избежать этого. Тем не менее, эффективность сокращения этого вычисления сравнивается с дополнительным сравнением указателя на итерацию или включает в себя undefined или поведение, определенное реализацией. Предполагая, что вам требуется портативное и совместимое решение, фактический средний коэффициент усиления, вероятно, равен нулю, и не стоит усилий.
Это решение по-прежнему является одной и той же наихудшей производительностью, но оптимизировано для хитов - вам не нужно разбирать обе строки.
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;
}
Важное замечание об этой версии состоит в том, что он выполняет реляционное сравнение двух указателей, которые не гарантируют указание на один и тот же массив, что формально приводит к поведению undefined. Он будет работать на практике в системе с плоской моделью памяти, но может привлечь критику от рецензента педантичного кода. Чтобы формально обойти эту проблему, можно преобразовать указатели в uintptr_t перед выполнением реляционных сравнений. Таким образом, поведение undefined преобразуется в поведение, определенное реализацией, с правильной семантикой для наших целей в большинстве (если не всех) традиционных реализаций с плоской моделью памяти.
Этот подход свободен от проблемы "двойного счета": он анализирует неперекрывающуюся часть строки, которая находится "раньше" в памяти. Конечно, на практике преимущества такого подхода могут оказаться несуществующими. Это будет зависеть как от качества вашей реализации 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 только один раз.