Какими функциями заменить array_diff() в Си?

Question

[YukhaDav]

Реализовать функцию разности массивов, которая вычитает один массив из другого и возвращает результат.
Следует удалить все значения из списка a, которые есть в списке b, сохраняя их порядок.
Я знаю, что на других есть array_diff(), но как заменить его здесь?

Comments

[mayton2019]

Сразу замечание. Ты в одном тексте задания меняешь массив на список.

Ты определись что тебе надо точнее. Начни с хедера твоей функции.

Answer 1

[Wataru]

Руками. Если лень писать свою хеш таблицу, то можно и совсем в тупую. Итерируйтесь по списку a. Внутри итерируйтесь по списку b и, если нашли там элемент, то удаляйте из a. Иначе переходите к следующему элементу.

Более продвинутый вариант - отсортировать список b и искать там каждый элемент из a бинарным поиском.

Удобный трюк для удаления элементов из массива - хранить индекс первого не занятого элемента. Тогда получается что-то вроде этого:

int empty_pos = 0;
for (int i = 0; i < n; ++i) {
  if (!ShouldDelete(a[i], b)) {
    a[empty_pos++] = a[i];
  }
}
n = empty_pos;

Comments

[mayton2019]

Чтобы разность множеств сработала однозначно, нам нужно понимание того что делать с дубликатами элементов.

[Wataru]

mayton2019, Похоже тут все просто. В вопросе:

удалить все значения из списка a, которые есть в списке b

. Если элемент встречается в b, неважно сколько раз, все его вхождения в a надо удалить. Оставить только те, что не всречаются в b. array_diff, упомянутый в вопросе, работает точно так же.

Альтернативное понимание, что надо удалить из a элементы столько раз, сколько они встречаются в b, слишком заумно, сложно формализуемо, имеет мало практического смысла, и при этом его гораздо сложнее натянуть на условие в вопросе.

[mayton2019]

Wataru, согласен. Будем игнорировать мультимножество. Работаем только с множествами.