Lassen Sie a
und b
ganze Zahlen sein, a < b
. Mit einem std::set<int> S
ist eine effiziente und elegante (vorzugsweise ohne explizite Schleifen) Möglichkeit, alle Zahlen aus vector
, die nicht in [a, b]
sind, zu finden und zu speichern (in S
) .
Lösung 1:
%Vor%Lösung 2:
Verschiebe alle Zahlen von a
nach b
in ein set
und verwende std::set_difference
Solution1 enthält eine explizite Schleife, und solution2 scheint nicht sehr effizient zu sein (zumindest in Bezug auf den Speicher). Was würdest du vorschlagen? Ich bin auf der Suche nach einem eleganten STL-ish (Boost ist auch akzeptabel) idiomatische Weise, dies zu tun.
Sie können etwas wie Ihre Lösung # 2 tun. Aber anstatt einen tatsächlichen Container mit dem Bereich [a,b]
zu erstellen, verwenden Sie boost::irange
, was ein virtueller Container für einen numerischen Bereich ist. Auf diese Weise haben Sie keine expliziten Schleifen, es wird in linearer Zeit ausgeführt und nicht zu viel Speicher.
Um es noch schneller zu machen, decken Sie nur den relevanten Teil des Sets ab, indem Sie lower_bound
/ upper_bound
:
Oder mit Boost.Range
s set_difference
:
Das "set" in set_intersection
bedeutet nicht std::set
- es bedeutet einfach eine logische Menge; eine Gruppe von Dingen. Wenn beide Sammlungen sortiert sind, können Sie einfach set_intersection
die beiden in einen dritten Container einfügen.
BEARBEITEN:
Hier ist ein vollständiges Beispiel, das das obige veranschaulicht. Dies verwendet C ++ 11 Lambdas, aber wenn Sie nicht C ++ 11 haben oder keine Lambdas verwenden können, können Sie stattdessen Funktoren verwenden. Beachten Sie das Fehlen expliziter Schleifen.
%Vor%Ausgabe ist:
%Vor%