3. Unterschiede zweier std::vectoren in weiterem vector anfügen

Unterschiede zweier std::vectoren in weiterem vector anfügen

  • K

    comparor schrieb:

    std::back_inserter<std::vector<T> >(out)

    Nö. back_inserter ist ein Funktionstemplate. Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen -- so wie auch hier:

    std::back_inserter(out)

    comparor schrieb:

    Durch die Sortierung müsste das natürlich noch etwas besser gehen.

    die Mengen-Operationen verlangen sogar geordnete Sequenzen. Es "geht" also überhaupt erst, wenn sie geordnet sind. Da hast du in deinem Fall Glück wohl gehabt.

    0
  • ?

    comparor schrieb:

    Eine Funktion, die nur die Referenzen oder Indizes speichert, muss man sich dann wahrscheinlich, wie out es gemacht hat, selber schreiben. Die Objekte sind nämlich nicht so einfach zu kopieren wie im obigen Beispiel.

    Für das Speichern ist in deinem Beispiel nicht die Funktion, sondern der back_insert_iterator zuständig. Du brauchst also nur ihn zu ändern:

    #include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

// -- 15 neue Zeilen -----------------------------------------------------------

template <typename T> struct pointer_traits;
template <typename T> struct pointer_traits<T*> { typedef T element_type; };

template <typename C, template<class> class Inserter>
struct pointer_insert_iterator : Inserter<C> {
  pointer_insert_iterator(C& c) : Inserter<C>(c) {}
  pointer_insert_iterator&
  operator= (typename pointer_traits<typename C::value_type>::element_type& value)
  { *static_cast<Inserter<C>&>(*this) = &value; return *this; }
  pointer_insert_iterator& operator*()     { return *this; }
  pointer_insert_iterator& operator++()    { return *this; }
  pointer_insert_iterator  operator++(int) { return *this; }  
};

template <typename C> pointer_insert_iterator<C, std::back_insert_iterator>
pointer_back_inserter(C& c) { return pointer_insert_iterator<C, std::back_insert_iterator>(c); }

// -----------------------------------------------------------------------------

using namespace std;

// -- 2 Änderungen--------------------------------------------------------------

struct T
{
  int i;
  T(int i) : i(i) {}
  bool operator==(const T& t) const {return i==t.i;}
};
bool operator!=(const T& t1, const T& t2)
{
  return !(t1.operator==(t2));
}

int main()
{
  vector<T> v1;
  vector<T> v2;
  for(int i=0;i<40;++i)
    {
      v2.push_back(i);   
      if(i&1)
        v1.push_back(i);
    }
  vector<T *> out;                                // (1) Pointer anstatt Werte
  std::set_difference(v2.begin(),v2.end(),
                      v1.begin(),v1.end(),
                      pointer_back_inserter(out), // (2) mein Iterator, nicht std::back_iterator
                      std::not_equal_to<T>());

  for(size_t i=0;i<out.size();++i)
    cout << out[i]->i << endl;
}
    0
  • K

    Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen

    Mein aktuelles Beispiel: VS 2010 schafft es nicht bei std::sort aus dem Iterator heraus die Parameter des Vergleichsoperators abzuleiten.

    0
  • ?

    Danke registrarius 👍 !

    Ich muss mich wirklich noch tiefer einarbeiten - auf diese Lösung wäre ich nicht so schnell gekommen.

    @kk: Ich bezog mich darauf, dass out in seinem Code immer den vector von Anfang an durchsucht hat - mein Ansatz wäre gewesen, immer den letzten gültigen Iterator zu speichern und ab diesem zu suchen.
    Mit der kürzeren Schreibweise beim back_inserter hast du natürlich Recht.

    Auch allen anderen natürlich Danke.

    0
  • K

    knivil schrieb:

    Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen

    Mein aktuelles Beispiel: VS 2010 schafft es nicht bei std::sort aus dem Iterator heraus die Parameter des Vergleichsoperators abzuleiten.

    Echt? Zeig mal.

    0
  • K
     

    namespace geo {

template<typename T>
struct vec_2d
{
    T x,y;

    vec_2d() : x(T(0)), y(T(0)) {}
    vec_2d(T const& a, T const& b) : x(a), y(b) {}
};

template<typename T>
bool lt_yx(T const& a, T const& b)
{
    return (a.y==b.y) ? (a.x<b.x) : (a.y<b.y);
}

}

    Und irgendwo im Code:

    std::vector<geo::vec_2d<int>> ps = ...
std::sort(ps.begin(), ps.end(), geo::lt_yx<geo::vec_2d<int>>);

    Das ist nur Copy-Paste aus meinem aktuellen Projekt. Lasse ich den Templateparameter der Vergleichsfunktion beim Aufruf von std::sort weg, also nur geo::lt_yx , so gibt es Compilerfehler bei VS 2010. Keine Ahnung wie gcc damit umgeht. Fuer geo::lt_yx gibt es keine Spezialisierungen oder andere Uneindeutigkeiten. Keine Ahnung ob das als Demo taugt. Es ist kein Minimalbeispiel.

    0
  • C
    Mod

    Dann stimmt das Zitat ja immer noch, in deinem Beispiel stammt das Funktionstemplate, bei dem der Parameter explizit angegeben werden muss, nicht aus std (zufällig). 😉

    Ansonsten verhhält sich der Compiler hier völlig korrekt:

    template <typename RandomAccessIterator, typename Func>
InputIterator sort(RandomAccessIterator first, RandomAccessIterator last, Func comp);

    (aus dem Kopf, müsste aber stimmen). Da comp auch ein Funktionsobjekt sein kann, wird der dritte Funktionsparameter nicht weiter eingeschränkt, mit der Folge, dass bei Templatefunktionen als Argument nichts deduziert werden kann. Dass ist in der STL fast überall so.
    Gäbe es eine Überladung

    template <typename RandomAccessIterator>
InputIterator sort(RandomAccessIterator first, RandomAccessIterator last, bool comp(const typename iterator_traits<RandomAccessIterator>::value_type&, const typename iterator_traits<RandomAccessIterator>::value_type&));

    könnte das Templateargument deiner Templatefunktion deduziert werden.
    Eine solche Überladung existiert aber nicht - und wäre auch nicht besonders nützlich; sobald die Signatur der Vergleichsfunktion abweicht, muss doch wieder auf die andere Überladung ausgewichen werden.

    0
  • K

    Funktionstemplates aus der Standardbibliothek

    Dann habe ich das wohl misverstanden, indem ich "Funktionstemplate" falsch zugeordnet habe.

    0
  • K

    knivil schrieb:

    [cpp]
std::vector<geo::vec_2d<int>> ps = ...
std::sort(ps.begin(), ps.end(), geo::lt_yx<geo::vec_2d<int>>);

    Aha. Nee, so meinte ich das eigentlich nicht. Ich hätte bei

    Es kommt ganz selten mal vor, dass man bei Funktionstemplates aus der Standardbibliothek einen Templateparameter explizit angeben muss. In den meisten Fällen ist die Idee, das dem Compiler zu überlassen.

    noch ein "beim Aufruf" einbauen müssen. Davon abgesehen, dass lt_yx kein Template aus der Standardbibliothek ist, ist das hier ja kein Aufruf von lt_yx. Der findet erst innerhalb von std::sort statt. Allerdings muss der Compiler schon vorher wissen, welche Spezialisierung du meinst. Und ich dachte, du meintest die Template-Parameter von sort. Die hast du ja auch nicht explizit angegeben. Du setzt hier immer noch auf Template-Argument-Deduction bzgl der Template-Parameter von std::sort.

    Aber: Ist dir klar, dass dein Ansatz so nicht der beste bzgl Performance ist? Vergleiche den mal mit diesem Ansatz hier:

    struct lt_yx {
    template<typename T> 
    bool operator()(T const& a, T const& b) 
    { return (a.y==b.y) ? (a.x<b.x) : (a.y<b.y); } 
};

    std::sort(ps.begin(), ps.end(), geo::lt_yx());
    0
  • K

    Ist dir klar, dass dein Ansatz so nicht der beste bzgl Performance ist? Vergleiche den mal mit diesem Ansatz hier

    Welcher Unterschied ist zu erwarten? Ich erwarte bei meinem Ansatz, dass alles "geinlined" wird.

    0
  • K

    knivil schrieb:

    Ich erwarte bei meinem Ansatz, dass alles "geinlined" wird.

    Das ist eine sehr hohe Erwartung; denn die Funktion, die für den Vergleich verwendet werden soll, übergibst du std::sort nur indirekt als Funktionszeiger. Der letzte Template-Parameter bei deiner std::sort-Instantiierung ist ein Funktionszeigertyp und dem Typ allein kann man nicht ansehen, mit welcher Funktion sortiert werden soll. Verstehst du den Unterschied?

    template<class Fun>
void foo(Fun f) {
  f();
}

void bar() {}

struct baz {
  void operator()() const {}
};

int main() {
  foo(bar);    // #1
  foo(baz());  // #2
}

    Bei #1 ist Fun = void(*)(), f also nur ein Funktionszeiger, mit dem man, je nach gespeicherter Adresse beliebige void-Funktionen aufrufen könnte.

    Bei #2 ist Fun = baz und beim Erzeugen der Spezialisierung foo<baz> ist klar, dass f() immer nur baz::operator() sein kann.

    0
Anmelden zum Antworten