Подтвердить что ты не робот

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

Использовался случай, когда вы захотели сделать промежуточную копию (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.
  • Есть ли более элегантное обходное решение с доступными инструментами стандартной библиотеки С++?
  • Есть ли причина, по которой transform_if не существует в библиотеке? Является ли сочетание существующих инструментов достаточным обходным решением и/или оценкой эффективности, хорошо себя вести?
4b9b3361

Ответ 1

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

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

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

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

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

Как указывает @hvd в комментарии, transform_if двойной результат в другом типе (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"));
}

Ответ 2

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

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

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

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

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

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

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

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

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

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?

Ответ 3

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

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

// another way

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

Я изменил пример, чтобы он компилировал, добавил некоторые диагностические данные и представил как алгоритм OP, так и my side by side.

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

Ответ 4

Извините, что возобновил этот вопрос так долго. В последнее время у меня было аналогичное требование. Я решил это, написав версию 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 };
          });

Ответ 5

После того, как вы снова нашли этот вопрос через некоторое время и разработали целый набор потенциально полезных универсальных адаптеров итераторов, я понял, что исходный вопрос не требует НИЧЕГО больше, чем 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 

Ответ 6

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 the 'if' part
            *oit++ = TRANSFORM(item);   // Here the 'transform' part
    }
);

Ответ 7

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

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

Ответ 8

Это всего лишь ответ на вопрос 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++ здесь.

Ответ 9

Почему мы не можем написать собственный transform_if? Например:

template <class Iterator, class Predicate, class Function>
void transform_if(Iterator first, Iterator last, Predicate pred, Function func){
    while (first != last) {
        if (pred(first))
            func(*first);
        first++;
    }
}