Dlaczego w standardowej bibliotece C ++ nie ma transform_if?

Przypadek użycia pojawił się, gdy chcieliśmy wykonać kopię warunkową (1. wykonalna z copy_if), ale z kontenera wartości do kontenera wskaźników do tych wartości (2. wykonalne z transform).

Z dostępnymi narzędziami nie mogę tego zrobić w mniej niż dwóch krokach:

#include <vector>
#include <algorithm>

using namespace std;

struct ha { 
    int i;
    explicit ha(int a) : i(a) {}
};

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector
    vector<ha*> pv; // temporary vector
    // 1. 
    transform(v.begin(), v.end(), back_inserter(pv), 
        [](ha &arg) { return &arg; }); 
    // 2. 
    copy_if(pv.begin(), pv.end(), back_inserter(ph),
        [](ha *parg) { return parg->i < 2;  }); // 2. 

    return 0;
}

Oczywiście moglibyśmy nazwać remove_ifna pvi eliminuje potrzebę stosowania tymczasowego, choć jeszcze lepiej, to nie jest trudne do wdrożenia (dla operacji jednoargumentowych) coś takiego:

template <
    class InputIterator, class OutputIterator, 
    class UnaryOperator, class Pred
>
OutputIterator transform_if(InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op, Pred pred)
{
    while (first1 != last1) 
    {
        if (pred(*first1)) {
            *result = op(*first1);
            ++result;
        }
        ++first1;
    }
    return result;
}

// example call 
transform_if(v.begin(), v.end(), back_inserter(ph), 
[](ha &arg) { return &arg;      }, // 1. 
[](ha &arg) { return arg.i < 2; });// 2.

1. Czy istnieje bardziej eleganckie obejście z dostępnymi standardowymi narzędziami bibliotecznymi C ++?
2. Czy jest jakiś powód, dla którego transform_ifnie ma go w bibliotece? Czy połączenie istniejących narzędzi jest wystarczającym obejściem i / lub uważa się, że dobrze się zachowuje pod względem wydajności?

Biblioteka standardowa preferuje podstawowe algorytmy.

Jeśli to możliwe, kontenery i algorytmy powinny być od siebie niezależne.

Podobnie, algorytmy, które mogą składać się z istniejących algorytmów, są dołączane rzadko, jako skrót.

Jeśli potrzebujesz transformacji if, możesz ją napisać w trywialny sposób. Jeśli chcesz / dzisiaj /, komponując ready-mades i nie ponosić narzutów, możesz skorzystać z biblioteki zakresów, która ma zakresów , leniwe zakresy , taką jak Boost .

v | filtered(arg1 % 2) | transformed(arg1 * arg1 / 7.0)

Jak @hvd wskazuje w komentarzu, transform_ifpodwójny wynik w innym typie ( doublew tym przypadku). Kolejność kompozycji ma znaczenie, a dzięki Boost Range możesz również napisać:

 v | transformed(arg1 * arg1 / 7.0) | filtered(arg1 < 2.0)

co skutkuje inną semantyką. To prowadzi do sedna sprawy:

nie ma sensu uwzględniać std::filter_and_transform,std::transform_and_filter , std::filter_transform_and_filteritd. itd. w bibliotece standardowej .

Zobacz przykład Live On Coliru

#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>

using namespace boost::adaptors;

// only for succinct predicates without lambdas
#include <boost/phoenix.hpp>
using namespace boost::phoenix::arg_names;

// for demo
#include <iostream>

int main()
{
    std::vector<int> const v { 1,2,3,4,5 };

    boost::copy(
            v | filtered(arg1 % 2) | transformed(arg1 * arg1 / 7.0),
            std::ostream_iterator<double>(std::cout, "\n"));
}

Nowość w notacji pętli for na wiele sposobów zmniejsza potrzebę stosowania algorytmów, które mają dostęp do każdego elementu kolekcji, gdzie teraz jest czystsze, aby po prostu napisać pętlę i umieścić logikę w miejscu.

std::vector< decltype( op( begin(coll) ) > output;
for( auto const& elem : coll )
{
   if( pred( elem ) )
   {
        output.push_back( op( elem ) );
   }
}

Czy naprawdę daje teraz dużą wartość do umieszczenia w algorytmie? Chociaż tak, algorytm byłby przydatny w C ++ 03 i rzeczywiście miałem go do tego, nie potrzebujemy go teraz, więc nie ma prawdziwej korzyści z dodania go.

Zauważ, że w praktyce twój kod nie zawsze będzie wyglądał dokładnie tak: niekoniecznie masz funkcje „op” i „pred” i być może będziesz musiał stworzyć lambdy, aby dopasować je do algorytmów. Chociaż dobrze jest oddzielić obawy, jeśli logika jest złożona, jeśli chodzi tylko o wyodrębnienie elementu członkowskiego z typu wejściowego i sprawdzenie jego wartości lub dodanie go do kolekcji, jest to o wiele prostsze niż użycie algorytmu.

Ponadto, po dodaniu pewnego rodzaju transform_if, musisz zdecydować, czy zastosować predykat przed transformacją, czy po niej, czy nawet mieć 2 predykaty i zastosować go w obu miejscach.

Więc co będziemy robić? Dodać 3 algorytmy? (A w przypadku, gdy kompilator może zastosować predykat na dowolnym końcu konwersji, użytkownik może łatwo przez pomyłkę wybrać niewłaściwy algorytm, a kod nadal kompiluje się, ale daje błędne wyniki).

Ponadto, jeśli kolekcje są duże, czy użytkownik chce zapętlić się z iteratorami lub zmapować / zmniejszyć? Wraz z wprowadzeniem map / redukuj otrzymujesz jeszcze więcej złożoności w równaniu.

Zasadniczo biblioteka zapewnia narzędzia, a użytkownik pozostaje tutaj, aby wykorzystać je do tego, co chce, a nie na odwrót, jak to często miało miejsce w przypadku algorytmów. (Zobacz, jak powyższy użytkownik próbował przekręcić rzeczy za pomocą narzędzia akumuluj, aby dopasować je do tego, co naprawdę chciał zrobić).

Na przykład mapa. Dla każdego elementu podam wartość, jeśli klucz jest parzysty.

std::vector< std::string > valuesOfEvenKeys
    ( std::map< int, std::string > const& keyValues )
{
    std::vector< std::string > res;
    for( auto const& elem: keyValues )
    {
        if( elem.first % 2 == 0 )
        {
            res.push_back( elem.second );
        }
    }
    return res;
}         

Ładnie i prosto. Masz ochotę dopasować to do algorytmu transform_if?

Przepraszam, że po tak długim czasie wskrzeszam to pytanie. Niedawno miałem podobny wymóg. Rozwiązałem to, pisząc wersję back_insert_iterator, która ma przyspieszenie :: opcjonalne:

template<class Container>
struct optional_back_insert_iterator
: public std::iterator< std::output_iterator_tag,
void, void, void, void >
{
    explicit optional_back_insert_iterator( Container& c )
    : container(std::addressof(c))
    {}

    using value_type = typename Container::value_type;

    optional_back_insert_iterator<Container>&
    operator=( const boost::optional<value_type> opt )
    {
        if (opt) {
            container->push_back(std::move(opt.value()));
        }
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator*() {
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator++() {
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator++(int) {
        return *this;
    }

protected:
    Container* container;
};

template<class Container>
optional_back_insert_iterator<Container> optional_back_inserter(Container& container)
{
    return optional_back_insert_iterator<Container>(container);
}

używane w ten sposób:

transform(begin(s), end(s),
          optional_back_inserter(d),
          [](const auto& s) -> boost::optional<size_t> {
              if (s.length() > 1)
                  return { s.length() * 2 };
              else
                  return { boost::none };
          });

Norma została zaprojektowana w taki sposób, aby zminimalizować powielanie.

W tym konkretnym przypadku można osiągnąć cele algorytmu w bardziej czytelny i zwięzły sposób za pomocą prostej pętli zakresu dla.

// another way

vector<ha*> newVec;
for(auto& item : v) {
    if (item.i < 2) {
        newVec.push_back(&item);
    }
}

Zmodyfikowałem przykład tak, aby się kompilował, dodałem trochę diagnostyki i zaprezentowałem algorytm OP i mój obok siebie.

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

using namespace std;

struct ha { 
    explicit ha(int a) : i(a) {}
    int i;   // added this to solve compile error
};

// added diagnostic helpers
ostream& operator<<(ostream& os, const ha& t) {
    os << "{ " << t.i << " }";
    return os;
}

ostream& operator<<(ostream& os, const ha* t) {
    os << "&" << *t;
    return os;
}

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector
    vector<ha*> pv; // temporary vector
    // 1. 
    transform(v.begin(), v.end(), back_inserter(pv), 
        [](ha &arg) { return &arg; }); 
    // 2. 
    copy_if(pv.begin(), pv.end(), back_inserter(ph),
        [](ha *parg) { return parg->i < 2;  }); // 2. 

    // output diagnostics
    copy(begin(v), end(v), ostream_iterator<ha>(cout));
    cout << endl;
    copy(begin(ph), end(ph), ostream_iterator<ha*>(cout));
    cout << endl;


    // another way

    vector<ha*> newVec;
    for(auto& item : v) {
        if (item.i < 2) {
            newVec.push_back(&item);
        }
    }

    // diagnostics
    copy(begin(newVec), end(newVec), ostream_iterator<ha*>(cout));
    cout << endl;
    return 0;
}

Po tym, jak po pewnym czasie ponownie znalazłem to pytanie i opracowałem całą masę potencjalnie użytecznych generycznych adapterów iteratorów, zdałem sobie sprawę, że pierwotne pytanie nie wymagało NIC więcej niżstd::reference_wrapper .

Użyj go zamiast wskaźnika i jesteś dobry:

Live On Coliru

#include <algorithm>
#include <functional> // std::reference_wrapper
#include <iostream>
#include <vector>

struct ha {
    int i;
};

int main() {
    std::vector<ha> v { {1}, {7}, {1}, };

    std::vector<std::reference_wrapper<ha const> > ph; // target vector
    copy_if(v.begin(), v.end(), back_inserter(ph), [](const ha &parg) { return parg.i < 2; });

    for (ha const& el : ph)
        std::cout << el.i << " ";
}

Wydruki

1 1 

Możesz użyć copy_ifrazem. Dlaczego nie? Zdefiniuj OutputIt(zobacz kopię ):

struct my_inserter: back_insert_iterator<vector<ha *>>
{
  my_inserter(vector<ha *> &dst)
    : back_insert_iterator<vector<ha *>>(back_inserter<vector<ha *>>(dst))
  {
  }
  my_inserter &operator *()
  {
    return *this;
  }
  my_inserter &operator =(ha &arg)
  {
    *static_cast< back_insert_iterator<vector<ha *>> &>(*this) = &arg;
    return *this;
  }
};

i przepisz swój kod:

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector

    my_inserter yes(ph);
    copy_if(v.begin(), v.end(), yes,
        [](const ha &parg) { return parg.i < 2;  });

    return 0;
}

template <class InputIt, class OutputIt, class BinaryOp>
OutputIt
transform_if(InputIt it, InputIt end, OutputIt oit, BinaryOp op)
{
    for(; it != end; ++it, (void) ++oit)
        op(oit, *it);
    return oit;
}

Użycie: (Zwróć uwagę, że WARUNKI i TRANSFORMACJA nie są makrami, są symbolami zastępczymi dowolnego warunku i przekształcenia, które chcesz zastosować)

std::vector a{1, 2, 3, 4};
std::vector b;

return transform_if(a.begin(), a.end(), b.begin(),
    [](auto oit, auto item)             // Note the use of 'auto' to make life easier
    {
        if(CONDITION(item))             // Here's the 'if' part
            *oit++ = TRANSFORM(item);   // Here's the 'transform' part
    }
);

To tylko odpowiedź na pytanie 1 „Czy istnieje bardziej eleganckie obejście z dostępnymi narzędziami biblioteki standardowej C ++?”.

Jeśli możesz użyć C ++ 17, możesz użyć std::optionalprostszego rozwiązania, korzystając tylko z funkcji biblioteki standardowej C ++. Chodzi o to, aby powrócić std::nulloptw przypadku braku mapowania:

Zobacz na żywo w Coliru

#include <iostream>
#include <optional>
#include <vector>

template <
    class InputIterator, class OutputIterator, 
    class UnaryOperator
>
OutputIterator filter_transform(InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
    while (first1 != last1) 
    {
        if (auto mapped = op(*first1)) {
            *result = std::move(mapped.value());
            ++result;
        }
        ++first1;
    }
    return result;
}

struct ha { 
    int i;
    explicit ha(int a) : i(a) {}
};

int main()
{
    std::vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector

    // GOAL : make a vector of pointers to elements with i < 2
    std::vector<ha*> ph; // target vector
    filter_transform(v.begin(), v.end(), back_inserter(ph), 
        [](ha &arg) { return arg.i < 2 ? std::make_optional(&arg) : std::nullopt; });

    for (auto p : ph)
        std::cout << p->i << std::endl;

    return 0;
}

Zauważ, że właśnie zaimplementowałem podejście Rusta w C ++ tutaj.

Możesz użyć tego, std::accumulatektóry działa na wskaźniku do kontenera docelowego:

Live On Coliru

#include <numeric>
#include <iostream>
#include <vector>

struct ha
{
    int i;
};

// filter and transform is here
std::vector<int> * fx(std::vector<int> *a, struct ha const & v)
{
    if (v.i < 2)
    {
        a->push_back(v.i);
    }

    return a;
}

int main()
{
    std::vector<ha> v { {1}, {7}, {1}, };

    std::vector<int> ph; // target vector

    std::accumulate(v.begin(), v.end(), &ph, fx);
    
    for (int el : ph)
    {
        std::cout << el << " ";
    }
}

Wydruki

1 1