Dlaczego w standardowej bibliotece C ++ nie ma transform_if?


83

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?

(IMO) Nazwa transform_ifimplikuje „przekształcanie tylko wtedy, gdy spełniony jest określony predykat”. Bardziej opisowa nazwa tego, co chcesz, byłaby copy_if_and_transform!
Oliver Charlesworth

@OliCharlesworth, w rzeczywistości copy_ifoznacza również „kopiuj tylko wtedy, gdy określony predykat jest spełniony”. Jest równie niejednoznaczne.
Shahbaz

@Shahbaz: Ale tak właśnie copy_ifjest, prawda?
Oliver Charlesworth

2
Nie zdziwiłbym się, gdyby spory o nazwę czegoś takiego były prawdziwym powodem, dla którego go nie wprowadzono !!
Nikos Athanasiou

6
Może czegoś mi brakuje w tych komentarzach, ale jak można transform_if skopiować te elementy, których nie przekształca, jeśli transformacja może być innego niezgodnego typu? Realizacja w pytaniu jest dokładnie tym, czego oczekiwałbym od takiej funkcji.

Odpowiedzi:


33

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"));
}

28
Problem w tym, że standardowych algorytmów nie da się łatwo skomponować, ponieważ nie są leniwe.
Jan Hudec

1
@JanHudec Rzeczywiście. (przepraszam za to? :)). Dlatego używasz biblioteki (podobnie jak używasz AMP / TBB do współbieżności lub reaktywnych rozszerzeń w C #). Wiele osób pracuje nad propozycją zakresu + wdrożeniem do włączenia do standardu.
sehe

2
@sehe +1 Bardzo imponujące, nauczyłem się dziś czegoś nowego! Czy zechciałbyś powiedzieć nam, kto nie jest zaznajomiony z Boost.Range i Phoenix, gdzie możemy znaleźć dokumentację / przykłady, które wyjaśniają, jak używać boost::phoenixdo tworzenia tak ładnych predykatów bez lambd? Szybkie wyszukiwanie w Google nie zwróciło nic odpowiedniego. Dzięki!
Ali

1
Nie zgadzam się co do części „nie ma sensu dołączać części std :: filter_and_transform”. Inne języki programowania również udostępniają tę kombinację w swojej „bibliotece standardowej”. Całkowicie sensowne jest jednorazowe iterowanie listy elementów, przekształcanie ich w locie i pomijanie tych, których nie można przekształcić. Inne podejścia wymagają więcej niż jednego przejścia. Tak, możesz użyć BOOST, ale tak naprawdę pytanie brzmiało: „Dlaczego w standardowej bibliotece C ++ nie ma transform_if?”. I IMHO, on ma rację, kwestionując to. Taka funkcja powinna istnieć w bibliotece standardowej.
Jonny Dee

1
@sehe Odnośnie „wszyscy używają abstrakcyjnych kompozycji”: to nieprawda. Na przykład Rust ma dokładnie taki plik transform_if. To się nazywa filter_map. Muszę jednak przyznać, że ma to na celu uproszczenie kodu, ale z drugiej strony można by zastosować ten sam argument w przypadku C ++.
Jonny Dee

6

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?


4
Jeśli uważasz, że powyższy kod ma więcej miejsca na błędy niż transform_if z 2 lambdami, jedną dla predykatu i jedną dla transformacji, wyjaśnij to. Assembly, C i C ++ to różne języki i mają różne miejsca. Jedynym miejscem, w którym algorytm może mieć przewagę nad pętlą, jest możliwość „mapowania / zmniejszania”, tak aby działał równolegle na dużych kolekcjach. Jednak w ten sposób użytkownik może kontrolować, czy zapętlać sekwencyjnie, czy zmniejszać mapę.
CashCow

3
W poprawnym podejściu funkcjonalnym funkcje predykatu i mutatora to dobrze zdefiniowane bloki, które sprawiają, że konstrukt jest odpowiednio skonstruowany. Ponieważ ciało pętli może zawierać dowolne elementy, a każda pętla, którą widzisz, musi być dokładnie przeanalizowana, aby zrozumieć jej zachowanie.
Bartek Banachewicz

2
Prawidłowe podejście funkcjonalne pozostaw dla odpowiednich języków funkcyjnych. To jest C ++.
CashCow

3
„Masz ochotę dopasować to do algorytmu transform_if?” To jest „algorytm transform_if”, z wyjątkiem tego, że ma wszystko zakodowane na stałe.
R. Martinho Fernandes

2
Wykonuje odpowiednik transform_if. Tyle tylko, że algorytmy mają uprościć kod lub w jakiś sposób go ulepszyć, a nie komplikować.
CashCow

5

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 };
          });

1
Nie mierzone - dopóki użytkownicy nie narzekają, że ich doświadczenie jest związane z procesorem (tj. Nigdy), bardziej interesuje mnie poprawność niż nanosekundy. Jednak nie widzę, żeby był biedny. Opcje są bardzo tanie, ponieważ nie ma alokacji pamięci, a konstruktor Ts jest wywoływany tylko wtedy, gdy opcja opcjonalna jest faktycznie wypełniona. Spodziewałbym się, że optymalizator wyeliminuje prawie cały martwy kod, ponieważ wszystkie ścieżki kodu są widoczne w czasie kompilacji.
Richard Hodges,

Tak. Zgodziłbym się, gdyby nie chodziło dokładnie o algorytm ogólnego przeznaczenia (a właściwie ogólny element konstrukcyjny w nich). To jest miejsce, w którym zwykle nie jestem zachwycony, chyba że coś jest tak proste, jak to tylko możliwe. Ponadto chciałbym, aby opcjonalna obsługa była dekoratorem na dowolnym iteratorze wyjściowym (więc przynajmniej otrzymujemy możliwość komponowania iteratorów wyjściowych, podczas gdy próbujemy zlikwidować brak możliwości komponowania algorytmów).
sehe

Z logicznego punktu widzenia nie ma różnicy, czy obsłużysz opcjonalną wstawkę za pomocą dekoratora w iteratioru, czy w funkcji transformacji. Ostatecznie to tylko test flagi. Myślę, że przekonasz się, że zoptymalizowany kod byłby taki sam w obu przypadkach. Jedyną rzeczą stojącą na drodze do pełnej optymalizacji byłaby obsługa wyjątków. Oznaczanie T jako konstruktorów noexcept wyleczyłoby to.
Richard Hodges

jaką formę ma mieć wywołanie transform ()? Jestem pewien, że moglibyśmy zbudować komponowalny zestaw iteratorów.
Richard Hodges

Ja też :) Komentowałem Twoją sugestię. Nie było zaproponowanie czegoś innego (miałem tak dawno temu Rzućmy zakresy i algorytmy dające się składać zamiast :).)
sehe

3

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;
}

3

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 

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;
}

4
"Dlaczego nie?" - Ponieważ kod jest dla ludzi. Dla mnie tarcie jest w rzeczywistości gorsze niż powrót do pisania obiektów funkcyjnych zamiast lambd. *static_cast< back_insert_iterator<vector<ha *>> &>(*this) = &arg;jest nieczytelny i niepotrzebnie konkretny. Zobacz tę c ++ 17 z bardziej ogólnymi zastosowaniami.
sehe

Oto wersja nie koduje na stałe iteratora bazowego (więc możesz jej używać z std::insert_iterator<>lub std::ostream_iterator<>np.), A także pozwala na dostarczenie transformacji (np. Jako lambda).C ++ 17 zaczyna wyglądać użyteczne / sama C ++ 11
sehe

Zauważ, że w tym momencie nie ma powodu, aby zachować podstawowe iteratory i możesz po prostu: użyć dowolnej funkcji , zauważając, że Boost zawiera lepszą implementację: boost :: function_output_iterator . Teraz wszystko, co pozostało jest ponowne wynalezienie for_each_if:)
sehe

Właściwie, ponownie czytając oryginalne pytanie, dodajmy głos rozsądku - używając tylko standardowej biblioteki c ++ 11.
sehe

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
    }
);

czy oceniłbyś to wdrożenie jako gotowe? Czy działałoby dobrze z elementami, których nie można skopiować? Albo iteratory ruchu?
sehe

0

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.


0

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 
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.