Я пытался найти пересечение между двумя std :: set в C ++, но все время получаю сообщение об ошибке.
Я создал небольшой образец теста для этого
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
set<int> s1;
set<int> s2;
s1.insert(1);
s1.insert(2);
s1.insert(3);
s1.insert(4);
s2.insert(1);
s2.insert(6);
s2.insert(3);
s2.insert(0);
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
return 0;
}
Последняя программа не генерирует никакого вывода, но я ожидаю получить новый набор (назовем его s3
) со следующими значениями:
s3 = [ 1 , 3 ]
Вместо этого я получаю сообщение об ошибке:
test.cpp: In function ‘int main()’:
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)’
Что я понимаю из этой ошибки, так это то, что в ней нет определения, set_intersection
которое принимает в Rb_tree_const_iterator<int>
качестве параметра.
Кроме того, я полагаю, что std::set.begin()
метод возвращает объект такого типа,
есть ли лучший способ найти пересечение двух std::set
в C ++? Желательно встроенную функцию?
Большое спасибо!
c++
std
stl-algorithm
stdset
Я люблю тако
источник
источник
Ответы:
Вы не предоставили итератор вывода для set_intersection
template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result );
Исправьте это, выполнив что-то вроде
...; set<int> intersect; set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));
Вам нужен
std::insert
итератор, поскольку на данный момент набор пуст. Мы не можем использовать back_ или front_inserter, поскольку set не поддерживает эти операции.источник
set<T>& set::isect(set<T>&)
метод, который сделает все необходимое? (Я бы попросилset<T>& set::operator^(set<T>&)
, но это, вероятно, слишком далеко.)<algorithm>
если не что иное, как согласованность. Я полагаю, что этот стиль также дает вам гибкость. И позволяет использовать алгоритмы с несколькими контейнерами, хотя здесь этого может и не произойти .. Также ваша подпись может не работать, вам, вероятно, потребуется вернуть значение. И я думаю, что в те дни, когда еще не было семантики копирования, она была бы двойной копией. Я уже некоторое время не занимаюсь C ++, так что возьмите это с щепоткой илиset
контейнера, который пересекается с другим набором. Тема передачи контейнера вместо.begin()
-.end()
это другое дело - это будет исправлено, когда в 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));
источник
back_inserter
не работает, такset
какset
не имеетpush_back
функции.См. Std :: set_intersection . Вы должны добавить итератор вывода, в котором вы будете хранить результат:
#include <iterator> std::vector<int> s3; set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));
См. Полный список в Ideone .
источник
Просто прокомментируйте здесь. Думаю, пора добавить операцию объединения, пересечения в заданный интерфейс. Предложим это в будущих стандартах. Я давно использую стандартную операцию, и каждый раз, когда я использовал операцию установки, мне хотелось, чтобы она была лучше. Для некоторых сложных операций над множеством, таких как пересечение, вы можете просто (проще?) Изменить следующий код:
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. Однако с вектором это не сработает.
источник
Первый (получивший хорошее голосование) комментарий принятого ответа жалуется на отсутствие оператора для существующих операций стандартного набора.
С одной стороны, я понимаю отсутствие таких операторов в стандартной библиотеке. С другой стороны, при желании их легко добавить (для личного удовольствия). Я перегружен
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)
: вуаля - ход конструктора. Спасибо, Олаф, за (мое) просветление.Для полноты картины я также реализовал соответствующие операторы присваивания
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 } $
источник
std::set
уже реализует необходимый конструктор перемещения и оператор присваивания, поэтому не нужно об этом беспокоиться. Также компилятор, скорее всего, использует оптимизацию возвращаемого значения