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

89

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!

Ich mag Tacos
quelle
"Ich erwarte ein neues Set (nennen wir es s3)" Aber du tust es nicht und du hast es nicht getan. Ich verstehe nicht, wohin Sie die Ergebnisse erwartet haben. Außerdem haben Sie die Dokumentation nicht gelesen, um herauszufinden, welche Argumente zu übergeben sind.
Leichtigkeitsrennen im Orbit

Antworten:

105

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.

Karthik T.
quelle
67
Ich würde gerne verstehen, warum solch eine grundlegende Operation an Mengen eine so arkanisch ausführliche Beschwörung erfordert. Warum nicht eine einfache set<T>& set::isect(set<T>&)Methode, die das Notwendige tut? (Ich würde um eine bitten set<T>& set::operator^(set<T>&), aber das ist wahrscheinlich eine Brücke zu weit.)
Ryan V. Bissell
3
@ RyanV.Bissell Dies ist ein ähnliches Design wie fast alle Algorithmen in <algorithm>so Konsistenz, wenn nichts anderes. Ich nehme an, dieser Stil gibt Ihnen auch Flexibilität. Und ermöglicht die Verwendung der Algen mit mehreren Containern, obwohl dies hier möglicherweise nicht der Fall ist. Auch Ihre Signatur funktioniert möglicherweise nicht, Sie müssen wahrscheinlich einen Wert zurückgeben. Und dass in den Tagen vor der Kopiersemantik eine Doppelkopie gewesen wäre, denke ich. Ich habe C ++ schon eine Weile nicht mehr gemacht, also nimm das mit einer Prise oder 3 Salz
Karthik T
4
Ich betrachte mich immer noch als STL-Neuling, daher gilt auch die Anwendung von Salzkörnern. Mein Kommentarbearbeitungsfenster ist abgelaufen, daher kann ich die Referenz-Fauxpas nicht korrigieren. Mein Kommentar war keine Beschwerde über Konsistenz, sondern eine ehrliche Frage, warum diese Syntax unbedingt so bitter schmecken muss. Vielleicht sollte ich das zu einer SO-Frage machen.
Ryan V. Bissell
3
Tatsächlich ist der größte Teil der C ++ - Standardbibliothek auf diese obskure Weise entworfen. Während die Eleganz des Designs offensichtlich ist (was Generizität betrifft, aber nicht nur), hat die Komplexität der API verheerende Auswirkungen (hauptsächlich, weil die Leute die Räder immer wieder neu erfinden, da sie diejenigen, die mit ihrem Compiler geliefert werden, nicht verwenden können). In einer anderen Welt wären die Designer geschlagen worden, weil sie ihr Vergnügen dem ihrer Benutzer vorgezogen hätten. In dieser Welt ... zumindest haben wir StackOverflow.
3
Dies ist eine "allgemeine Syntax" - Sie können set_intersection auch für einen Vektor und eine Liste ausführen und Ergebnisse in einer Deque speichern, und Sie sollten in der Lage sein, auch diese Sache effizient auszuführen (natürlich ist es Ihr Problem, darauf zu achten, dass beide Quellcontainer werden vor dem Aufruf sortiert. Ich finde es nicht schlecht, das einzige, mit dem ich Probleme habe, ist, dass es auch eine setContainermethode geben könnte, die sich mit einer anderen Menge schneidet. Das Thema, einen Container zu übergeben, anstatt .begin()- .end()ist eine andere Sache - dies wird behoben, sobald C ++ Konzepte hat.
Ethouris
25

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));
billz
quelle
6
back_inserterfunktioniert nicht mit setda sethat keine push_backfunktion.
Jack Aidley
6

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.

Olaf Dietsche
quelle
3
Beachten Sie, dass back_inserter nicht funktioniert, wenn das Ergebnis auch eine Menge sein soll. Dann benötigen Sie std :: inserter wie Karthik.
Joseph Garvin
4

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.

Kemin Zhou
quelle
4

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 }

$
Scheff
quelle
1
std::setimplementiert bereits den erforderlichen Verschiebungskonstruktor und Zuweisungsoperator, sodass Sie sich darüber keine Sorgen machen müssen. Auch der Compiler verwendet höchstwahrscheinlich eine Rückgabewertoptimierung
Olaf Dietsche
@OlafDietsche Danke für deinen Kommentar. Ich habe dies überprüft und die Antwort jeweils verbessert. Über RVO hatte ich bereits einige Diskussionen mit meinen Kollegen, bis ich ihnen im Debugger von VS2013 zeigte, dass dies nicht der Fall ist (zumindest in unserer Entwicklungsplattform). Eigentlich ist es nicht so wichtig, außer wenn Code leistungskritisch ist. Im letzteren Fall behalte ich mich vorerst nicht auf RVO. (Das ist eigentlich nicht so schwierig in C ++ ...)
Scheff
@Scheff gut Scheff (nicht Bose), nette Erklärung.
JeJo
Selbst jetzt ist die Unterstützung von VS für die garantierte Elision von C ++ 17 bedauerlich.
Leichtigkeitsrennen im Orbit