Краткий ответ

Код не компилируется, потому что std::back_inserter пытается добавлять элементы через push_back, а у std::set такого метода нет. Для ассоциативного контейнера следует использовать std::inserter, который вызывает вставку через insert.

Исправленный вызов выглядит так:

std::set_difference(a.begin(), a.end(),
                    b.begin(), b.end(),
                    std::inserter(result, result.end()));

Исторический контекст

Алгоритмы STL отделены от конкретного контейнера: алгоритм работает с диапазонами и выходным итератором, не зная, куда именно записываются результаты. Это позволяет применять один и тот же std::set_difference к вектору, списку или множеству.

Адаптеры выходных итераторов связывают общий алгоритм с интерфейсом конкретного контейнера. std::back_inserter предназначен для контейнеров с push_back, а std::inserter — для контейнеров, вставляющих элементы через insert.

Постановка проблемы

std::back_inserter(result) при присваивании очередного результата логически выполняет операцию result.push_back(value). Контейнер std::set хранит уникальные ключи в упорядоченном виде и предоставляет insert, но не предоставляет push_back, поскольку понятия «конец последовательности» для него недостаточно для сохранения инварианта сортировки.

Даже если заменить контейнер на такой, у которого есть push_back, диапазоны для std::set_difference должны быть отсортированы по совместимому сравнению. В данном примере это условие выполняется благодаря упорядоченному обходу std::set.

Подробное решение

std::inserter(result, hint) создаёт итератор-адаптер, который при записи вызывает примерно такую операцию:

result.insert(hint, value);

После вставки адаптер обновляет позицию подсказки. Поэтому он подходит для std::set, std::multiset, std::map и std::multimap, где добавление выполняется через insert, а не через операции последовательного контейнера.

Для этого примера корректный вариант таков:

#include <algorithm>
#include <iterator>
#include <set>

int main() {
    std::set<int> a{1, 2, 3};
    std::set<int> b{2, 3, 4};
    std::set<int> result;

    std::set_difference(a.begin(), a.end(),
                        b.begin(), b.end(),
                        std::inserter(result, result.end()));
}

Результатом будет множество {1}. Алгоритм требует отсортированные входные диапазоны и записывает элементы в выходной диапазон; он не обязан знать, является ли выход контейнером или, например, потоком.

Сложность сравнения входных диапазонов составляет линейное время относительно их размеров. Вставка в std::set обычно имеет сложность O(log M), где M — размер множества, но корректная подсказка может сделать вставку амортизированно константной. В данном случае результаты формируются в возрастающем порядке, поэтому передача актуального конца множества обычно является подходящей подсказкой.

std::back_inserter остаётся правильным выбором для std::vector, std::deque и std::list, поскольку эти контейнеры поддерживают push_back. Для фиксированного std::array он не подходит: размер такого контейнера нельзя увеличивать.

Ситуация из практики

Сервис формирует разницу двух наборов идентификаторов. Разработчик выбрал std::vector результата и std::back_inserter: это просто, совместимо с контейнером и обычно эффективно благодаря последовательному хранению элементов. Однако такой результат допускает дубликаты, если входные диапазоны не являются множествами с нужной семантикой.

Другой вариант — сразу записывать в std::set через std::inserter. Он автоматически сохраняет уникальность и порядок, но каждый элемент потенциально требует поиска позиции в дереве и узлы множества хуже используют кэш процессора.

Если результат далее нужен только для последовательного чтения, выбран бы std::vector с back_inserter. Если же требуется поддерживать уникальность и выполнять последующие операции поиска по ключу, обоснован выбор std::set с inserter. Это устраняет ошибку адаптера и сохраняет требуемую семантику результата.

Что кандидаты часто упускают

Вопрос: Можно ли использовать std::inserter для std::vector?

Ответ: Да, технически можно: адаптер будет вызывать vector.insert(position, value). Но для добавления в конец это обычно хуже, чем std::back_inserter, потому что вставка в середину вектора сдвигает элементы и может иметь линейную сложность. Для последовательного добавления в конец следует использовать back_inserter.
Вопрос: Почему нельзя подавать в std::set_difference неотсортированные диапазоны?

Ответ: Алгоритм использует упорядоченное сравнение двух диапазонов и продвигает итераторы, не проверяя все пары элементов. Без сортировки его логика не гарантирует правильный результат. Сортировка должна быть выполнена тем же отношением порядка или совместимым с ним.
Вопрос: Что произойдёт, если выходной диапазон пересекается с одним из входных?

Ответ: Для std::set_difference такое перекрытие не следует использовать без проверки требований конкретного алгоритма: запись результата может изменить элементы, которые алгоритм ещё должен прочитать. Надёжный вариант — выводить результат в отдельный контейнер или в заранее безопасный непересекающийся диапазон.