std::set_intersection принимает отсортированные диапазоны элементов (ну, пары итераторов). Но предположим, что у меня есть несортированные данные, например. два std::unordered_set с. Есть ли стандартный объект для их пересечения?
std::set_intersection для отсортированных диапазонов, а [ _ ] для несортированных диапазонов/контейнеров
comment
связанные: объединение и пересечение tr1::unordered_set. Это предстандартные имена. Также не полное решение, поэтому от меня нет фактического близкого голосования.
- person NathanOliver schedule 03.05.2016
Ответы (2)
В этом случае нет короткого пути. Вы должны проверить каждый элемент меньшего набора на принадлежность к большему набору и вставить его в выходной набор, если он найден. Поскольку unordered_set реализован с использованием хэша с сегментами, время поиска должно быть небольшим (при хорошей хэш-функции и разумной максимальной загрузке хэша). Вы должны иметь возможность написать вызов for_each для меньшего набора, который выполняет проверку большего и вставляет в выходной набор, не получая слишком уродливых.
Если вы хотите построить пересечение на месте в одном из двух исходных наборов, вы можете проверить, находится ли каждый из его элементов в другом наборе, и удалить этот элемент, если нет. Это можно записать с помощью remove_if для unordered_set, в котором будет храниться результат.
Еще один вариант — использовать copy_if с итератором вставки. Есть много вариантов сделать это в том же времени и пространстве. Выберите тот, который кажется оптимизированным для ясности.
Я не знаю ни одной готовой библиотечной функции, которая просто сделает это за вас.
person
Thomas Kammeyer
schedule
03.05.2016
Это даст вам объединение, а не пересечение, и функция, которая это сделает,
s1.insert(s2.begin(), s2.end())
- person Jonathan Wakely; 03.05.2016
Бларг. Большое спасибо. Отвлекся, подумав об этом, и ответил не на тот вопрос. Я отредактировал свой ответ.
- person Thomas Kammeyer; 03.05.2016
Я не знаю ни одной такой функции в С++ 11. Ответ - нет".
person
R Sahu
schedule
03.05.2016
