Doppelte Elemente des N-dimensionalen Vektors löschen

Question

Rekursive Vorlagen sind für mich immer noch ziemlich verwirrend und ich habe nicht das Gefühl, dass ich sie so gut benutze, wie ich es sollte. Zum Beispiel habe ich versucht, rekursive Vorlagen zu verwenden, um eine Funktion zu schreiben, die alle doppelten Elemente eines n-dimensionalen Vektors entfernt, und ich glaube, dass ich einen Code habe, der funktioniert. Aber ich bin fast sicher, dass es einen besseren Weg, dies zu tun:

template <typename T> 
    void remove_if_duplicate(std::vector<T>& vec, bool at_end) 
    { 
    static std::set<T> seen; 
    if(!at_end) 
    { 
     auto newEnd = std::remove_if(vec.begin(), vec.end(), [=](const T& value) 
     { 
     if(seen.find(value) != std::end(seen)) 
      return true; 

     seen.insert(value); 
     return false; 
     }); 
     vec.erase(newEnd, vec.end()); 
     std::cout << "\n\nhere: " << at_end << "\n\n"; 
    } 
    if(at_end) {seen.clear();} 
    } 

    template <typename T> 
    void remove_if_duplicate(std::vector<std::vector<T>>& v, bool at_end) 
    { 
    if(!at_end) 
    { 
     for(unsigned int i = 0; i < v.size(); i++) 
     { 
     remove_if_duplicate(v[i], at_end); 
     } 
    } 
    if(at_end) {remove_if_duplicate(v[0], at_end);} 
    } 

template <typename T> 
void remove_duplicates(std::vector<std::vector<T>>& v) 
{ 
    remove_if_duplicate(v, false); 
    remove_if_duplicate(v, true); 
} 

ein Beispiel Siehe hier: http://coliru.stacked-crooked.com/a/6e11f9ababcdfa12

Beachten Sie, wie ich die eingestellte Variable „gesehen“ als statische Variable der Basis erklären Funktion. Ich habe dies getan, damit ich immer noch auf frühere Elemente zugreifen kann, die ich vorher "gesehen" habe, selbst wenn ich durch multidimensionale Vektoren iteriere. Ich kann die Variable "seen" nicht innerhalb der zweiten Funktion deklarieren, weil der Basistyp, an dem die mehrdimensionalen Vektoren templatiert werden, zu diesem Zeitpunkt unbekannt ist (und dann würde auch der Fall eines eindimensionalen Vektors nicht funktionieren). Also muss ich in diese Funktionen boolesche Werte eingeben, um zu entscheiden, wann die Variable statisch gesetzt werden soll, damit ich diese Funktion für andere n-dimensionale Vektoren wieder verwenden kann.

Während es scheint so weit zu arbeiten und gibt mir das Verhalten, das ich will, ich bin mir nicht sicher, ob irgendwelche unerwarteten Bugs als Ergebnis meiner schlechten Implementierung angezeigt werden. Ich denke, dass die Art und Weise, wie ich das hier gemacht habe, alles andere als ideal ist, und ich bin mir sicher, dass es einen besseren, effizienteren Weg gibt. Wie würdest du es anders machen?

Answer 1

Sie können durch die Verwendung einer Hilfsklasse des statischen loszuwerden das richtige set zu konstruieren:

template <typename T> struct inner_type 
{ 
    using type = T; 
}; 

template <typename T> struct inner_type<std::vector<T>> 
{ 
    using type = typename inner_type<T>::type; 
}; 

Dann können Sie tun:

template <typename T> 
void RemoveDuplicatesImpl(std::vector<T>& v, 
          std::set<T>& values) 
{ 
    v.erase(std::remove_if(v.begin(), v.end(), [&](const T& t) 
     { 
      return !values.insert(t).second; 
     }), v.end()); 
} 

template <typename T> 
void RemoveDuplicatesImpl(std::vector<std::vector<T>>& v, 
          std::set<typename inner_type<T>::type>& values) 
{ 
    for (auto& inner : v) { 
     RemoveDuplicatesImpl(inner, values); 
    } 
} 

template <typename T> 
void RemoveDuplicates(std::vector<T>& v) 
{ 
    std::set<typename inner_type<T>::type> values; 
    RemoveDuplicatesImpl(v, values); 
} 

Answer 2

Ich würde nicht einen Satz verwenden, um alle. Da Sie einen std::set verwenden, spielt die Reihenfolge der Elemente im resultierenden Vektor keine Rolle.

template<class T> void RemoveDuplicates(std::vector<T> &v) 
{ 
    std::sort(v.begin(), v.end()); 
    v.erase(v.begin(), std::unique(v.begin(), v.end()); 
} 

template<class T> void RemoveDuplicates(std::vector<std::vector<T> > &v) 
{ 
     // remove duplicates from every individual vector 

     for (auto &i : v) RemoveDuplicates(e); 

     // for every vector, remove any copy of its elements in subsequent vectors 
     auto i = v.begin(); 
     auto end = v.end(); 
     while (i != end) 
     { 
      auto next = std::advance(i, 1); // alternatively next = i+1 
      auto next_i = next; 
      while (next != end) 
      { 
       for (const auto &e : *i) 
        next->erase(next->begin(), std::remove(next->begin(), next->end(), e)); 
       next = std::advance(next, 1);  // alternatively ++next 
      } 
      i = next_i; 
     } 
}