Set intersection c что это

std::sort(second, second + 5);

std::cout «First array :» ;

std::cout «Second array :» ;

ls = std::set_intersection(first, first + 5, second, second + 5, v1.begin());

std::cout «The intersection has » » elements:» ;

2. Сравнивая, используя предопределенную функцию:
Synatax:

// Программа CPP для иллюстрации
// std :: set_intersection

bool comp( int a, int b)

int n = sizeof (first) / sizeof (first[0]);

std::vector int > v1(5);

std::vector int > v2(5);

std::vector int >::iterator it, ls;

std::sort(first, first + 5);

std::sort(second, second + 5);

std::cout «First array :» ;

std::cout «Second array :» ;

ls = std::set_intersection(first, first + 5, second, second + 5, v1.begin(), comp);

std::cout «The intersection has » » elements:» ;

Возможное применение: используется для поиска элементов, присутствующих только в обоих наборах.

1. С его помощью можно найти список учеников, присутствующих в обоих классах.

using namespace std;

int n = sizeof (first) / sizeof (first[0]);

// Распечатать студентов первого списка

cout «Students in first class :» ;

// Распечатать студентов второго списка

cout «Students in second class :» ;

vector ::iterator it, st;

// Сортировка обоих списков

sort(first, first + n);

sort(second, second + n);

// Используем оператор по умолчанию

it = set_intersection(first, first + n, second, second + n, v.begin());

cout «Students attending both the classes only are :\n» ;

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Источник

как найти пересечение двух std:: set в C++?

Я пытался найти пересечение между двумя std:: set в C++, но я продолжаю получать ошибку.

Я создал небольшой образец теста для этого

последняя программа не генерирует никаких выходных данных, но я ожидаю, что у меня будет новый набор (назовем его s3 ) со следующими значениями:

вместо этого я получаю ошибку:

что я понимаю из этой ошибки, так это то, что в set_intersection что принимает Rb_tree_const_iterator в качестве параметра.

кроме того, я полагаю std::set.begin() метод возвращает объект такого типа,

есть ли лучший способ найти пересечение двух std::set в C++? Предпочтительно встроенная функция?

5 ответов

вы не предоставили выходной итератор для set_intersection

исправьте это, сделав что-то вроде

вам понадобится std::insert итератор, так как набор на данный момент пуст. Мы не можем использовать back_ или front_inserter, так как set не поддерживает эти операции.

вам нужен другой контейнер для хранения данных пересечения, ниже кода, который должен работать:

посмотреть std:: set_intersection. Необходимо добавить выходной итератор, в котором будет сохранен результат:

посмотреть Ideone для полного списка.

просто комментарий здесь. Я думаю, что пришло время добавить операцию union, intersect в интерфейс set. Давайте предложим это в будущих стандартах. Я использую std в течение длительного времени, каждый раз, когда я использовал операцию набора, я хотел, чтобы std был лучше. Для некоторых сложных операций набора, таких как intersect, вы можете просто (проще?) изменить следующий код:

например, если ваш вывод является набором, вы можете выводить.вставка(*first1). Кроме того, ваша функция не может быть шаблонной.Если код может быть короче, чем с помощью функции std set_intersection, продолжайте.

Если вы хотите сделать объединение двух наборов, вы можете просто setA.вставка(setB.begin (), setB.end ()); Это намного проще, чем метод set_union. Однако, это не будет работать с вектор.

первый (хорошо проголосованный) комментарий принято отвечать жалуется на отсутствие оператора для существующих операций набора std.

С одной стороны, я понимаю, что отсутствие таких операторов в стандартной библиотеке. С другой стороны, при желании их легко добавить (для личной радости). Я перегружен

собран и протестирован:

мне не нравится копия возвращаемых значений в операторах. Может быть, это можно решить с помощью задания перемещения, но это все еще за пределами моих навыков.

из-за моих ограниченных знаний об этой семантике перемещения «новой фантазии» я был обеспокоен возвратами оператора, которые могут вызвать копии возвращаемых наборов. Олаф Жи Dietsche указал, что эти опасения излишни, как std::set уже оснащен конструктором/назначением перемещения.

хотя я верил ему, я думал, как это проверить (что-то вроде «самовнушение»). На самом деле, это довольно легко. Поскольку шаблоны должны быть предоставлены в исходном коде, вы можете просто пройти через отладчик. Таким образом, я поставил точку разрыва прямо на return s; на operator *() и продолжил с одноступенчатым шагом, который привел меня немедленно в std::set::set(_myt&& _Right) : et voilà-the move конструктор. Спасибо, Олаф, за (мое) просвещение.

для полноты я также реализовал соответствующие операторы присваивания

Источник

Когда не нужно использовать алгоритмы из STL

Я боролся с соблазном назвать статью как-то типа «Ужасающая неэффективность алгоритмов STL» — ну, знаете, просто ради тренировки в мастерстве создания кричащих заголовков. Но всё же решил оставаться в рамках приличий — лучше получить от читателей комментарии по содержанию статьи, чем негодование по поводу её громкого названия.

В этом месте я предположу, что вы немного знаете С++ и STL, а также заботитесь об используемых в вашем коде алгоритмах, их сложности и соответствия поставленным задачам.

Алгоритмы

Одним из хорошо известных советов, которые вы можете услышать от современного сообщества разработчиков на С++, будет не придумывать велосипеды, а использовать алгоритмы из стандартной библиотеки. Это хороший совет. Данные алгоритмы безопасны, быстры, проверены годами. Я тоже часто даю совет применять их.

Каждый раз, когда вам хочется написать очередной for — следует сначала вспомнить, нет ли в STL (или в boost) чего-то, что уже решает эту задачу в одну строку. Если есть — чаще лучше использовать это. Нам, однако, и в этом случае следует понимать, что за алгоритм лежит за вызовом стандартной функции, каковы его характеристики и ограничения.

Обычно, если наша проблема в точности совпадает с описанием алгоритма из STL, будет хорошей идеей взять и применить его «в лоб». Беда только в том, что данные не всегда хранятся в том виде, в котором их хочет получить реализованный в стандартной библиотеке алгоритм. Тогда у нас может возникнуть идея сначала преобразовать данные, а потом всё же применить тот же алгоритм. Ну, знаете, как в том анекдоте про математика «Затушить огонь из чайника. Задача сведена к предыдущей».

Пересечение множеств

Представьте, что мы пытаемся написать инструмент для программистов на С++, который будет находить в коде все лямбды с захватом всех переменных по умолчанию ([=] и [&]) и выводить советы по преобразованию их в лямбды с конкретным списком захватываемых переменных. Как-то вот так:

По ходу разбора файла с кодом, нам придётся где-то хранить коллекцию переменных в текущей и окружающей области видимости, а при обнаружении лямбды с захватом всех переменных сравнить эти две коллекции и дать совет по её преобразованию.

Одно множество с переменными родительской области видимости, и ещё одно с переменными внутри лямбды. Для формирования совета разработчику нужно всего лишь найти их пересечение. И это тот случай, когда описание алгоритма из STL просто идеально подходит к задаче: std::set_intersection принимает два множества и возвращает их пересечение. Алгоритм прекрасен в своей простоте. Он принимает две отсортированные коллекции и проходит по ним параллельно:

C каждым шагом алгоритма мы движемся по первой, второй или обеим коллекциями, а значит сложность данного алгоритма будет линейной — О(m + n), где n и m — это размеры коллекций.

Просто и эффективно. Но это лишь пока входные коллекции отсортированы.

Сортировка

Проблема в том, что в общем случае коллекции не отсортированы. В нашем конкретном случае удобно хранить переменные в какой-нибудь стеко-подобной структуре данных, добавляя переменные на очередной уровень стека при входе во вложенную область видимости и удаляя их из стека при выходе из данной области видимости.

Это означает, что переменные не будут отсортированы по имени и мы не можем напрямую использовать std::set_intersection на их коллекциях. Поскольку std::set_intersection требует на входе именно отсортированные коллекции, может возникнуть мысль (и я часто видел такой подход в реальных проектах) отсортировать коллекции перед вызовом библиотечной функции.

Сортировка в данном случае убьёт всю идею использования стека для хранения переменных соответственно их областям видимости, но всё же это возможно:

Какова сложность полученного алгоритма? Что-то типа O(n log n + m log m + n + m) — квазилинейная сложность.

Меньше сортировок

Можем ли мы не использовать сортировку? Можем, почему бы и нет. Просто будем искать каждый элемент из первой коллекции во второй, линейным поиском. Получим сложность O(n * m). И этот подход я также видел в реальных проектах достаточно часто.

Вместо вариантов «сортировать всё» и «не сортировать ничего» мы можем попробовать найди Дзен и пойти третьим путём — сортировать лишь одну из коллекций. Если одна из коллекций будет отсортирована, а вторая нет, то мы сможем перебирать элементы неотсортированной коллекции по одному и искать их в отсортированной бинарным поиском.

Сложность этого алгоритма будет составлять O(n log n) для сортировки первой коллекции и O (m log n) для поиска и проверки. В сумме получим сложность O((n + m) log n).

Если мы решим отсортировать другую из коллекций, то получим сложность O((n + m) log m). Как вы понимаете, логичным здесь будет сортировать коллекцию меньшего размера для получения итоговой сложности О((m + n) log (min(m, n))

Реализация будет выглядеть вот так:

В нашем примере с лямбда-функциями и захватом переменных, коллекцией, которую мы будем сортировать, обычно будет коллекция переменных, используемых в коде лямбда-функции, поскольку их, скорее всего, будет меньше, чем переменных в окружающей лямбду области видимости.

Хеширование

И последней рассматриваемой в данной статье опцией будет использование хеширования для меньшей коллекции вместо её сортировки. Это даст нам возможность искать в ней за О(1), хотя само построение хеша, конечно, займёт некоторое время (от O(n) до O(n*n), что может стать проблемой):

Подход с хешированием будет абсолютным победителем в случае, когда нашей задачей является последовательно сравнить некоторое небольшое множество А с набором других (больших) множеств B₁, B₂, В…. В этом случае нам нужно построить хеш для А лишь один раз, а использовать его мгновенный поиск можно будет для сравнения с элементами всех рассматриваемых множеств В.

Тест производительности

Всегда полезно подтвердить теорию практикой (особенно в случаях подобно последнему, когда не ясно, окупятся ли первоначальные затраты на хеширование приростом производительности на поиске).

В моих тестах первый вариант (с сортировкой обеих коллекций) всегда показывал худшие результаты. Сортировка одной лишь меньшей коллекции работала чуть лучше на коллекциях одинаковых размеров, но не слишком. Но и второй и третий алгоритм показали очень существенный прирост производительности (примерно в 6 раз) в случаях, когда одна из коллекций была в 1000 раз больше другой.

Источник

алгоритм — функция сравнения c_set_intersection

Двоичная функция, которая принимает два аргумента типов, указанных
входные итераторы, и возвращает значение, конвертируемое в bool. Значение
возвращенный указывает, считается ли первый аргумент доступным
перед вторым в конкретном строгом слабом порядке это определяет.
Функция не должна изменять ни один из своих аргументов. Это может быть
указатель на функцию или функциональный объект.

Он описывает, что функция должна возвращать порядок двух аргументов. Но как насчет функции сопоставления, например:

Мы получаем результаты:

Как интерпретировать результаты, и как правильно написать функцию сравнения при использовании функции, и как написать тот, который может дать мне ожидаемые результаты?

Решение

std::set_intersection ожидает функцию, которая связывает два элемента так же, как они хранятся в наборе. Это не функция для описания того, какие элементы одинаковы, потому что эта функция работает внутри.

Итак, в вашем примере, set1 не является правильным набором, потому что он не в порядке (в порядке возрастания, например). Если бы это было в порядке, вы могли бы использовать в std::set_intersection та же функция заказа. Например:

Возможность явно сказать, какую функцию заказа вы хотите использовать, полезна, когда вы имеете дело со сложными объектами, которые не имеют неявного порядка. Например:

Другие решения

Источник

how to find the intersection of two std::set in C++?

I have been trying to find the intersection between two std::set in C++, but I keep getting an error.

I created a small sample test for this

The latter program does not generate any output, but I expect to have a new set (let’s call it s3 ) with the following values:

Instead I’m getting the error:

What I understand out of this error, is that there’s no definition in set_intersection that accepts Rb_tree_const_iterator as parameter.

Furthermore, I suppose the std::set.begin() method returns an object of such type,

is there a better way to find the intersection of two std::set in C++? Preferably a built-in function?

5 Answers 5

You haven’t provided an output iterator for set_intersection

Fix this by doing something like

You need a std::insert iterator since the set is as of now empty. We cannot use std::back_inserter or std::front_inserter since set doesn’t support those operations.

You need another container to store the intersection data, below code suppose to work:

See std::set_intersection. You must add an output iterator, where you will store the result:

See Ideone for full listing.

The first (well-voted) comment of the accepted answer complains about a missing operator for the existing std set operations.

On one hand, I understand the lack of such operators in the standard library. On the other hand, it is easy to add them (for the personal joy) if desired. I overloaded

Compiled and tested:

What I don’t like is the copy of return values in the operators. May be, this could be solved using move assignment but this is still beyond my skills.

Due to my limited knowledge about these «new fancy» move semantics, I was concerned about the operator returns which might cause copies of the returned sets. Olaf Dietsche pointed out that these concerns are unnecessary as std::set is already equipped with move constructor/assignment.

Although I believed him, I was thinking how to check this out (for something like «self-convincing»). Actually, it is quite easy. As templates has to be provided in source code, you can simply step through with the debugger. Thus, I placed a break point right at the return s; of the operator *() and proceeded with single-step which leaded me immediately into std::set::set(_myt&& _Right) : et voilà – the move constructor. Thanks, Olaf, for the (my) enlightment.

For the sake of completeness, I implemented the corresponding assignment operators as well

Источник