is_none_of



  • Ahoi

    hat jemand eine Idee für:

    #define is_none_of(val, v1, v2, v3, v4, v5, v6, v7, v8, v9) \
      (val != v1 && val != v2 && val != v3 && ...
    

    Geht da vielleicht was rekursiv? Oder mit Templates? Also am besten wäre ein is_none_of mit variabler Parameterzahl, aber zumindest mit nur einer Ober und keiner Untergrenze.



  • Mit Boost.Preprocessor:

    #include <boost/preprocessor/seq.hpp>
    
    #define AND_IS_UNEQUAL(unused, data, elem) && ((data) != (elem))
    #define IS_NONE_OF(needle, sequence) true BOOST_PP_SEQ_FOR_EACH(AND_IS_UNEQUAL, needle, sequence)
    
    int main() {
      /* IS_NONE_OF(0, (1)(2)(3)) expandiert zu true && ((0) != (1)) && ((0) != (2)) && ((0) != (3) */
      if(IS_NONE_OF(0, (1)(2)(3))) {
        ...
      }
    }
    

    Mit variadischen Templates (C++11):

    template<typename T> bool is_none_of(T const &t) { return true; }
    template<typename T, typename A, typename... Args> bool is_none_of(T const &t, A const &a1, Args... args) {
      return t != a1 && is_none_of(t, args...);
    }
    


  • Etwas weniger spektakulär, ohne schwarze Magie, dafür eine relativ schöne Syntax:

    #include <vector>
    #include <algorithm>
    
    class number
    {
        private:
            struct holder
            {
                explicit holder(int x)
                : x(x)
                , ys()
                {
                }
    
                holder& operator() (int y)
                {
                    ys.push_back(y);
                    return *this;
                }
    
                operator bool () const
                {
                    return std::find(ys.begin(), ys.end(), x) == ys.end();
                }
    
                int              x;
                std::vector<int> ys;
            };
    
        public:
            explicit number(int x)
            : is_none_of(x)
            {
            }
    
            holder is_none_of;
    };
    

    Anwendung:

    int main()
    {
        bool a = number(7).is_none_of(4)(1)(3)(8);
        bool b = number(7).is_none_of(2)(1)(7);
    }
    

    Oder wenn dir das lieber ist, mit entsprechender Umbenennung:

    int main()
    {
        bool a = is(7).none_of(4)(1)(3)(8);
        bool b = is(7).none_of(2)(1)(7);
    }
    

    Falls dir andere Operatoren besser gefallen, kannst du z.B. auch operator<< oder operator, verwenden. Wenn du C++0x nutzen kannst, wären auch Initializer-Lists eine Möglichkeit. Und Variadic Templates sind natürlich ganz elegant.



  • mach den holder-Member private und is_none_of zu einer Funktion, die holder::op() aufruft und eine Referenz zurückgibt. Sonst geht sowas:

    number n7(7);
    n.is_none_of = number(8).is_none_of;
    if(! n7.is_none_of(8, 9, 10))
      std::cout << "WTF???";
    

    😉



  • pumuckl schrieb:

    mach den holder-Member private und is_none_of zu einer Funktion, die holder::op() aufruft und eine Referenz zurückgibt

    Hatte ich zuerst, aber mir kam der Code sonst schon zu gross vor. Solange man nur temporäre Ausdrücke verwendet, ist ja auch alles ok. Aber du hast schon recht, es wäre sicherer 😉

    Übrigens, ich warte auf deinen Metaprogrammierungs-Ansatz 🤡



  • Den Vektor sollte man loswerden. Denkbar etwa

    class number
    {
    private:
      struct holder
      {
        explicit holder(int x)
          : x(x),
            b(true)
        {
        }
    
        holder& operator() (int y)
        {
          b = b && x != y;
          return *this;
        }
    
        operator bool () const
        {
          return b;
        }
    
        int  x;
        bool b;
      };
    
    public:
      explicit number(int x)
        : is_none_of(x)
      {
      }
    
      holder is_none_of;
    };
    

    Einen echten Kurzschlussmechanismus kriegt man so wahrscheinlich nicht hin, oder?



  • So würds mit variadic templates gehen. 😉

    #include <iostream>
    
    template<typename Value, typename Other>
    bool is_none_of(Value toCompare, Other value)
    {
      return (toCompare != value);
    }
    
    template<typename Value, typename Head, typename... Tail>
    bool is_none_of(Value toCompare, Head arg1, Tail... args)
    {
      return (toCompare != arg1) && is_none_of(toCompare, args...);
    }
    
    int main()
    {
            int value = 123;
    
            std::cout << is_none_of(value, 1, 2, 3, 4, 5, 6, 7) << "\n";
            std::cout << is_none_of(value, 120, 121, 122, 123) << "\n";
    }
    

    Edit: Zu spät ... Die Lösung oben war auf so wenig Zeilen gequetscht, hab ich glatt überlesen. 😛



  • seldon, sehr schön! Da hätte ich eigentlich auch drauf kommen können...

    Was meinst du mit "echtem Kurzschluss"? Der operator&& wertet ja den rechten Operanden nicht mehr aus, falls der linke false ist. Aber die Funktionsaufrufe wirst du nicht verhindern können, da sie bei der Anwendung im Quelltext stehen. Je nach Optimierung dürfte der Overhead aber gering sein.

    Die Frage ist, ob die Liste der Werte y zur Kompilierzeit bekannt ist. Unter Umständen könnte man dann da noch ein wenig Geschwindigkeit herausholen. Allerdings wird es kaum deine anfänglichen Vorschläge übertreffen, wo der Ausdruck 1:1 da steht 🙂



  • Naja, wenn ich

    number(7).is_none_of(7)(1)(1)(1)(1)(1);
    

    schreibe, wird einmal b, dann 7 != 7, und dann 5 mal b geprüft. Mit "Kurzschlussmechanismus" meine ich, dass man sich die letzten fünf Prüfungen spart.



  • Variante von seldons/Nexus', ohne die Klassenschachtelung:

    #include <iostream>
    template<class T>
    struct test_t
    {
      T const& t_;
      bool matched;
    
      test_t(T const& t) : t_(t), matched(false) {}
    
      template <class U>
      test_t& operator,(U const& u)
      {
        matched = matched && t_ == u;
        return *this;
      }
    };
    
    template <class T>
    test_t<T> test(T const& t)
    {
      return test_t<T>(t);
    }
    
    template <class T>
    bool is_none_of(test_t<T> const& tt)
    {
      return !tt.matched;
    }
    
    int main()
    {
      std::cout << is_none_of((test(15), 14u, 12l, 3.6)) << '\n';
    }
    

  • Mod

    Ist es eigentlich möglich, ein Funktions-Argumentpack bequem auzusplitten? Ich hatte an so etwas gedacht (Idee: geringere Rekursionstiefe weniger rekursive Instantiierung führt dazu, dass der Compiler das Inlining nicht zu früh aufgibt)

    #include <tuple>
    
    template <typename Tuple>
    struct tuple_split;
    
    template <std::size_t N, typename Tuple>
    struct tuple_ignore_first;
    
    template <std::size_t N, typename T0, typename... Args>
    struct tuple_ignore_first<N, std::tuple<T0, Args...>> : tuple_ignore_first<N-1, std::tuple<Args...>>::type
    {};
    
    template <typename... Args>
    struct tuple_ignore_first<0, std::tuple<Args...>>
    {
        typedef std::tuple<Args...> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, ExtraArgs&..., Args&&... args)
        {
            return tuple_split<Args...>::first::is_not_of(std::forward(value), std::forward(args)...)
                && tuple_split<Args...>::last::is_not_of(std::forward(value), std::forward(args)...);
        };
    };
    
    template <typename Arg>
    struct tuple_ignore_first<0, std::tuple<Arg>>
    {
        typedef std::tuple<Arg> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, ExtraArgs&..., Arg&& arg)
        {
            return value != arg;
        };
    };
    
    template <>
    struct tuple_ignore_first<0, std::tuple<>>
    {
        typedef std::tuple<Args...> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, ExtraArgs&...)
        {
            return true;
        };
    };
    
    template <std::size_t N, typename Tuple>
    struct tuple_ignore_last;
    
    template <std::size_t N, typename... Args, typename TN>
    struct tuple_ignore_last<N, std::tuple<Args..., TN>> : tuple_ignore_last<N-1, std::tuple<Args...>>::type
    {};
    
    template <typename... Args>
    struct tuple_ignore_last<0, std::tuple<Args...>>
    {
        typedef std::tuple<Args...> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, Args&&... args, ExtraArgs&&...)
        {
            return tuple_split<Args...>::first::is_not_of(std::forward(value), std::forward(args)...)
                && tuple_split<Args...>::last::is_not_of(std::forward(value), std::forward(args)...);
        };
    };
    
    template <typename Arg>
    struct tuple_ignore_last<0, std::tuple<Arg>>
    {
        typedef std::tuple<Arg> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, Arg&& arg, ExtraArgs&...)
        {
            return value != arg;
        };
    };
    
    template <>
    struct tuple_ignore_first<0, std::tuple<>>
    {
        typedef std::tuple<Args...> type;
        template <typename T, typename... ExtraArgs>
        void is_not_of(T&& value, ExtraArgs&...)
        {
            return true;
        };
    };
    
    template <typename Tuple>
    struct tuple_split
    {
        typedef tuple_ignore_last<(std::tuple_size<Tuple>::value+1)/2, Tuple> first;
        typedef tuple_ignore_first<std::tuple_size<Tuple>::value/2, Tuple> last;
    };
    
    template <typename T, typename T&& Args>
    void is_not_of(T&& value, Args&&... args)
    {
        return tuple_split<Args...>::first::is_not_of(std::forward(value), std::forward(args)...)
            && tuple_split<Args...>::last::is_not_of(std::forward(value), std::forward(args)...);
    };
    

    So geht das ntürlich nicht. Falls es nicht auf die Reihenfolge des Vergleichs ankommt, gäbe es eine einfache Lösung.



  • Was mir nur so aufgefallen ist: Deine falsche Verwendung von std::forward.


  • Mod

    314159265358979 schrieb:

    Was mir nur so aufgefallen ist: Deine falsche Verwendung von std::forward.

    std::forward<Args>(args)... natürlich. Das ist auch nicht der einzige Syntaxfehler der verbleibt - aber nicht das Problem, um das es mir geht.



  • camper schrieb:

    Idee: geringere Rekursionstiefe weniger rekursive Instantiierung führt dazu, dass der Compiler das Inlining nicht zu früh aufgibt)

    Blöde Frage, aber reicht dazu nicht ganz normales loop unrolling?


  • Mod

    Shade Of Mine schrieb:

    camper schrieb:

    Idee: geringere Rekursionstiefe weniger rekursive Instantiierung führt dazu, dass der Compiler das Inlining nicht zu früh aufgibt)

    Blöde Frage, aber reicht dazu nicht ganz normales loop unrolling?

    Braucht man dafür nicht eine Schleife?
    Ich kann mich erinnern, dass frühere vc-Versionen (05 war es glaube ich), inlining grundsätzlich aufgeben wenn die Rekursionstiefe 16 überschreitet; möglich dass das jetzt nicht mehr der Fall ist.



  • camper schrieb:

    Shade Of Mine schrieb:

    camper schrieb:

    Idee: geringere Rekursionstiefe weniger rekursive Instantiierung führt dazu, dass der Compiler das Inlining nicht zu früh aufgibt)

    Blöde Frage, aber reicht dazu nicht ganz normales loop unrolling?

    Braucht man dafür nicht eine Schleife?

    Ich habe sowas aber mal für ein type-array gebaut wo das count() zu teuer war.

    Die Idee war einfach, statt nur Head und Tails zu nehmen, 10 Heads zu nehmen und einen Tail und das ganze zu überladen. So dass es eine Version mit 1 Item, 5 Items und 10 Items gab.

    Und anstatt dann bei 102 Items eine rekursionstiefe von 102 zu haben, hatte man nur 12 (10mal 10 Items lesen und 2 mal 1 Item lesen).

    Müsste hier doch auch funktionieren, oder?

    Mein Problem ist, dass mein Compiler keine variadic Templates kann - deshalb kann ich die Syntax noch nicht und kann deshalb kein Beispiel zeigen.


  • Mod

    Shade Of Mine schrieb:

    camper schrieb:

    Shade Of Mine schrieb:

    camper schrieb:

    Idee: geringere Rekursionstiefe weniger rekursive Instantiierung führt dazu, dass der Compiler das Inlining nicht zu früh aufgibt)

    Blöde Frage, aber reicht dazu nicht ganz normales loop unrolling?

    Braucht man dafür nicht eine Schleife?

    Ich habe sowas aber mal für ein type-array gebaut wo das count() zu teuer war.

    Die Idee war einfach, statt nur Head und Tails zu nehmen, 10 Heads zu nehmen und einen Tail und das ganze zu überladen. So dass es eine Version mit 1 Item, 5 Items und 10 Items gab.

    Und anstatt dann bei 102 Items eine rekursionstiefe von 102 zu haben, hatte man nur 12 (10mal 10 Items lesen und 2 mal 1 Item lesen).

    Müsste hier doch auch funktionieren, oder?

    Mein Problem ist, dass mein Compiler keine variadic Templates kann - deshalb kann ich die Syntax noch nicht und kann deshalb kein Beispiel zeigen.

    Das wäre gewissermaßen brute-force - ein möglicher Ausweg. Nur scheint mir dass das eigentlich gerade das war, was man durch variadic Templates beseitigen wollte.



  • camper schrieb:

    Nur scheint mir dass das eigentlich gerade das war, was man durch variadic Templates beseitigen wollte.

    Wieso? Du implementiert die Funktion natürlich 5 mal, mit unterschiedlich vielen Parametern. zB 1, 10, 20, 50, 100 - dafür hast du eine enorme Geschwindigkeit, weil deine Rekursionstiefe (auch beim Kompilieren des Templates) enorm klein ist. zB eine Rekursion für 432 Elemente wäre nur noch 8 Ebenen Tief.

    Klar gewinnt das keinen optischen Schönheitsbeweis - aber Loop Unrolling ist halt etwas messy 😉 Wie gesagt, wir hatten einmal das Problem mit so einem Type-Array und der Funktion count() dazu die die Anzahl der Elemente des Arrays liefern sollte. Ab einer gewissen Tiefe ist der Compiler ausgestiegen und hat es nicht mehr kompiliert.



  • Ich hab keinen C++0x-Compiler, aber sollte nicht etwas in der folgenden Art gehen?

    bool is_none_of(int x, initializer_list<int> sequence)
    {
        return find(sequence.begin(), sequence.end(), x) == sequence.end();
    }
    
    is_none_of(5, {6, 7, 2});
    

Log in to reply