jak znaleźć przecięcie dwóch std :: set w C ++?

93

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_intersectionktó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::setw C ++? Preferowana funkcja wbudowana?

Wielkie dzięki!

Lubię tacos
źródło
„Spodziewam się, że będę miał nowy zestaw (nazwijmy to s3)” Ale nie masz i nie zrobiłeś. Nie rozumiem, gdzie spodziewasz się wyników. Nie przeczytałeś również dokumentacji, aby dowiedzieć się, jakie argumenty przekazać.
Wyścigi lekkości na orbicie

Odpowiedzi:

113

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::insertiteratora, ponieważ zbiór jest teraz pusty. Nie możemy użyć back_ lub front_inserter, ponieważ set nie obsługuje tych operacji.

Karthik T
źródło
71
Chciałbym zrozumieć, dlaczego tak fundamentalna operacja na planie wymaga tak niesamowicie gadatliwej inkantacji. Dlaczego nie prosta set<T>& set::isect(set<T>&)metoda, która nie jest potrzebna? (Poprosiłbym o set<T>& set::operator^(set<T>&), ale to prawdopodobnie most za daleko.)
Ryan V. Bissell
3
@ RyanV.Bissell to jest podobny projekt do prawie wszystkich algorytmów w <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ą
Karthik T
4
Nadal uważam się za nowicjusza w STL, więc zastosowanie ma też sól ziaren. Moje okno edycji komentarza wygasło, więc nie mogę poprawić faux-pas zwrotu przez odniesienie. Mój komentarz nie był zarzutem spójności, ale szczerym pytaniem, dlaczego ta składnia musi koniecznie smakować tak gorzko. Może powinienem postawić to pytanie SO.
Ryan V. Bissell
3
W rzeczywistości większość biblioteki standardowej C ++ jest zaprojektowana w ten niejasny sposób. Podczas gdy elegancja projektu jest oczywista (w porównaniu z ogólnością, ale nie tylko), złożoność API ma druzgocące skutki (głównie dlatego, że ludzie ciągle wymyślają koła, ponieważ nie mogą używać tych, które są dostarczane ze swoim kompilatorem). W innym świecie projektanci zostaliby spoliczkowani za to, że przedkładali ich przyjemność nad ich użytkownika. Na tym świecie ... cóż, przynajmniej mamy StackOverflow.
3
To jest "ogólna składnia" - możesz także wykonać set_intersection na wektorze i na liście i zapisać wyniki w postaci deque, i nawet powinieneś być w stanie zrobić to skutecznie (oczywiście, Twoim problemem jest zadbanie o to, aby oba kontenery źródłowe są sortowane przed wywołaniem tego). Nie uważam tego za źle, jedyne, z czym mam problem, to to, że może istnieć również metoda setkontenera, 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.
Ethouris
25

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));
billz
źródło
6
back_inserternie działa, setponieważ setnie ma push_backfunkcji.
Jack Aidley,
6

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ę.

Olaf Dietsche
źródło
3
Zauważ, że back_inserter nie zadziała, jeśli chcesz, aby wynik był również zestawem, potrzebujesz std :: inserter, takiego jak Karthik.
Joseph Garvin
4

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.

Kemin Zhou
źródło
4

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ów
  • operator +() 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::setjest 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ątku operator *()i przeszedłem do jednego kroku, który natychmiast zaprowadził mnie do std::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ów
  • operator +=() 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 }

$
Scheff
źródło
1
std::setjuż implementuje niezbędny konstruktor przenoszenia i operator przypisania, więc nie musisz się tym martwić. Również kompilator najprawdopodobniej wykorzystuje optymalizację wartości zwracanej
Olaf Dietsche
@OlafDietsche Dzięki za komentarz. Sprawdziłem to i odpowiednio poprawiłem odpowiedź. O RVO miałem już pewne dyskusje z moimi kolegami, dopóki nie pokazałem im w debugerze VS2013, że tak się nie dzieje (przynajmniej na naszej platformie rozwojowej). W rzeczywistości nie jest to takie ważne, chyba że kod ma kluczowe znaczenie dla wydajności. W tym drugim przypadku na razie nie polegam na RVO. (To właściwie nie jest takie trudne w C ++ ...)
Scheff
@Scheff well Scheff (nie Bose), ładne wyjaśnienie.
JeJo
Nawet teraz wsparcie VS dla gwarantowanej elizji C ++ 17 jest żałosne.
Wyścigi lekkości na orbicie