Совместимость алгоритмов STL

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

Например, скажем, у меня есть 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 (или регулярный цикл, в зависимости от того, что подходит вашему воображению):

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 в новый, не требуя временного хранения?

Ответы

Ответ 1

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

Ответ 2

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

С++ использует два итератора для представления последовательности
Функции С++ однозначны

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

В качестве опции можно было бы использовать однопользовательские последовательности (как подход диапазона от повышения). Таким образом, вы могли бы объединить результат одной обработки в качестве входа другого... (один объект → один объект).

В стандартной библиотеке С++ вместо этого обрабатывается (два объекта → один объект), и ясно, что это невозможно связать, не называя временного объекта.

Ответ 3

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

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

Например, используйте пример vector<pair<int, int>> to 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());

Ответ 4

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

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

Читайте до 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();

Даже если это выражение разбито на несколько переменных, оно не менее эффективно.
Каждая промежуточная переменная просто описывает единицу кода, которая должна быть выполнена. Все держится в стеке.