Композиционность алгоритмов STL - PullRequest
Новая
       35

Композиционность алгоритмов STL

36 голосов
/ 19 июля 2011

Алгоритмы STL довольно полезны в C ++. Но что меня раздражает, так это то, что им, похоже, не хватает сочетаемости.

Например, допустим, у меня есть vector<pair<int, int>> и я хочу преобразовать его в vector<int>, содержащий только second член пары. Это достаточно просто: 

std::vector<std::pair<int, int>> values = GetValues();
std::vector<int> result;

std::transform(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return p.second; });

Или, может быть, я хочу отфильтровать vector только для тех пар, у которых first член четный. Также довольно просто: 

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return (p.first % 2) == 0; });

Но что, если я хочу сделать оба? Алгоритм transform_if отсутствует, и для использования transform и copy_if требуется выделение временного vector для хранения промежуточного результата: 

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> temp;
std::vector<int> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(temp),
    [] (std::pair<int, int> p) { return (p.first % 2) == 0; });

std::transform(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return p.second; });

Это кажется мне довольно расточительным. Единственный способ избежать временного вектора, который я могу придумать, - это отказаться от transform и copy_if и просто использовать for_each (или обычный цикл for, в зависимости от того, что вам подходит): 

std::vector<std::pair<int, int>> values = GetValues();
std::vector<int> result;

std::for_each(values.begin(), values.end(),
    [&result] (std::pair<int, int> p) 
        { if( (p.first % 2) == 0 ) result.push_back(p.second); });

Я что-то здесь упускаю? Есть ли хороший способ объединить два существующих алгоритма STL в новый, не требуя временного хранения?

Ответы [ 4 ]

24 голосов
/ 19 июля 2011

Ты прав.Для достижения композиции можно использовать адаптеры Boost.Range .

10 голосов
/ 19 июля 2011

Я думаю, что проблема, к сожалению, структурная

  1. C ++ использует два итератора для представления последовательности
  2. Функции C ++ являются однозначными

, поэтому выне может связать их в цепочку, потому что функция не может возвращать «последовательность».

Можно было бы использовать вместо этого последовательности с одним объектом (, как подход с диапазоном от boost ).Таким образом, вы могли бы объединить результат одной обработки как ввод другой ... (один объект -> один объект).

В стандартной библиотеке C ++ вместо этого выполняется обработка (два объекта -> один объект) и ясно, что это не может быть объединено в цепочку без указания имени временного объекта.

8 голосов
/ 19 июля 2011

Еще в 2000 году проблема была уже отмечена.Гэри Пауэлл и Мартин Вайзер придумали концепцию «представления» и создали название «Библиотека шаблонов».Это не взлетело тогда, но идея имеет смысл.Адаптер «вида» по существу применяет преобразование «на лету».Например, он может адаптировать value_type.

. Концепция, вероятно, должна быть переадресована, теперь у нас есть C ++ 0x.С 2000 года мы достигли определенных успехов в универсальном программировании.

Например, давайте воспользуемся примером от vector<pair<int, int>> до vector<int>.Это может быть довольно просто: 

std::vector<std::pair<int, int>> values = GetValues();
vtl2::view v (values, [](std::pair<int, int> p) { return p.first }); 
std::vector<int> result(view.begin(), view.end());

Или, используя методы boost::bind, еще проще: 

std::vector<std::pair<int, int>> values = GetValues();
vtl2::view v (values, &std::pair<int, int>::first); 
std::vector<int> result(view.begin(), view.end());
0 голосов
/ 05 февраля 2019

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

Фрагмент документа:

  • Считывание до 10 целых чисел из файла "test.txt".
  • Фильтруйте четные числа, возводите их в квадрат и суммируйте их значения. 
    int total = lz::read<int>(ifstream("test.txt")) | lz::limit(10) |
                lz::filter([](int i) { return i % 2 == 0; }) |
                lz::map([](int i) { return i *  i; }) | lz::sum();

Вы можете разбить эту строку на несколько выражений. 

    auto numbers = lz::read<int>(ifstream("test.txt")) | lz::limit(10);
    auto evenFilter = numbers | lz::filter([](int i) { return i % 2 == 0; });
    auto squares = evenFilter | lz::map([](int i) { return i *  i; });
    int total = squares | lz::sum();
  • Даже если это выражение разбито на несколько присвоений переменных, оно не менее эффективно.
  • Каждая промежуточная переменная просто описывает единицу кода, которая должна быть выполнена.Все держится в стеке.

https://github.com/SaadAttieh/lazyCode

...