Wie finde ich den Schnittpunkt zweier std :: set in C ++?

Ich habe versucht, den Schnittpunkt zwischen zwei std :: set in C ++ zu finden, aber es wird immer wieder ein Fehler angezeigt.

Ich habe dafür einen kleinen Beispieltest erstellt

#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;
}

Das letztere Programm generiert keine Ausgabe, aber ich erwarte eine neue Menge (nennen wir es s3) mit den folgenden Werten:

s3 = [ 1 , 3 ]

Stattdessen erhalte ich den Fehler:

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>)’

Was ich aus diesem Fehler verstehe, ist, dass es keine Definition gibt set_intersection, die Rb_tree_const_iterator<int>als Parameter akzeptiert .

Außerdem nehme ich an, dass die std::set.begin()Methode ein Objekt dieses Typs zurückgibt.

Gibt es einen besseren Weg, um den Schnittpunkt von zwei std::setin C ++ zu finden? Am liebsten eine eingebaute Funktion?

Vielen Dank!

Sie haben keinen Ausgabe-Iterator für set_intersection bereitgestellt

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result );

Beheben Sie dies, indem Sie so etwas tun

...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
                  std::inserter(intersect,intersect.begin()));

Sie benötigen einen std::insertIterator, da der Satz ab sofort leer ist. Wir können back_ oder front_inserter nicht verwenden, da set diese Operationen nicht unterstützt.

Schauen Sie sich das Beispiel im Link an: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Sie benötigen einen anderen Container, um die Schnittpunktdaten zu speichern. Der folgende Code soll funktionieren:

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

Siehe std :: set_intersection . Sie müssen einen Ausgabe-Iterator hinzufügen, in dem Sie das Ergebnis speichern:

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

Siehe Ideone für eine vollständige Auflistung.

Einfach hier kommentieren. Ich denke, es ist an der Zeit, der Set-Schnittstelle eine Union-Intersect-Operation hinzuzufügen. Lassen Sie uns dies in den zukünftigen Standards vorschlagen. Ich benutze den Standard schon lange. Jedes Mal, wenn ich die eingestellte Operation verwendete, wünschte ich mir, der Standard wäre besser. Für einige komplizierte Mengenoperationen wie intersect können Sie einfach (einfacher?) Den folgenden Code ändern:

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;
}

kopiert von http://www.cplusplus.com/reference/algorithm/set_intersection/

Wenn Ihre Ausgabe beispielsweise eine Menge ist, können Sie output.insert (* first1) ausgeben. Darüber hinaus wird Ihre Funktion möglicherweise nicht als Vorlage verwendet. Wenn Ihr Code kürzer sein kann als die Verwendung der Funktion std set_intersection, fahren Sie fort.

Wenn Sie eine Vereinigung von zwei Mengen durchführen möchten, können Sie einfach setA.insert (setB.begin (), setB.end ()); Dies ist viel einfacher als die set_union-Methode. Dies funktioniert jedoch nicht mit Vektor.

Der erste (gut abgestimmte) Kommentar der akzeptierten Antwort beklagt einen fehlenden Operator für die vorhandenen Standardsatzoperationen.

Einerseits verstehe ich das Fehlen solcher Operatoren in der Standardbibliothek. Auf der anderen Seite ist es einfach, sie (für die persönliche Freude) hinzuzufügen, wenn dies gewünscht wird. Ich habe überladen

• operator *() für Schnittmenge von Mengen
• operator +() zur Vereinigung von Mengen.

Beispiel 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;
}

Zusammengestellt und getestet:

$ 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 }

$ 

Was mir nicht gefällt, ist die Kopie der Rückgabewerte in den Operatoren. Möglicherweise könnte dies mithilfe der Zugzuweisung gelöst werden, aber dies liegt immer noch außerhalb meiner Fähigkeiten.

Aufgrund meines begrenzten Wissens über diese "neue ausgefallene" Bewegungssemantik war ich besorgt über die Operatorrückgaben, die Kopien der zurückgegebenen Sätze verursachen könnten. Olaf Dietsche wies darauf hin, dass diese Bedenken unnötig sind, da sie std::setbereits mit einem Bewegungskonstruktor / einer Zuweisung ausgestattet sind.

Obwohl ich ihm glaubte, dachte ich darüber nach, wie ich das überprüfen sollte (für etwas wie "selbstüberzeugend"). Eigentlich ist es ganz einfach. Da Vorlagen im Quellcode bereitgestellt werden müssen, können Sie einfach mit dem Debugger durchgehen. So legte ich einen Haltepunkt direkt an die return s;von der operator *()und ging mit einstufiges , die mich sofort verbleit instd::set::set(_myt&& _Right) : et voilà - unterwegs Konstruktor. Danke, Olaf, für die (meine) Erleuchtung.

Der Vollständigkeit halber habe ich auch die entsprechenden Zuweisungsoperatoren implementiert

• operator *=() für "destruktive" Schnittmenge von Mengen
• operator +=() für "destruktive" Vereinigung von Mengen.

Beispiel 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;
}

Zusammengestellt und getestet:

$ 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 }

$