Composabilité des algorithmes STL

Question

Les algorithmes STL sont une chose assez utile en C++. Mais une chose qui m'irrite est qu'ils semblent manquer de composabilité.

Par exemple, disons que j'ai une vector<pair<int, int>> et je veux le transformer en un vector<int> contenant uniquement le second membre de la paire. C'est assez simple :

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

Ou peut-être que je veux filtrer les vector pour seulement les paires dont first est pair. C'est aussi assez simple :

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

Mais que faire si je veux faire les deux ? Il n'y a pas de transform_if et en utilisant à la fois transform y copy_if semble nécessiter l'allocation d'un espace temporaire vector pour contenir le résultat intermédiaire :

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

Cela me semble plutôt inutile. La seule façon à laquelle je pense pour éviter le vecteur temporaire est d'abandonner transform y copy_if et utiliser simplement for_each (ou une boucle for ordinaire, selon ce qui vous convient le mieux) :

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

Est-ce que je rate quelque chose ? Existe-t-il un bon moyen de composer deux algorithmes STL existants en un nouveau sans avoir besoin de stockage temporaire ?

Answer 1

Vous avez raison. Vous pouvez utiliser Adaptateurs Boost.Range pour réaliser la composition.

Answer 2

Je pense que le problème est malheureusement structurel

1. Le C++ utilise deux itérateurs pour représenter une séquence
2. Les fonctions C++ sont à valeur unique

donc vous ne pouvez pas les enchaîner car une fonction ne peut pas retourner "une séquence".

Une option aurait été d'utiliser des séquences à objet unique à la place ( comme l'approche de la gamme de boost ). De cette façon, vous auriez pu combiner le résultat d'un traitement comme l'entrée d'un autre... (un objet -> un objet).

Dans la bibliothèque standard C++, le traitement est plutôt (deux objets -> un objet) et il est clair que cela ne peut être enchaîné sans nommer l'objet temporaire.

Answer 3

En 2000, le problème avait déjà été constaté. Gary Powell et Martin Weiser ont proposé un concept de "vue" et ont inventé le nom "View Template Library". L'idée n'a pas décollé à l'époque, mais elle a du sens. Un adaptateur de "vue" applique essentiellement une transformation à la volée. Par exemple, il peut adapter la vue value_type .

Le concept devrait probablement être réétudié maintenant que nous avons C++0x. Nous avons fait des progrès considérables en matière de programmation générique depuis 2000.

Par exemple, utilisons le vector<pair<int, int>> à vector<int> exemple. Cela pourrait être très simple :

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

Ou, en utilisant le boost::bind techniques, encore plus simples :

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

Answer 4

Desde C++20 vous pouvez utiliser std::ranges::copy avec les adaptateurs de gamme std::views::filter y std::views::values de la Bibliothèque des gammes comme suit :

int main() {
    std::vector<std::pair<int, int>> values = { {1,2}, {4,5}, {6,7}, {9,10} };
    std::vector<int> result;

    auto even = [](const auto& p) { return (p.first % 2) == 0; };
    std::ranges::copy(values | std::views::filter(even) | std::views::values,
                      std::back_inserter(result));

    for (int i : result)
        std::cout << i << std::endl;

    return 0;
}

Sortie :

5
7

Dans la solution ci-dessus, aucun vecteur temporaire n'est créé pour un résultat intermédiaire, car les adaptateurs de vue créent des plages qui ne contiennent pas d'éléments. Ces plages sont simplement des vues sur le vecteur d'entrée, mais avec un comportement d'itération personnalisé.

Code sur Wandbox

Answer 5

Pas sûr que ce soit encore actif, mais... Une nouvelle librairie d'attente légère qui fait ce que vous décrivez. Le document parle de l'évaluation paresseuse et des générateurs composables.

Doc snippet :

• Lisez jusqu'à 10 entiers à partir d'un fichier "test.txt".

• filtrer les nombres pairs, les mettre au carré et additionner leurs valeurs.

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

vous pouvez diviser cette ligne en plusieurs expressions.

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

• Même si cette expression est répartie sur plusieurs affectations de variables, elle n'en est pas moins efficace.
• Chaque variable intermédiaire est simplement décrit simplement une unité de code à exécuter. Tout est conservé dans la pile.

https://github.com/SaadAttieh/lazyCode