AskOverflow.Dev

AskOverflow.Dev Logo AskOverflow.Dev Logo

AskOverflow.Dev Navigation

  • Início
  • system&network
  • Ubuntu
  • Unix
  • DBA
  • Computer
  • Coding
  • LangChain

Mobile menu

Close
  • Início
  • system&network
    • Recentes
    • Highest score
    • tags
  • Ubuntu
    • Recentes
    • Highest score
    • tags
  • Unix
    • Recentes
    • tags
  • DBA
    • Recentes
    • tags
  • Computer
    • Recentes
    • tags
  • Coding
    • Recentes
    • tags
Início / coding / Perguntas / 79447006
Accepted
Ashcoll Ash
Ashcoll Ash
Asked: 2025-02-18 10:47:52 +0800 CST2025-02-18 10:47:52 +0800 CST 2025-02-18 10:47:52 +0800 CST

Função variádica para percorrer o produto cartesiano de vários intervalos

  • 772

Span se refere a uma memória contínua, por exemplo, uma matriz;

template <typename T>
class Span {
public:
    Span(T first, size_t s) ...;
    Span(T first, T lasst) ...;
public:
    // iterating underlying continuous memory;
    begin() ...
    end() ...
    T & operator[](idx) ...
private:
    T first;
    T last;
};

A função de loop pode iterar todos os intervalos de passagem, como um loop de bolhas aninhado;

template <typename Func, typename ...Spans>
void loop(Func func, Spans &&...spans) {
    // question: how to implements ?
}

exemplo

int main() {
    int arr[] {1, 2, 3};
    float arr2[] {1.1, 2.2};
    int arr3[] {-1, -2, -3};
    
    loop(func, Span(arr, 3), Span(arr2, 2));
    /*
        we can get:
        func(1, 1.1);
        func(1, 2.2);
        func(2, 1.1);
        func(2, 2.2);
        func(3, 1.1);
        func(3, 2.2);
    */

    loop(func, Span(arr, 3), Span(arr2, 2), Span(arr3, 3));
    /*
        we can get:
        func(1, 1.1, -1);
        func(1, 1.1, -2);
        func(1, 1.1, -3);
        func(1, 2.2, -1);
        func(1, 2.2, -2);
        func(1, 2.2, -3);
        func(2, 1.1, -1);
        func(2, 1.1, -2);
        ...
    */
}

como implementar a função de loop, usando recursos da linguagem C++ até C++20 está ok, mas sem biblioteca padrão ou biblioteca de terceiros, apenas implementando manualmente;

nenhuma chamada de função de recursão, melhor for loop; faz com que a recursão facilmente cause estouro de pilha;

usando vetor e tupla, a ligação de estrutura está ok;

c++
  • 4 4 respostas
  • 179 Views

4 respostas

  • Voted
  1. Turtlefight
    2025-02-18T12:25:24+08:002025-02-18T12:25:24+08:00

    Com C++23 isso é muito mais fácil graças a std::views::cartesian_product():

    parafuso divino

    template<class Fn, class... Spans>
    void loop(Fn&& fn, Spans... spans) {
        for(auto tuple : std::views::cartesian_product(spans...)) {
            std::apply(std::forward<Fn>(fn), tuple);
        }
    }
    

    Se você estiver limitado ao C++20, terá que fazer o produto cartesiano sozinho - por exemplo, usando recursão e vinculando o valor atual de cada intervalo à função:

    parafuso divino

    template<class Fn, class FirstSpan, class... OtherSpans>
    requires std::ranges::range<FirstSpan> && (std::ranges::range<OtherSpans> && ...)
    void loop(Fn&& fn, FirstSpan first, OtherSpans... otherSpans) {
        for(auto& el: first) {
            if constexpr(sizeof...(OtherSpans) > 0) {
                loop(std::bind_front(fn, el), otherSpans...);
            } else {
                fn(el);
            }
        }
    }
    

    Nenhuma implementação de biblioteca padrão: (conforme solicitado nos comentários)
    godbolt

    template<class Fn, class Span, class... OtherSpans>
    void loop(Fn&& fn, Span firstSpan, OtherSpans... otherSpans) {
        if constexpr(sizeof...(OtherSpans) > 0) {
            for(auto& el : firstSpan) {
                loop(
                    [&](auto&... values) {
                        fn(el, values...);
                    },
                    otherSpans...
                );
            }
        } else {
            for(auto& el : firstSpan) {
               fn(el);
            }
        }
    }
    
    • 8
  2. 康桓瑋
    2025-02-18T12:10:15+08:002025-02-18T12:10:15+08:00

    Você pode combinar ranges::for_eachcom C++23 views::cartesian_productcomo:

    template <typename Func, typename ...Spans>
    void loop(Func func, Spans &&...spans) {
      std::ranges::for_each(
        std::views::cartesian_product(spans...),
        [&](auto&& elem) { std::apply(func, elem); }
      );
    }
    
    • 1
  3. edrezen
    2025-02-18T16:30:57+08:002025-02-18T16:30:57+08:00

    Aqui está uma simplificação de uma resposta deste post que permite gerar em tempo de compilação o produto cartesiano de várias matrizes.

    #include <tuple>
    #include <array>
    #include <type_traits>
    #include <iostream>
    
    ////////////////////////////////////////////////////////////////////////////////
    template<typename FCT, typename...ARRAYS>
    constexpr auto cartesian_product_loop (FCT fct, ARRAYS...arrays)
    {
        // we define the number of entries
        constexpr std::size_t N = (1 * ... * arrays.size());
    
        // we compute the dimensions of the successive parts of the tensor
        std::array<std::size_t,sizeof...(arrays)> dims { arrays.size()... };
        for (std::size_t i=1; i<dims.size(); ++i)  { dims[i] *= dims[i-1]; }
            
        // we iterate each possible entry
        for (std::size_t i=0; i<N; ++i)
        {
            [&]<std::size_t... Is>(std::index_sequence<Is...>) 
            {
               // we demultiplex the current index for each array from the global index 'i'
               auto idx = std::make_tuple ( ( (i*std::get<Is>(dims)) / N) % arrays.size() ...);
    
               // we call the function with the current entry.
               fct (arrays[std::get<Is>(idx)]...);
                
            }(std::make_index_sequence<sizeof...(arrays)>{});
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    
    int main() 
    {
        std::array<int,   3> a1  {1, 2, 3}; 
        std::array<char,  2> a2  {'a','b'}; 
        std::array<double,4> a3  {2.0, 4.0, 6.0, 8.0}; 
    
        auto fct = [] (auto...args)
        {
            ((std::cout << args << ' '), ...) << "\n";
        };
        
        cartesian_product_loop (fct, a1,a2,a3);
    } 
    

    Demonstração

    A ideia principal é iterar um inteiro ide 0 a N-1 (com N o número de entradas possíveis do produto cartesiano) e desse inteiro 'global', recupera-se como uma tupla o índice idxde cada array que faz a entrada atual. Então, é preciso apenas chamar a função fornecida fctcom argumentos sendo uma expressão fold nesse índice idx.

    Ele usa principalmente expressões fold e std::make_index_sequence/ std::index_sequence. Ele também supõe que os arrays fornecidos suportam métodos operator[]e size.

    Funciona com c++17 e superiores.

    • 1
  4. Best Answer
    Weijun Zhou
    2025-02-18T16:46:58+08:002025-02-18T16:46:58+08:00

    Aqui está uma alternativa que usa um array para manter o controle dos índices para cada um dos spans. O array de índices é declarado para ter nSpans+1elementos onde o primeiro elemento serve como um sentinela. O array spanSizesé declarado para ter o mesmo tamanho e também ter um sentinela. A variável carryIndexmantém o controle de qual índice deve ser incrementado. A palavra "carry" aqui se refere ao fato de que os índices são incrementados de uma maneira similar a carries em adições.

    template<class Fn, class... Spans>
    void loop(Fn&& fn, Spans... spans) {
        constexpr std::size_t nSpans = sizeof...(spans);
        // Array containing the sizes of each span, with a sentinel in front
        std::size_t spanSizes[]{0, spans.size()...};
        // Array containing the loop indexes, also with a sentinel in front
        std::size_t indexes[nSpans+1]{};
        // Points to the index that should be incremented, after considering carries from less significant indexes
        std::size_t carryIndex = nSpans;
        // While the sentinel (most significant index) is not reached
        while(indexes[0] == 0){
            // Call `fn` with perfect forwarding, passing in elements picked from each span according to the corresponding index.
            // The +1 accounts for the sentinel.
            [&]<std::size_t... Is>(std::index_sequence<Is...>){
                std::forward<Fn>(fn)(spans[indexes[Is+1]]...);
            }(std::make_index_sequence<nSpans>());
            // Increment the current index.
            ++indexes[nSpans];
            // Loop while there's need to carry to a more significant index
            while(indexes[carryIndex] == spanSizes[carryIndex]){
                // Reset the index.
                indexes[carryIndex] = 0;
                // Update `carryIndex` to point to the next more significant index and increment it.
                ++indexes[--carryIndex];
    
                // The next increment should start over from the least significant index.
                if(indexes[carryIndex] != spanSizes[carryIndex]){
                    carryIndex = nSpans;
                }
            }
        }
    }
    

    Demonstração: https://godbolt.org/z/ejzhe7e5G ( main()Foi retirado da demonstração na resposta de @Turtlefight )

    • 1

relate perguntas

  • Por que os compiladores perdem a vetorização aqui?

  • Erro de compilação usando CMake com biblioteca [fechada]

  • Erro lançado toda vez que tento executar o premake

  • Como criar um tipo de octeto semelhante a std::byte em C++?

  • Somente operações bit a bit para std::byte em C++ 17?

Sidebar

Stats

  • Perguntas 205573
  • respostas 270741
  • best respostas 135370
  • utilizador 68524
  • Highest score
  • respostas
  • Marko Smith

    Reformatar números, inserindo separadores em posições fixas

    • 6 respostas
  • Marko Smith

    Por que os conceitos do C++20 causam erros de restrição cíclica, enquanto o SFINAE antigo não?

    • 2 respostas
  • Marko Smith

    Problema com extensão desinstalada automaticamente do VScode (tema Material)

    • 2 respostas
  • Marko Smith

    Vue 3: Erro na criação "Identificador esperado, mas encontrado 'import'" [duplicado]

    • 1 respostas
  • Marko Smith

    Qual é o propósito de `enum class` com um tipo subjacente especificado, mas sem enumeradores?

    • 1 respostas
  • Marko Smith

    Como faço para corrigir um erro MODULE_NOT_FOUND para um módulo que não importei manualmente?

    • 6 respostas
  • Marko Smith

    `(expression, lvalue) = rvalue` é uma atribuição válida em C ou C++? Por que alguns compiladores aceitam/rejeitam isso?

    • 3 respostas
  • Marko Smith

    Um programa vazio que não faz nada em C++ precisa de um heap de 204 KB, mas não em C

    • 1 respostas
  • Marko Smith

    PowerBI atualmente quebrado com BigQuery: problema de driver Simba com atualização do Windows

    • 2 respostas
  • Marko Smith

    AdMob: MobileAds.initialize() - "java.lang.Integer não pode ser convertido em java.lang.String" para alguns dispositivos

    • 1 respostas
  • Martin Hope
    Fantastic Mr Fox Somente o tipo copiável não é aceito na implementação std::vector do MSVC 2025-04-23 06:40:49 +0800 CST
  • Martin Hope
    Howard Hinnant Encontre o próximo dia da semana usando o cronógrafo 2025-04-21 08:30:25 +0800 CST
  • Martin Hope
    Fedor O inicializador de membro do construtor pode incluir a inicialização de outro membro? 2025-04-15 01:01:44 +0800 CST
  • Martin Hope
    Petr Filipský Por que os conceitos do C++20 causam erros de restrição cíclica, enquanto o SFINAE antigo não? 2025-03-23 21:39:40 +0800 CST
  • Martin Hope
    Catskul O C++20 mudou para permitir a conversão de `type(&)[N]` de matriz de limites conhecidos para `type(&)[]` de matriz de limites desconhecidos? 2025-03-04 06:57:53 +0800 CST
  • Martin Hope
    Stefan Pochmann Como/por que {2,3,10} e {x,3,10} com x=2 são ordenados de forma diferente? 2025-01-13 23:24:07 +0800 CST
  • Martin Hope
    Chad Feller O ponto e vírgula agora é opcional em condicionais bash com [[ .. ]] na versão 5.2? 2024-10-21 05:50:33 +0800 CST
  • Martin Hope
    Wrench Por que um traço duplo (--) faz com que esta cláusula MariaDB seja avaliada como verdadeira? 2024-05-05 13:37:20 +0800 CST
  • Martin Hope
    Waket Zheng Por que `dict(id=1, **{'id': 2})` às vezes gera `KeyError: 'id'` em vez de um TypeError? 2024-05-04 14:19:19 +0800 CST
  • Martin Hope
    user924 AdMob: MobileAds.initialize() - "java.lang.Integer não pode ser convertido em java.lang.String" para alguns dispositivos 2024-03-20 03:12:31 +0800 CST

Hot tag

python javascript c++ c# java typescript sql reactjs html

Explore

  • Início
  • Perguntas
    • Recentes
    • Highest score
  • tag
  • help

Footer

AskOverflow.Dev

About Us

  • About Us
  • Contact Us

Legal Stuff

  • Privacy Policy

Language

  • Pt
  • Server
  • Unix

© 2023 AskOverflow.DEV All Rights Reserve