Próbowałem znaleźć punkt przecięcia między dwoma std :: ustawionymi w C ++, ale ciągle otrzymuję błąd.
Stworzyłem do tego mały przykładowy test
#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;
}
Ten ostatni program nie generuje żadnych danych wyjściowych, ale spodziewam się, że będzie miał nowy zestaw (nazwijmy go s3
) z następującymi wartościami:
s3 = [ 1 , 3 ]
Zamiast tego otrzymuję błąd:
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>)’
Z tego błędu rozumiem, że nie ma definicji, set_intersection
która akceptuje Rb_tree_const_iterator<int>
jako parametr.
Ponadto przypuszczam, że std::set.begin()
metoda zwraca obiekt tego typu,
czy jest lepszy sposób na znalezienie przecięcia dwóch std::set
w C ++? Preferowana funkcja wbudowana?
Wielkie dzięki!
c++
std
stl-algorithm
stdset
Lubię tacos
źródło
źródło
Odpowiedzi:
Nie dostarczyłeś iteratora wyjścia dla set_intersection
template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result );
Napraw to, wykonując coś takiego
...; set<int> intersect; set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));
Potrzebujesz
std::insert
iteratora, ponieważ zbiór jest teraz pusty. Nie możemy użyć back_ lub front_inserter, ponieważ set nie obsługuje tych operacji.źródło
set<T>& set::isect(set<T>&)
metoda, która nie jest potrzebna? (Poprosiłbym oset<T>& set::operator^(set<T>&)
, ale to prawdopodobnie most za daleko.)<algorithm>
takiej spójności, jeśli nic innego. Zakładam, że ten styl również zapewnia elastyczność. I pozwala na użycie algorytmów z kilkoma kontenerami, chociaż może się to nie zdarzyć w tym przypadku. Twój podpis może również nie działać, prawdopodobnie będziesz musiał zwrócić wartość. I myślę, że w czasach poprzedzających semantykę kopiowania byłaby to podwójna kopia. Od jakiegoś czasu nie robiłem c ++, więc weź to ze szczyptą lub 3 soląset
kontenera, która wykonuje przecięcie z innym zestawem. Temat przekazywania kontenera zamiast.begin()
-.end()
to inna sprawa - zostanie to naprawione, gdy C ++ będzie miał koncepcje.Zobacz przykład w linku: http://en.cppreference.com/w/cpp/algorithm/set_intersection
Potrzebujesz innego kontenera do przechowywania danych o skrzyżowaniu, poniższy kod powinien działać:
std::vector<int> common_data; set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));
źródło
back_inserter
nie działa,set
ponieważset
nie mapush_back
funkcji.Zobacz std :: set_intersection . Musisz dodać iterator wyjściowy, w którym będziesz przechowywać wynik:
#include <iterator> std::vector<int> s3; set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));
Zobacz Ideone, aby uzyskać pełną listę.
źródło
Po prostu skomentuj tutaj. Myślę, że nadszedł czas, aby dodać połączenie, przecięcie operacji do zestawu interfejsu. Zaproponujmy to w przyszłych standardach. Używam std przez długi czas, za każdym razem, gdy korzystałem z operacji set, chciałem, aby std było lepsze. W przypadku niektórych skomplikowanych operacji na zbiorach, takich jak przecięcie, możesz po prostu (łatwiej?) Zmodyfikować następujący kod:
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; }
skopiowane z http://www.cplusplus.com/reference/algorithm/set_intersection/
Na przykład, jeśli wyjście jest zbiorem, możesz output.insert (* first1). Co więcej, funkcja może nie podlegać szablonowi.Jeśli kod może być krótszy niż przy użyciu funkcji std set_intersection, kontynuuj go.
Jeśli chcesz zrobić sumę dwóch zbiorów, możesz po prostu ustawićA.insert (setB.begin (), setB.end ()); Jest to znacznie prostsze niż metoda set_union. Jednak to nie zadziała z wektorami.
źródło
Pierwszy (dobrze przegłosowany) komentarz zaakceptowanej odpowiedzi narzeka na brak operatora dla istniejących operacji na zestawie standardowym.
Z jednej strony rozumiem brak takich operatorów w standardowej bibliotece. Z drugiej strony łatwo jest je dodać (dla osobistej radości) w razie potrzeby. Przeładowałem
operator *()
do przecinania zbiorówoperator +()
do łączenia zbiorów.Próbka
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; }
Skompilowane i przetestowane:
$ 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 } $
To, co mi się nie podoba, to kopia wartości zwracanych w operatorach. Być może można to rozwiązać za pomocą przypisania ruchu, ale wciąż przekracza to moje umiejętności.Ze względu na moją ograniczoną wiedzę na temat semantyki tych "nowych fantazyjnych" ruchów, obawiałem się o zwroty operatora, które mogą powodować kopie zwracanych zestawów. Olaf Dietsche zwrócił uwagę, że te obawy są niepotrzebne, ponieważ
std::set
jest już wyposażony w konstruktora przenoszenia / przypisanie.Chociaż mu wierzyłem, zastanawiałem się, jak to sprawdzić (coś w rodzaju „przekonania do siebie”). Właściwie to całkiem proste. Ponieważ szablony muszą być dostarczane w kodzie źródłowym, możesz po prostu przejść przez debuger. W ten sposób umieściłem punkt przerwania na samym
return s;
początkuoperator *()
i przeszedłem do jednego kroku, który natychmiast zaprowadził mnie dostd::set::set(_myt&& _Right)
: et voilà - konstruktora ruchu. Dzięki, Olaf, za (moje) oświecenie.Ze względu na kompletność zaimplementowałem również odpowiednie operatory przypisania
operator *=()
do „destrukcyjnego” przecięcia zbiorówoperator +=()
dla "destrukcyjnego" połączenia zbiorów.Próbka
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; }
Skompilowane i przetestowane:
$ 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 } $
źródło
std::set
już implementuje niezbędny konstruktor przenoszenia i operator przypisania, więc nie musisz się tym martwić. Również kompilator najprawdopodobniej wykorzystuje optymalizację wartości zwracanej