Почему в стандартной библиотеке C ++ нет transform_if?

84

Возник случай использования, когда нужно сделать условную копию (1. выполнимая с copy_if), но из контейнера значений в контейнер указателей на эти значения (2. выполнимая с transform).

С доступными инструментами я не могу сделать это менее чем за два шага:

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

Конечно , мы могли бы назвать remove_ifна pvи устранить необходимость временного, еще лучше , хотя, это не сложно реализовать (для одинарных операций) что - то вроде этого:

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. Есть ли более элегантный обходной путь с доступными инструментами стандартной библиотеки C ++?
  2. Есть ли причина, по которой transform_ifего нет в библиотеке? Является ли комбинация существующих инструментов достаточным обходным решением и / или считается ли производительность хорошей?
Никос Афанасиу
источник
(IMO) Название transform_ifподразумевает «преобразование только в том случае, если выполняется определенный предикат». Было бы более наглядное название того, что вы хотите copy_if_and_transform!
Оливер Чарльзуорт
@OliCharlesworth на самом деле copy_ifтакже подразумевает «копировать только в том случае, если выполняется определенный предикат». Это одинаково неоднозначно.
Шахбаз
@Shahbaz: Но вот что copy_ifзначит, правда ?
Оливер Чарльзуорт
2
Я бы не удивился, если бы споры о названии такой вещи были реальной причиной отказа от ее реализации !!
Никос Афанасиу
6
Возможно, мне что-то не хватает в этих комментариях, но как я могу transform_ifскопировать те элементы, которые он не трансформирует, если трансформация может относиться к другому несовместимому типу? Реализация в вопросе - это именно то, что я ожидал от такой функции.

Ответы:

33

Стандартная библиотека отдает предпочтение элементарным алгоритмам.

Контейнеры и алгоритмы должны быть по возможности независимыми друг от друга.

Точно так же алгоритмы, которые могут быть составлены из существующих алгоритмов, используются в качестве сокращений только изредка.

Если вам требуется преобразование if, вы можете просто написать его. Если вы хотите / сегодня /, составляя готовые модели и не неся накладные расходы, вы можете использовать библиотеку диапазонов с ленивыми диапазонами , например Boost.Range , например:

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

Как указывает @hvd в комментарии, transform_ifdouble приведет к другому типу ( doubleв данном случае). Порядок композиции имеет значение, и с помощью Boost Range вы также можете написать:

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

что приводит к разной семантике. Это подчеркивает суть:

это делает очень мало смысла включать std::filter_and_transform, std::transform_and_filter, и std::filter_transform_and_filterт.д. и т.п. в стандартной библиотеке .

Посмотреть образец 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"));
}
sehe
источник
29
Ну, проблема в том, что стандартные алгоритмы нелегко составить, потому что они не ленивы.
Ян Худек
1
@JanHudec Действительно. (прости за это? :)). Вот почему вы используете библиотеку (так же, как вы используете AMP / TBB для параллелизма или Reactive Extensions в C #). Многие люди работают над предложением диапазона + реализацией для включения в стандарт.
sehe
2
@sehe +1 Очень впечатляет, сегодня я узнал кое-что новое! Не могли бы вы сказать нам, кто не знаком с Boost.Range и Phoenix, где мы можем найти документацию / примеры, объясняющие, как использовать boost::phoenixтакие хорошие предикаты без лямбда-выражений? Быстрый поиск в Google не дал ничего подходящего. Благодаря!
Али
1
Я не согласен с тем, что «не имеет смысла включать std :: filter_and_transform». Другие языки программирования также предоставляют эту комбинацию в своей «стандартной библиотеке». Совершенно имеет смысл выполнить итерацию по списку элементов один раз, преобразовывая их на лету, пропуская те, которые не могут быть преобразованы. Другие подходы требуют более одного прохода. Да, вы можете использовать BOOST, но на самом деле вопрос был «Почему в стандартной библиотеке C ++ нет transform_if?». И ИМХО, он прав, сомневаясь в этом. В стандартной библиотеке должна быть такая функция.
Джонни Ди
1
@sehe Что касается «все они используют составные абстракции»: это неправда. В Rust, например, есть именно такой transform_if. Это называется filter_map. Однако я должен признать, что он существует для упрощения кода, но, с другой стороны, можно применить тот же аргумент в случае С ++.
Джонни Ди
6

Новая нотация цикла for во многом снижает потребность в алгоритмах, которые обращаются к каждому элементу коллекции, где теперь проще просто написать цикл и поместить логику на место.

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

Действительно ли сейчас стоит добавить в алгоритм большую ценность? Хотя да, алгоритм был бы полезен для C ++ 03, и действительно, у меня был один для него, он нам сейчас не нужен, поэтому нет реальных преимуществ в его добавлении.

Обратите внимание, что на практике ваш код также не всегда будет выглядеть точно так же: у вас не обязательно есть функции «op» и «pred», и, возможно, придется создавать лямбда-выражения, чтобы они «вписывались» в алгоритмы. Хотя неплохо разделить проблемы, если логика сложна, если это просто вопрос извлечения члена из входного типа и проверки его значения или добавления его в коллекцию, это снова намного проще, чем использование алгоритма.

Кроме того, как только вы добавляете какой-то transform_if, вы должны решить, применять ли предикат до или после преобразования, или даже иметь 2 предиката и применять его в обоих местах.

Так что же мы будем делать? Добавить 3 алгоритма? (И в случае, если компилятор может применить предикат к любому концу преобразования, пользователь может легко выбрать неправильный алгоритм по ошибке, и код все равно компилируется, но дает неверные результаты).

Кроме того, если коллекции большие, хочет ли пользователь выполнить цикл с итераторами или сопоставить / уменьшить? С введением map / reduce вы получите еще больше сложностей в уравнении.

По сути, библиотека предоставляет инструменты, и пользователю предоставляется возможность использовать их в соответствии с тем, что они хотят делать, а не наоборот, как это часто бывает с алгоритмами. (Посмотрите, как пользователь выше пытался изменить что-то, используя накопление, чтобы соответствовать тому, что он действительно хотел сделать).

Для простого примера карта. Для каждого элемента я выведу значение, если ключ четный.

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

Красиво и просто. Замечательно вписать это в алгоритм transform_if?

Дойная корова
источник
4
Если вы думаете, что в моем приведенном выше коде больше места для ошибок, чем в transform_if с двумя лямбдами, одним для предиката и одним для преобразования, тогда, пожалуйста, объясните это. Ассемблер, C и C ++ - это разные языки и имеют разные места. Единственное место, где алгоритм может иметь преимущество перед циклом, - это способность «отображать / сокращать», чтобы работать одновременно над большими коллекциями. Однако таким образом пользователь может контролировать, следует ли выполнять цикл по порядку или уменьшить карту.
CashCow
3
При правильном функциональном подходе функции для предиката и мутатора представляют собой четко определенные блоки, которые делают конструкцию должным образом структурированной. В теле цикла for могут быть произвольные элементы, и каждый цикл, который вы видите, должен быть тщательно проанализирован, чтобы понять его поведение.
Bartek Banachewicz
2
Оставьте правильный функциональный подход для правильных функциональных языков. Это C ++.
CashCow
3
"Необычно вписать это в алгоритм transform_if?" То есть «transform_if алгоритм», за исключением того, что есть все зашиты.
Р. Мартиньо Фернандес
2
Он выполняет эквивалент transform_if. Именно эти алгоритмы призваны упростить ваш код или улучшить его, а не усложнить его.
CashCow
5

Извините, что воскресил этот вопрос спустя столько времени. Недавно у меня было подобное требование. Я решил это, написав версию back_insert_iterator, которая принимает boost :: optional:

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

используется так:

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
Не измеряется - пока пользователи не жалуются, что их опыт зависит от ЦП (т.е. никогда), меня больше беспокоит правильность, чем наносекунды. Однако я не вижу, чтобы это было плохо. Необязательные параметры очень дешевы, поскольку нет выделения памяти, а конструктор Ts вызывается только в том случае, если факультативный параметр действительно заполнен. Я ожидал, что оптимизатор устранит почти весь мертвый код, поскольку все пути кода видны во время компиляции.
Ричард Ходжес
Да уж. Я бы согласился, если бы речь не шла именно об алгоритме общего назначения (на самом деле, об общем строительном блоке внутри них). Это то место, где я обычно не в восторге, если только что-то не настолько простое, насколько это возможно. Кроме того, мне бы хотелось, чтобы дополнительная обработка была декоратором для любого итератора вывода (чтобы, по крайней мере, мы получили возможность компоновки итераторов вывода, пока мы пытаемся устранить отсутствие компоновки алгоритмов).
смотрите
Логически нет разницы, обрабатываете ли вы необязательную вставку через декоратор в итераторе или в функции преобразования. В конечном итоге это просто проверка флага. Я думаю, вы обнаружите, что оптимизированный код в любом случае будет таким же. Единственное, что мешает полной оптимизации, - это обработка исключений. Пометка T как не имеющая конструкторов исключений вылечит это.
Ричард Ходжес
какую форму вы бы хотели, чтобы вызов transform () принял? Я уверен, что мы могли бы создать составной набор итераторов.
Ричард Ходжес
Я тоже :) Я комментировал ваше предложение. Я не предлагал ничего другого (у меня это было давно. Давайте вместо этого будем использовать диапазоны и составные алгоритмы :))
см.
3

Стандарт разработан таким образом, чтобы минимизировать дублирование.

В этом конкретном случае вы можете достичь целей алгоритма более читаемым и лаконичным способом с помощью простого цикла range-for.

// another way

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

Я изменил пример так, чтобы он компилировался, добавил диагностику и представил алгоритм OP и мой рядом.

#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

После того, как я снова нашел этот вопрос через некоторое время и разработал целый ряд потенциально полезных универсальных адаптеров итераторов, я понял, что исходный вопрос не требовал НИЧЕГО больше, чем std::reference_wrapper.

Используйте его вместо указателя, и все будет хорошо:

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

Печать

1 1 
sehe
источник
1

Вы можете использовать copy_ifвместе. Почему бы и нет? Определите OutputIt(см. Копию ):

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

и перепишите свой код:

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
"Почему бы и нет?" - Потому что код предназначен для людей. Для меня трение на самом деле хуже, чем возвращение к написанию объектов функций вместо лямбда-выражений. *static_cast< back_insert_iterator<vector<ha *>> &>(*this) = &arg;является одновременно нечитаемым и излишне конкретным. См. Этот дубль С ++ 17 с более общим использованием.
смотрите
Здесь версия не жестко кодирует базовый итератор (поэтому вы можете использовать его с std::insert_iterator<>или, std::ostream_iterator<>например,), а также позволяет вам предоставить преобразование (например, как лямбда). c ++ 17,
начинает
Обратите внимание, что на данный момент нет особых причин для сохранения базовых итераторов, и вы можете просто: использовать любую функцию , отмечая, что Boost содержит лучшую реализацию: boost :: function_output_iterator . Теперь все, что осталось, это изобретать заново for_each_if:)
см.
Собственно, перечитывая исходный вопрос, давайте добавим голос разума - используя только стандартную библиотеку С ++ 11.
см
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;
}

Использование: (обратите внимание, что CONDITION и TRANSFORM не являются макросами, они являются заполнителями для любых условий и преобразований, которые вы хотите применить)

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
    }
);
user5406764
источник
Вы бы оценили готовность этого внедрения? Будет ли он хорошо работать с некопируемыми элементами? Или ход-итераторы?
sehe
0

Это просто ответ на вопрос 1 «Есть ли более элегантный обходной путь с доступными инструментами стандартной библиотеки C ++?».

Если вы можете использовать C ++ 17, вы можете использовать std::optionalболее простое решение, используя только функциональные возможности стандартной библиотеки C ++. Идея состоит в том, чтобы вернуться std::nulloptв случае отсутствия сопоставления:

Смотрите в прямом эфире на 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;
}

Обратите внимание, что здесь я только что реализовал подход Rust на C ++.

Джонни Ди
источник
0

Вы можете использовать std::accumulatewhich работает с указателем на целевой контейнер:

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

Печать

1 1 
Войцех Мигда
источник