Czas kompilacji generuj sekwencję całkowitą z jedną pominiętą

Question

Odpowiedzi here i here są prawie tym, czego potrzebuję. Jednakże, że chcą być zdolne do generowania sekwencji, takich jak:

gen_seq<5, 2> // {0, 1, 3, 4} 
gen_seq<3, 0> // {1, 2} 
// optional behavior that would be useful for me: 
gen_seq<4, 4> // {0, 1, 2, 3} 

w przykładach I wykorzystywanych do generowania gen_seq sekwencję od 0 do n-1, bez I. nie jest obowiązkowo, ja też w porządku z gen_seq gdzie N jest długością sekwencji, a ja brakującym indeksem lub innymi wariantami.

Myślę, że na większość problemów już udzielono odpowiedzi w połączonych pytaniach. Jednak tak naprawdę nie mogę zawinąć głowy, jak włączyć warunek "zostaw to jedno wyjście" dla drugiego parametru.

Najlepiej byłoby, gdybym trzymał się funkcji C++ 11 i unikał C++ 14. Eleganckie i szczególnie czytelne soulutions przy użyciu C++ 14 również mogą być bardzo interesujące.

Answer 1

Możesz użyć następujących:

#if 1 // Not in C++11 // make_index_sequence 
#include <cstdint> 

template <std::size_t...> struct index_sequence {}; 

template <std::size_t N, std::size_t... Is> 
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {}; 

template <std::size_t... Is> 
struct make_index_sequence<0u, Is...> : index_sequence<Is...> { using type = index_sequence<Is...>; }; 

#endif // make_index_sequence 

namespace detail 
{ 
    template <typename Seq1, std::size_t Offset, typename Seq2> struct concat_seq; 

    template <std::size_t ... Is1, std::size_t Offset, std::size_t ... Is2> 
    struct concat_seq<index_sequence<Is1...>, Offset, index_sequence<Is2...>> 
    { 
     using type = index_sequence<Is1..., (Offset + Is2)...>; 
    }; 
} 

template <std::size_t N, std::size_t E> 
using gen_seq = typename detail::concat_seq<typename make_index_sequence<E>::type, E + 1, typename make_index_sequence<(N > E) ? (N - E - 1) : 0>::type>::type; 

static_assert(std::is_same<index_sequence<0, 1, 3, 4>, gen_seq<5, 2>>::value, ""); 
static_assert(std::is_same<index_sequence<1, 2>, gen_seq<3, 0>>::value, ""); 
static_assert(std::is_same<index_sequence<0, 1, 2, 3>, gen_seq<4, 4>>::value, ""); 

Live example

Answer 2

Zawsze świetnie jest pisać swoje pytania.

Właśnie odkryłem, że mogę po prostu użyć metody dziel i rządź i nie generuj od 0 do N/2 i N/2 + 1 do n, ale w pierwszym kroku po prostu generuj od 0 do I - 1 i od I + 1 do N.

Mogę to połączyć z liniową lub logarytmiczną metodą generowania. Teraz czuję się głupio, że o to pytam, ale przynajmniej nie utknąłem.

Answer 3

Prosta metoda liniowa wygenerowania sekwencji liczb całkowitych jest trywialnie dostosować do wyłączając określone elementy, dodając specjalizacje, które obejmuje przypadek, w którym przedmiot jest jeden jest wykluczone:

#include <iostream> 

// general case, ignores X 

template <int N, int X, int... vals> 
struct gen_seq : gen_seq<N - 1, X, N - 1, vals...> { }; 

template <int X, int... vals> 
struct gen_seq<0, X, vals...> { static constexpr int values[] = { vals... }; }; 

// specialisations when vals has had X prepended: remove X 

template <int N, int X, int... vals> 
struct gen_seq<N, X, X, vals...> : gen_seq<N, X, vals...> { }; 

template <int... vals> 
struct gen_seq<0, 0, 0, vals...> : gen_seq<0, 0, vals...> { }; 

template <int X, int... vals> 
constexpr int gen_seq<0, X, vals...>::values[]; 

int main() { 
    for (auto i : gen_seq<5, 2>::values) std::cout << i << std::endl; // 0 1 3 4 
    for (auto i : gen_seq<3, 0>::values) std::cout << i << std::endl; // 1 2 
    for (auto i : gen_seq<4, 4>::values) std::cout << i << std::endl; // 0 1 2 3 
} 

to nie może być tak skuteczny jak inne, bardziej zaawansowanych metod, ale jest to najbardziej czytelny. W przeciwieństwie do twojej własnej odpowiedzi i Jarod42's, nie buduje ona nowego algorytmu na wcześniej istniejącym, ale buduje nowy od zera.