Hat die C ++ STL-Satzdatenstruktur einen Satzdifferenzoperator?
68
Ja, es ist in <algorithm>
und heißt : std::set_difference
. Die Verwendung ist:
#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(result, result.end()));
Am Ende enthält das Set result
die s1-s2
.
std::inserter
stattdessen zu verwenden . Es ist keine Qualifikation erforderlich, da dies eine Funktion ist.Ja, der Algorithmus-Header enthält eine Funktion set_difference .
Bearbeitungen:
Zu Ihrer Information, die eingestellte Datenstruktur kann diesen Algorithmus effizient verwenden, wie in der Dokumentation angegeben . Der Algorithmus funktioniert auch nicht nur für Mengen, sondern für jedes Iteratorpaar über sortierten Sammlungen.
Wie andere bereits erwähnt haben, handelt es sich hierbei um einen externen Algorithmus, nicht um eine Methode. Vermutlich ist das gut für Ihre Anwendung.
quelle
Kein "Operator" im Sinne der Sprache, aber es gibt den Algorithmus set_difference in der Standardbibliothek:
http://www.cplusplus.com/reference/algorithm/set_difference.html
Natürlich sind auch die anderen grundlegenden Mengenoperationen vorhanden - (Vereinigung usw.), wie im Abschnitt "Siehe auch" am Ende des verlinkten Artikels vorgeschlagen.
quelle
Die gewählte Antwort ist korrekt, weist jedoch einige Syntaxfehler auf.
Anstatt von
#include <algorithms>
verwenden
#include <algorithm>
Anstatt von
std::insert_iterator(result, result.end()));
verwenden
std::insert_iterator<set<int> >(result, result.end()));
quelle
std::inserter(result, result.end())
Noch einmal, Boost zur Rettung:
#include <string> #include <set> #include <boost/range/algorithm/set_algorithm.hpp> std::set<std::string> set0, set1, setDifference; boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());
setDifference enthält set0-set1.
quelle
C ++ definiert keinen Satzdifferenzoperator, aber Sie können Ihren eigenen definieren (unter Verwendung des in anderen Antworten angegebenen Codes):
template<class T> set<T> operator -(set<T> reference, set<T> items_to_remove) { set<T> result; std::set_difference( reference.begin(), reference.end(), items_to_remove.begin(), items_to_remove.end(), std::inserter(result, result.end())); return result; }
quelle
Nicht als Methode, aber es gibt die externe Algorithmusfunktion set_difference
template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
http://www.sgi.com/tech/stl/set_difference.html
quelle
Anscheinend schon.
SGI - set_difference
quelle
Alle Antworten, die ich hier sehe, sind O (n). Wäre das nicht besser?:
template <class Key, class Compare, class Allocator> std::set<Key, Compare, Allocator> set_subtract(std::set<Key, Compare, Allocator>&& lhs, const std::set<Key, Compare, Allocator>& rhs) { if (lhs.empty()) { return lhs; } // First narrow down the overlapping range: const auto rhsbeg = rhs.lower_bound(*lhs.begin()); const auto rhsend = rhs.upper_bound(*lhs.rbegin()); for (auto i = rhsbeg; i != rhsend; ++i) { lhs.erase(*i); } return std::move(lhs); }
Das scheint das Richtige zu tun. Ich bin mir nicht sicher, wie ich mit dem Fall umgehen soll, dass
Compare
der Typ sein Verhalten nicht vollständig spezifiziert, wie wennCompare
es ein iststd::function<bool(int,int)>
, aber abgesehen davon scheint dies richtig zu funktionieren und sollte wie O sein ((num überlappend) • log (lhs.size()
)).In dem Fall,
lhs
der nicht enthält*i
, ist es wahrscheinlich möglich, weiter zu optimieren, indem eine O (log (rhs.size()
)) - Suche nach dem nächsten Element vonrhs
> = dem nächsten Element von durchgeführt wirdlhs
. Das würde den Fall optimierenlhs = {0, 1000}
undrhs = {1, 2, ..., 999}
die Subtraktion in der Protokollzeit durchführen.quelle
können wir nur verwenden
set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).
quelle
std::back_inserter
erfordert diepush_back()
Methode für den Zielcontainerresult
. Dies wird nicht funktionieren, wennresult
einstd::set