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

Посмотрите образец в ссылке:
http://en.cppreference.com/w/cpp/algorithm/set_intersection

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

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));

Увидеть станд :: set_intersection. Вы должны добавить выходной итератор, где вы будете хранить результат:

#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));

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

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

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (first1!=last1 && first2!=last2)
{
if (*first1<*first2) ++first1;
else if (*first2<*first1) ++first2;
else {
*result = *first1;
++result; ++first1; ++first2;
}
}
return result;
}

скопировано с http://www.cplusplus.com/reference/algorithm/set_intersection/

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

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

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

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

• operator *() для пересечения множеств
• operator +() для объединения множеств.

Образец test-set-ops.cc:

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

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator * (
const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
std::set<T, CMP, ALLOC> s;
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(s, s.begin()));
return s;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator + (
const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
std::set<T, CMP, ALLOC> s;
std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(s, s.begin()));
return s;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
const char *sep = " ";
for (const T &value : values) {
out << sep << value; sep = ", ";
}
return out;
}

int main()
{
set<int> s1 { 1, 2, 3, 4 };
cout << "s1: {" << s1 << " }" << endl;
set<int> s2 { 0, 1, 3, 6 };
cout << "s2: {" << s2 << " }" << endl;
cout << "I: {" << s1 * s2 << " }" << endl;
cout << "U: {" << s1 + s2 << " }" << endl;
return 0;
}

Составлено и протестировано:

$ g++ -std=c++11 -o test-set-ops test-set-ops.cc

$ ./test-set-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
I: { 1, 3 }
U: { 0, 1, 2, 3, 4, 6 }

$

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

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

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

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

• operator *=() для «деструктивного» пересечения множеств
• operator +=() за «разрушительное» объединение множеств.

Образец test-set-assign-ops.cc:

#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator *= (
std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
auto iter1 = s1.begin();
for (auto iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
if (*iter1 < *iter2) iter1 = s1.erase(iter1);
else {
if (!(*iter2 < *iter1)) ++iter1;
++iter2;
}
}
while (iter1 != s1.end()) iter1 = s1.erase(iter1);
return s1;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator += (
std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
s1.insert(s2.begin(), s2.end());
return s1;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
const char *sep = " ";
for (const T &value : values) {
out << sep << value; sep = ", ";
}
return out;
}

int main()
{
set<int> s1 { 1, 2, 3, 4 };
cout << "s1: {" << s1 << " }" << endl;
set<int> s2 { 0, 1, 3, 6 };
cout << "s2: {" << s2 << " }" << endl;
set<int> s1I = s1;
s1I *= s2;
cout << "s1I: {" << s1I << " }" << endl;
set<int> s2I = s2;
s2I *= s1;
cout << "s2I: {" << s2I << " }" << endl;
set<int> s1U = s1;
s1U += s2;
cout << "s1U: {" << s1U << " }" << endl;
set<int> s2U = s2;
s2U += s1;
cout << "s2U: {" << s2U << " }" << endl;
return 0;
}

Составлено и протестировано:

$ g++ -std=c++11 -o test-set-assign-ops test-set-assign-ops.cc

$ ./test-set-assign-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
s1I: { 1, 3 }
s2I: { 1, 3 }
s1U: { 0, 1, 2, 3, 4, 6 }
s2U: { 0, 1, 2, 3, 4, 6 }

$