max_element + remove_if für einen const vector



  • Hallo,

    ich habe einen vector<double> v, der NANs enthalten kann. Aus diesem möchte ich das größte Element haben.

    Nun hatte ich mir gedacht, ich gehe in zwei Schritten vor, also zuerst die NANs ausfiltern, dann max_element berechnen.

    Also schrieb ich:

    auto m = std::max_element(std::remove_if(v.begin(), v.end(), [](double d){return std::isnan(d);}), v.end());
    

    Nur leider geht das nicht, wenn der vector const ist:

    In file included from /usr/include/c++/4.8/algorithm:62:0,
                     from /tmp/test.cpp:1:
    /usr/include/c++/4.8/bits/stl_algo.h: In instantiation of ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = __gnu_cxx::__normal_iterator<const double*, std::vector<double> >; _Predicate = main()::__lambda0]’:
    /tmp/test.cpp:11:25:   required from here
    /usr/include/c++/4.8/bits/stl_algo.h:1152:23: error: assignment of read-only location ‘__result.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator*<const double*, std::vector<double> >()’
                 *__result = _GLIBCXX_MOVE(*__first);
                           ^
    

    Warum geht das nicht? Ich will doch nur den Zeiger auf das größte Element und nichts ändern! Und wie könnte man es auf diese Weise zum Funktionieren bringen?

    Vollständiges Programm:

    #include <algorithm>
    #include <iostream>
    #include <limits>
    #include <vector>
    
    int main() {
      using namespace std;
      const vector<double> v = {10, numeric_limits<double>::quiet_NaN(), 20};
      auto m = max_element(remove_if(v.begin(), v.end(), [](double d) {
                             return std::isnan(d);
                           }), v.end());
      cout << *m << "\n";
    }
    

    Das Problem selbst habe ich jetzt gelöst, darum geht es mir nicht - ich dachte nur, obige Variante wäre einfacher, da ich unten beim (a<b oder isnan) einmal kurz nachdenken musste:

    auto max_it = std::max_element(y_.begin(), y_.end(), [](double a, double b) { return a < b || std::isnan(a); });
    

    (Unterschiede für "nur nans im vector" mal ignoriert)


  • Mod

    remove_if strukturiert den vector so um, dass alle das Prädikat nicht erfüllenden Elemente am Ende stehen. Der Rückgabewert ist ein Iterator auf das erste dieser Elemente. Diese Lösung ist natürlich, selbst wenn möglich, deutlich ineffizienter als deine zweite.


  • Mod

    Übrigens ist dein Code nach wie vor nicht so effizient wie er sein könnte.

    template <typename InputIt>
    auto max(InputIt first, InputIt last) {
        using type = typename std::iterator_traits<InputIt>::value_type;
        static_assert( std::numeric_limits<type>::is_iec559 );
        first = std::find_if(first, last, [] (float f) {return not std::isnan(f);});
        auto cur = *first;
        if (first == last) return std::numeric_limits<type>::quiet_NaN();
        while (++first != last)
            if (cur < *first) // Falls isnan(*first), ist der Vergleich false
                cur = *first;
        return cur;
    }
    

    Demo.



  • Meine Güte, ich war verwirrt und irgendwie der Meinung, dass remove_if den unterliegenden vector nicht ändert (benutze das normalerweise nur mit erase zusammen). Was ich eigentlich haben wollte, ist sowas wie boost::make_filter_iterator ! Sieht aber irgendwie komplizierter aus als die jetzige Lösung.

    Das ganze ist bei mir ein einem völlig unkritischen Codeteil. Bevor ich da an Performance denke, muss ich mir lieber erst mal überlegen, ob ich bei nur NaN im vector nicht lieber v.end() als Ergebnis vom nan-aware max_element haben will statt NaN...


Anmelden zum Antworten